数据结构（查找、排序）
AI-摘要
Zpeng GPT
AI初始化中...
介绍自己
生成本文简介
推荐相关文章
前往主页
前往tianli博客
本文最后更新于 2024-03-23，欢迎来到我的Blog! https://www.zpeng.site/
第七章、查找
1. 线性表的查找
1.1. 顺序查找
应用范围：
- 顺序表或线性表表示的****静态查找表。
- 表内元素之间****无序。
顺序表的表示：
typedef struct {
KeyType key; // 关键字域
ValueType val; // 值域
} ElemType;
typedef struct {
ElemType* R; // 表基础地址
int length; // 表长
} SqList;
SqList ST; // 定义顺序表ST
在顺序表ST中查找值为key的数据元素：
int search_seq(SqList ST, KeyType key) {
for(int i = ST.length - 1; i >= 0; i--) {
if(ST.R[i].key == key) return i;
}
return -1;
}
// 哨兵
int search_seq(SqList ST, KeyType key) {
ST.R[0].key = key;
for(int i = ST.lengt - 1; ST.R[i].key != key; i--);
return i;
}
比较次数与key的位置有关：
- **查找第 **i 个元素，需要比较 n-i+1 次。
- **查找失败，需要比较 **n+1 次。
- 时间复杂度：
O(n)。 - 空间复杂度：一个辅助空间用来存放哨兵，
O(1)。
1.2. 二分查找
二分查找前提：必须是有序序列。
// 1. 普通二分查找算法
int search_bin(SqList ST, KeyType key) {
int low = 0;
int high = ST.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(ST.R[mid].key == key) return mid;
else if(key < ST.R[mid].key) high = mid - 1;
else low = mid + 1;
}
return -1;
}
// 2. 二分查找递归算法
int search_bin(SqList ST, KeyType key, int low, int high) {
if(low > high) return -1;
int mid = (low + high) / 2;
if(key == ST.R[mid]) return mid;
if(key < ST.R[mid]) return search_bin(ST, key, low, mid-1);
if(key > ST.R[mid]) return search_bin(ST, key, mid+1, high);
}
二分查找的性能分析—判定树。
时间复杂度：O(logn)。
1.3. 分块查找
分块查找也叫做索引顺序查找。
分块查找的条件：
- 将表分成几块，且表 或者有序，或者****分块有序；分块有序是指：若 i < j，则第 j 块中所有记录的关键字均大于第 i 块中最大的关键字。
- 建立"索引表"（每个结点含有****最大关键字域和指向本块第一个结点的指针，且按关键字有序）。
分块查找的查找效率：查找效率 = 对索引表查找的ASL + 对块查找的ASL。
1.4. 查找方法的比较
2. 树表的查找
2.1. BST
定义：BST可以是空树，或者满足如下性质的二叉树，
- 若其****左子树非空，则左子树上所有结点的值均小于根结点的值；
- 若其****右子树非空，则左子树上所有结点的值均大于等于根结点的值；
- 其左右子树本身又各是一颗二叉排序树。
BST的存储结构：
// 定义数据类型
typedef struct {
KeyType key;
ValueType value;
} ElemType;
// 定义BST结点
typedef struct _node {
ElemType data;
struct _node* lchild;
struct _node* rchild;
} Node;
// 定义BST
typedef struct {
Node* root;
int size;
} BST;
算法思想：
- 若查找的关键字等于根结点，成功；
- 否则：
- 若小于根结点，查其左子树；
- 若大于根结点，查其右子树；
- 在左右子树上的操作类似。
Node* search(Node* x, KeyType key) {
if(x == NULL) return x;
if(x->data == key) return x;
if(key < x->data) return search(x->lchild, key);
if(key > x->data) return search(x->rchild, key);
}
BST的查找分析：
含有 n 个结点的二叉排序树的平均查找长度和树的形态有关。
BST的插入操作：
// 插入
Node* put(Node* x, KeyType key, ValueType value) {
if(x == NULL) {
x = (Node*)malloc(sizeof(Node));
x->data = key;
x->lchild = NULL;
x->rchild = NULL;
return x;
}
if(key < x->data) x->left = put(x->left, key, value);
else if(key > x->data) x->right = put(x->right, key, value);
else x->value = value;
return x;
}
BST的删除操作：
**第一种情况是，**如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
**第二种情况是，**如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
**第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。**我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。
/**
* 删除二叉查找树的结点
*/
void deleteNode(Bst* bst, int key) {
Node* p = bst->root; // p指向要删除的节点，初始化指向根结点
Node* pp = NULL; // pp记录的是p的父结点
while(p != NULL && p->key != key) { // 遍历二叉树寻找目标结点
pp = p;
if(key > p->key)
p = p->right;
else
p = p->left;
}
if (p == NULL) return ; // 没有找到
// 1.要删除的结点有两个子节点
if(p->left != NULL && p->right != NULL) { // 查找右子树的最小结点
Node* minP = p->right; // 初始化minP，指向右子树的根结点
Node* minPP = p; // minPP表示minP的父结点
while(minP->left != NULL) {
minPP = minP;
minP = minP->left;
}
p->key = minP->key; // 将minP的数据替换到p中
p->value = minP->value;
p = minP; // 下面就变成删除minP了
pp = minPP; // 这种类型属于删除pp的左子结点(p无子结点)
}
// 2.要删除的结点是叶子结点或仅有一个子结点
Node* child; // p的子结点
if(p->left != NULL) // p只有左子结点
child = p->left;
else if(p->right != NULL) // p只有右子结点
child = p->right;
else // p无子结点
child = NULL;
if(pp == NULL)
bst->root = child; // 删除的p是根结点
else if (pp->left == p)
pp->left = child; // 删除的p是pp的左子结点
else
pp->right = child; // 删除的p是pp的右子结点
}
总结：其实BST中删除结点，表面上是三种情况，本质上就两种情况。其一，目标结点只有左子结点或右子结点；其二，目标结点没有子结点。一定要注意对目标结点有左右子结点的情况进行转化。
2.2. 平衡二叉树
平衡二叉树：
- **又称 **AVL 树。
- 一颗平衡二叉树或者是空树，或者是具有以下性质的****二叉排序树：
- 左子树与右子树的高度之差的绝对值小于等于1；
- 左子树和右子树也是平衡二叉树。
平衡因子：为了方便起见，给每个结点附加一个平衡因子，给出该结点左子树与右子树的高度差。
平衡因子 = 结点左子树的高度 - 结点右子树的高度。平衡二叉树上所有结点的平衡因子只能是 -1 、0 或 1。
平衡调整的四种类型
3. 散列表的查找
3.1. 散列函数
散列函数的构造方法
(1)除留余数法。
3.2. 处理冲突的方法
开放地址法
基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素插入。
(1)线性探测法。
**例：关键码集为 {47，7，29，11，16，92，22，8，3}，散列表的长度 m = 11；散列函数为 **Hash(key) = key mod 11 ；拟用线性探测法解决冲突。
(2)二次探测法。
链地址法
基本思想：相同散列地址的记录链成一单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。
3.3. 散列表的查找
第八章、排序
排序方法的分类：
- 按数据存储介质：内部排序和外部排序。
- 内部排序：数据量不大、数据在内存，无需内外存交换数据。
- 外部排序：数据量较大、数据在外存（文件排序）。外部排序时，要将数据分批调入内存来排序，中间结果还要及时存放外存，显然外部排序就很复杂。
- 按比较器个数：串行排序和并行排序。
- 串行排序：单处理器（同一时刻比较一对元素）。
- 并行排序：多处理器（同一时刻比较多对元素）。
- 按主要操作：比较排序和基数排序。
- 比较排序：插入排序、交换排序、选择排序、归并排序。
- 基数排序：不比较元素的大小，仅仅根据元素本身的取值确定其有序位置。
- 按辅助空间：原地排序和非原地排序。
- 原地排序：辅助空间用量为
O(1)的排序方法。 - 非原地排序：辅助空间用量超过
O(1)的排序方法
- 原地排序：辅助空间用量为
- 按稳定性：稳定排序和非稳定排序。
- 稳定排序：能够使任何数值相等的元素，排序后相对次序不变。
- 非稳定排序：不是稳定排序的方法。
- 按自然性：自然排序和非自然排序。
- 自然排序：输入数据越有序，排序的速度越快的排序方法。
- 非自然排序：不是自然排序的方法。
存储结构——顺序存储结构：
#define MAXSIZE 20
typedef int KeyType;
typedef int ValueType;
// 定义记录的数据类型
typedef struct {
KeyType key;
ValueType value;
} RecordType;
// 定义顺序表
typedef struct {
RecordType r[MAXSIZE];
int length;
} SqList;
1. 插入排序
- 顺序法定位插入位置：直接插入排序。
- 二分法定位插入位置：二分插入排序。
- 缩小增量多遍插入排序：希尔排序。
1.1. 直接插入排序
/**
* 可以直接类比插入扑克牌
*/
void sort(SqList* list) {
int* a = list->r;
int N = list->length;
for(int i = 1; i < N; i++) {
int temp = a[i]; // temp来保存当前i位置的值
int j = i;
while(j > 0 && temp < a[j - 1]) {
// 当前temp值比i前面的值都小，就整体后移一位(当前i前面的值都是有序的)
a[j] = a[j-1];
j--;
}
a[j] = temp; // 最后将temp的值插入到合适的位置
}
}
算法效率分析：
- 原始数据越接近有序，排序速度越快。最好情况
O(n)。 - 最坏情况下（输入数据是逆向有序的）。
O(n2) - 平均情况下，耗时差不多是最坏情况的一半。
O(n2)。 - 直接插入排序是稳定排序。
1.2. 折半插入排序
/**
* 折半插入排序
*/
void sort(int a[], int N) {
int i, temp, low, high, mid;
for(i = 1; i < N; i++) {
temp = a[i];
low = 0;
high = i - 1;
// 折半查找确定插入位置：即为low+1的位置
while(low <= high) {
mid = (low + high) / 2;
if(temp < a[mid]) high = mid - 1;
else low = mid + 1;
}
// 将元素后移,腾出位置
int j = i - 1;
while(j > low) {
a[j+1] = a[j];
j--;
}
a[j] = temp;
}
}
算法效率分析：
- 时间复杂度为
O(n2)。 - 空间复杂度为
O(1)。 - 折半插入排序是一种稳定的排序方法。
1.3. 希尔排序
直接插入排序在什么情况下效率比较高？
- 直接插入排序在****基本有序时，效率较高。
- 直接插入排序的****记录个数较少时，效率较高。
希尔排序的出发点：直接插入排序比较一次移动一步，希尔排序比较一次移动一大步。
希尔排序基本思想：
- 先将整个待排记录序列分割成****若干子序列，分别进行直接插入排序。
- **待整个序列中的记录"**基本有序"时，再对全体记录进行一次直接插入排序。
希尔排序的特点：
- 一次移动，移动位置较大，跳跃式地接近排序后的最终位置。
- 最后一次只需要少量移动。
- 增量序列必须是递减的，最后一个必须是1。
- 增量序列应该是互质的。
- 希尔排序是不稳定的排序算法。
import static com.ymy.sort.utils.SortedUtils.*;
/**
* 希尔排序
* [S, H, E, L, L, S, O, R, T, E, X, A, M, p, L, E]
*
* [L, E, E, A, M, H, L, E, S, S, O, L, T, p, X, R]
* [A, E, E, E, H, L, L, L, M, O, R, S, S, T, X, p]
*/
public class Shell {
public static void main(String[] args) {
String[] a = new String[]{"S", "H", "E", "L", "L", "S", "O", "R", "T", "E", "X", "A", "M", "p", "L", "E"};
sort(a);
}
public static void sort(Comparable[] a) {
int N = a.length;
int h = 1;
while (h < N / 3) h = 3 * h + 1;
while (h >= 1) {
for (int i = h; i < N; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exchange(a, j, j - h);
}
}
h = h / 3;
}
}
}
2. 交换排序
2.1. 冒泡排序
基本思想：
每趟不断将记录两两比较，并按"前小后大"规则交换。
/**
* 冒泡排序
*/
void sort(int a[], int N) {
int T = N - 1; // 冒泡排序(N-1)趟完成
int temp; // temp 保存交换时的临时变量
for(int i = 1; i <= T; i++) {
for(int j = 1; j <= N - i; j++) { // j <= N-i 后边的大元素就不需要比较了
if(a[j-1] > a[j]) {
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
/**
* 算法改进
*/
void sort(int a[], int N) {
int T = N - 1; // 冒泡排序(N-1)趟完成
int temp; // temp 保存交换时的临时变量
int flag = 1; // flag表示是否有交换的标记
for(int i = 1; i <= T && flag == 1; i++) {
flag = 0;
for(int j = 1; j <= N - i; j++) { // j <= N-i 后边的大元素就不需要比较了
if(a[j-1] > a[j]) {
flag = 1; // 发生交换flag设置为1，若本趟没有交换flag保持为0
temp = a[j];
a[j] = a[j-1];
a[j-1] = temp;
}
}
}
}
冒泡排序算法分析：
- 最好时间复杂度是
O(n)。 - 最坏时间复杂度为
O(n2)。 - 平均时间复杂度为
O(n2)。
2.2. 快速排序
基本思想：
- 任取一个元素（一般为第一个）为中心；
- 所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；
- 对各子表重新选择中心元素并依此规则调整；
- 直到每个子表的元素只剩一个。
void sort(int a[], int N) {
quickSort(a, 0, N - 1);
}
// 快速排序
void quickSort(int a[], int lo, int hi) {
if(hi <= lo) return;
int j = partition(a, lo, hi);
quickSort(a, lo, j - 1);
quickSort(a, j + 1, hi);
}
// 获取切割点
int partition(int a[], int lo, int hi) {
int i = lo, j = hi + 1; // 左右扫描的指针
int v = a[lo]; // 切分数组的元素(默认使用第一个)
while(i < j) {
while(a[++i] < v) if(i == hi) break;
while(a[--j] > v) if(j == lo) break;
if(i >= j) break;
exch(a, i, j);
}
exch(a, lo, j); // 将分割的值放到合适的位置
return j;
}
// 交换元素
void exch(int a[], int idx1, int idx2) {
if(a == NULL) return ;
int temp = a[idx1];
a[idx1] = a[idx2];
a[idx2] = temp;
}
快速排序算法分析：
- 时间复杂度：
O(nlogn)。 - 空间复杂度：快速排序不是原地排序，用到了递归需要使用系统栈。平均条件下需要
O(logn)的栈空间。 - 快速排序不稳定。
- 快速排序不适于原本有序或基本有序的序列进行排序。
3. 选择排序
3.1. 简单选择排序
基本操作：
- **首先通过 **n - 1 次关键字比较，从 n 个记录中找出关键字最小的记录，将它与第一个记录交换；
- **再通过 n - 2 次关键字比较，从 剩余的n - 1 个记录中找出关键字最小的记录，将它与第二个记录交换；
- **重复上述操作，共进行 **n - 1 趟排序后，排序结束。
void sort(int a[], int N) {
// 执行 n-1 趟
for(int i = 1; i <= N-1; i++) {
// 最小值的下标
int min = i - 1;
for(int j = i; j < N; j++) if(a[j] < a[min]) min = j;
// 交换
int temp = a[i-1];
a[i-1] = a[min];
a[min] = temp;
}
}
时间复杂度：
- 记录移动次数：
- 最好情况：0。
- 最坏情况：3(n-1)。
- **比较次数：**无论待排序列处于什么状态，选择排序所需进行的"比较次数"相同。
- 简单选择排序是不稳定的排序。
3.2. 堆排序
(1)堆的定义：
(2)堆排序基本思想：
若在输出****堆顶的最小值（最大值）后，使得剩余 n - 1 个元素的序列重新又建成一个堆，则得到的 n 个元素的次小值（次大值）...如此反复，便能得到一个有序序列，这个过程称之为堆排序。
(3)如何在输出堆顶元素后。调整剩余元素为一个新的堆？
小根堆：
- 输出堆顶元素之后，****以堆中最后一个元素代替(编号最大的元素)；
- **然后将根结点值与左、右子树的根结点值进行比较，**并与其小者进行交换；
- 重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶到叶子的调整过程为"筛选"。
/**
* 堆排序
*
* @Param int a[] 数组
* @Param int N 堆中结点数量
*/
void sort(int a[], int N) {
// 循环建立初始堆
for(int i = N / 2; i >= 0; i--) {
heapAdjust(a, i, N);
}
// 进行 n-1 次循环完成排序
for(int i = N - 1; i > 0; i--) {
// 最后一个元素和第一个元素交换
int temp = a[i];
a[i] = a[0];
a[0] = temp;
// 筛选 a[0] 结点，得到剩余i个结点的堆
heapAdjust(a, 0, i);
}
}
/**
* 堆调整：大根堆
* 小根堆的调整只需要调整如下语句：
* 1. if(child + 1 < N && a[child] > a[child + 1]) child++;
* 2. if(temp <= a[child]) break;
*
* @Param int a[] 数组
* @Param int parent 父节点
* @Param int N 堆中结点的数量
*/
void heapAdjust(int a[], int parent, int N) {
int temp = a[parent]; // temp 保存当前父节点
int child = 2 * parent + 1; // 获得左孩子
while(child < N) {
// 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点
if(child + 1 < N && a[child] < a[child + 1]) child++;
// 如果父结点的值已经大于孩子结点的值，则直接结束
if(temp >= a[child]) break;
// 把孩子结点的值赋给父节点
a[parent] = a[child];
// (1)(2)任意两条语句任取一个都可以实现堆调整
a[child] = temp; // 这句容易理解(1)
// 选取孩子结点的左孩子结点，继续向下筛选
parent = child;
child = 2 * child + 1;
}
// a[parent] = temp; // 这句赋值次数会变少，但是不好理解(2)
}
(4)堆的建立
for(int i = N / 2; i >= 0; i--) {
heapAdjust(a, i, N);
}
堆排序算法分析：
- 初始堆所需要的时间不超过
O(n)。 - 排序阶段(不含堆初始化)：
- 一次重新堆化所需时间不超过
O(logn)； - n - 1 次循环所需时间不超过
O(nlog)。
- 一次重新堆化所需时间不超过
- 堆排序的时间复杂度：
O(nlogn)。 - 无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好"或"最坏"的状态。
- 堆排序是不稳定的排序方法。
4. 归并排序
基本思想：将两个或者两个以上的有序子序列"归并"为一个有序序列。
/**
* 归并排序
*/
public class Merge {
/**
* 归并需要的额外的数组
*/
private static Comparable[] aux;
public static void sort(Comparable[] a) {
aux = new Comparable[a.length]; // 数组aux初始化
sort(a, 0, a.length - 1);
}
/**
* 归并排序
*
* @param a 目标数组
* @param lo 开始下标
* @param hi 结束下标
*/
private static void sort(Comparable[] a, int lo, int hi) {
if (hi <= lo) return; // 递归的出口
int mid = (lo + hi) >>> 1; // 计算mid中间值
sort(a, lo, mid); // 将左半边排序
sort(a, mid + 1, hi); // 将右半边排序
merge(a, lo, mid, hi); // 归并结果
}
/**
* 原地归并方法
* 将a[lo...mid]和a[mid+1...hi]归并
* 前提：a[lo...mid]和a[mid+1...hi]都是有序的！
* For Example：
* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
* E E G M O R R S | A E E L M P T X
* 主要比较aux[i]和aux[j]的大小,只要满足less(aux[j],a[i])那么a[k]=aux[j++],
* 其他情况下就是a[k]=aux[i++];不过当i>mid的时候,就是左边遍历完了,就是a[k]=aux[j++];
* 右边遍历完了就是a[k]=aux[i++]
*
* @param a 目标数组
* @param lo 开始下标
* @param mid 中间下标
* @param hi 结束下标
*/
private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo;
int j = mid + 1;
// 将a[lo..hi]复制到aux[lo..hi]
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
// 将aux数组归并到a数组中
for (int k = lo; k <= hi; k++) {
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (less(aux[j], aux[i]))
a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
归并排序算法分析：
- 时间复杂度：
O(nlogn)。 - 空间复杂度：
O(n)。 - 归并排序是稳定排序。
5. 基数排序
基本思想：分配 + 收集。基数排序也叫做桶排序或箱排序。设置若干个箱子，将关键字为 k 的记录放入第 k 个箱子，然后在按序号将非空的连接。
基数排序：数字是有范围的，均由 0-9 这十个数字组成，则只需要设置是个箱子，相继按个、十、百...进行排序。
/**
* 求数据的最大位数
* @Param int a[] 待排数组
* @Param int N 待排数组长度
*/
int maxbit(int a[], int N) {
// 找到数组中的最大元素
int max = a[0];
for(int i = 1; i < N; i++) {
if(a[i] > max) max = a[i];
}
int cnt = 0;
int temp = max;
while(temp > 0) {
temp /= 10;
cnt++;
}
return cnt;
}
/**
* 基数排序
*
* @Param int* a 待排数组
* @Param int N 待排数组长度
*/
void sort(int* a, int N) {
int mbit = maxbit(a, N); // 数据的最大位数
int* temp = (int*)malloc(sizeof(int) * N); // 临时数组
int* count = (int*)malloc(sizeof(int) * 10); // 计数器(桶)
int radix = 1; // 用于"/10"或"/100"等 方便获得数据的各位的值
// 根据数据的最大位数来确定要进行基数排序的次数
for(int i = 1; i <= mbit; i++) {
// 计数器(桶)初始化
for(int j = 0; j < 10; j++)
count[j] = 0;
// 统计每个桶中的记录数
for(int j = 0; j < N; j++) {
int k = (a[j] / radix) % 10;
count[k]++;
}
// 将 temp 数组中的位置依次分配给每个桶(这里牛B)！
for(int j = 1; j < 10; j++)
count[j] = count[j-1] + count[j];
// 将桶中所有记录依次收集到 temp 数组中(这里也牛B)!
for(int j = N - 1; j >= 0; j--) {
int k = (a[j] / radix) % 10;
temp[count[k] - 1] = a[j];
count[k]--; // 这里的计数器-1至关重要
}
// 将 temp 数组中的数据复制到 a 数组中
for(int j = 0; j < N; j++)
a[j] = temp[j];
radix *= 10;
}
}
6. 各种排序方法的比较
评论
匿名评论
隐私政策
你无需删除空行，直接评论以获取最佳展示效果
