清华962数据结构 --- Ch10 排序
排序算法的评价指标
- 时间复杂度
- 空间复杂度
- 算法的稳定性(关键字相同的元素再排序之后相对位置不变)
排序算法
- 内部排序 - 数据都存在内存里 (关注如何使时空复杂度更低)
- 外部排序 - 数据太多,无法全部放入内存 (还需要关注如何使读写磁盘次数更少)
内部排序
一、插入排序
每次将一个待排序的记录按照关键字大小插入到前面已经排好的子序列中,直到全部记录插入完成
c
// 直接插入排序
void InsertSort(int A[], int n){
int i, j, temp;
for (i=1;i<n;i++)
if (A[i]<A[i-1]){
temp = A[i];
for (j=i-1;j>=0 && A[j]>temp;--j)
A[j+1] = A[j]
A[j+1] = temp;
}
}
空间复杂度:O (1) 时间复杂度:
- 最好时间复杂度:O (n)
- 最坏时间复杂度:O (n^2)
- 平均复杂度:O (n^2) 算法稳定性:稳定
优化:
c
// 折半插入排序
void InsertSort(ing A[], int n){
int i, j, low, high, mid;
for (i=2;i<=n;i++){
A[0] = A[i];
low = 1; high = i-1;
while(low <= high){
mid = (low + high) / 2;
if (A[mid]>A[0]) high = mid - 1;
else low = mid + 1;
}
for (j = i-1;j>=high + 1;--j)
A[j+1] = A[j];
A[high + 1] = A[0];
}
}
二、希尔排序
先追求表中元素部分有序,再逐渐逼近全局有序 先将待排序表分割成若干的子表(间距为缩小增量 d),重复上述步骤,直到 d=1 为止
void ShellSort(int A[], int n){
int d, i, j;
for (d = n/2; d >= 1; d = d/2)
for (i = d+1; i <= n; ++i)
if (A[i] < A[i-d]){
A[0] = A[i];
for (j = i-d; j>0 && A[0] < A[j]; j-=d)
A[j+d] = A[j];
A[j+d] = A[0];
}
}
空间复杂度:O (1) 时间复杂度:
- 最坏时间复杂度:O (n^2)
- 较优:O (n^1.3) 稳定性:不稳定 适用性:只能基于顺序表,不可基于链表
三、冒泡排序
从后往前(或从前往后)两两比较相邻元素的值,若为逆序(A[i-1] > A[i]), 则交换它们,直到序列比较完
void BubbleSort(int A[], int n){
for (int i=0;i < n-1; i++){
bool flag = false;
for (int j = n-1; j > i; j--)
if (A[j-1] > A[j]){
swap(A[j-1], A[j]);
flag = true;
}
if (flag == false)
return;
}
}
空间复杂度:O (1) 时间复杂度:
- 最好情况:O (n)
- 最坏情况:O (n^2)
- 平均时间复杂度:O (n^2) 稳定性:稳定 适用性:顺序表、链表都可以
四、快速排序
在待排序表中任取一个元素作为基准,通过一趟排序将待排序表划分为独立的两部分,使得左边的所有元素都小于基准,右边的都大于基准,这个过程称为一次划分,通过递归的划分两个子表,就可以完成排序
void Partition(int A[], int low, int high){
int pivot = A[low];
while (low < high){
while (low < high && A[high] >= pivot) --high;
A[low] = A[high];
while (low < high && A[low] <= pivot) ++low;
A[high] = A[low];
}
A[low] = pivot;
return low;
}
//快速排序
void QuickSort(int A[], int low, int high){
if (low < high){
int pivotpos = Partition(A, low, high);
QuickSort(A, low, pivotpos - 1);
QuicjSort(A,pivotpos + 1, high);
}
}
算法效率: 时间复杂度:O (n * 递归层数)
- 最好:O (nlog 2 n)
- 最坏:O (n^2)
- 平均:O (nlog 2 n) 空间复杂度:O (递归层数)
- 最好:O (log 2 n)
- 最坏:O (n) 稳定性:不稳定
若每一次选中的基准元素能将待排序序列划分为均匀的两部分,则递归深度最小,效率最高,反之不然。
五、选择排序
每一趟在待排序元素中选取关键字最小(或最大)的元素加入有序子序列
1、简单选择排序
void SelectSort(int A[], int n){
for (int i = 0; i < n-1; i++){
int min = i;
for (int j = i+1; j < n; j++)
if (A[j] < A[min]) min = j;
if (min != i) swap(A[i], A[min]);
}
}
算法效率: 空间复杂度:O (1) 时间复杂度:O (n^2) 稳定性:不稳定 适用性:既可以用于顺序表,也可以用于链表
2、堆排序
(1)什么是堆
大根堆:完全二叉树中,根>=左、右结点 小根堆:完全二叉树中,根<=左、右结点
(2)如何排序
把所有非终端结点都检查一遍,是否满足根>=左、右,若不满足,将当前结点与更大的一个孩子互换;若元素互换破坏了下一级的堆,则采用相同的方式往下调整。
//建立大根堆
void BuildMaxHeap(int A[], int len){
for (int i = len/2; i>0; i++)
HeadAdjust(A, i, len);
}
//将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
A[0] = A[k];
for (int i = 2*k; i <= len; i++){
if (i < len && A[i] < A[i+1])
i++;
if (A[0] >= A[i])
break;
else{
A[k] = A[i];
k = i;
}
}
A[k] = A[0];
}
//堆排序
void HeapSort(int A[], int len){
BuildMaxHeap(A, len);
for (int i = len; i>1; i--){
swap(A[i], A[1]);
HeadAdjust(A, 1, i-1);
}
}
算法效率: 一个结点,每下坠一层,最多只需要对比关键字 2 次 通过计算,建堆的过程中,关键字对比次数不超过 4n,建堆时间复杂度 = O (n) 排序的时间复杂度 = O (nlog2n) 总体时间复杂度:O (nlog2n) 稳定性:不稳定
六、归并排序
归并:把两个或多个已经有序的序列合并为一个 m 路归并,每选出一个元素需要对比关键字,m-1 次 归并排序:在内部排序之中,一般采用二路归并,把数组内的两个有序序列归并为一个
//辅助数组B
int *B = (int *)malloc(n * sizeof(int));
void Merge(int A[], int low; int mid; int high){
int i, j, k;
for (k = low; k <= high; k++)
B[k] = A[k];
for (i = low, j = mid + 1, k = i; i <= mid && j <=high; k++){
if (B[i] <= B[j])
A[k] = B[i++];
else
A[k] = B[j++];
}
while (i <= mid) A[k++] = B[i++];
while (j <= high ) A[k++] = B[j++];
}
//归并排序
void MergeSort(int A[], int low, int high){
if (low < high){
int mid = (low + high) / 2;
MergeSort(A, low, mid);
MergeSort(A, mid + 1, high);
Merge(A, low, mid, high);
}
}
算法效率: n 个元素进行 2 路归并排序,归并趟数 = [log2n] 每趟归并时间复杂度为 O (n),则算法时间复杂度为 O (nlog 2 n) 空间复杂度:O (n) 稳定性:稳定
七、基数排序
eg:分个、十、百位进行排序,最终达到全局排序
基数排序得到递减序列的过程: 初始化:设置 r 个空队列 按照各个关键字位权重递增的次序(个、十、百),对 d 个关键字位分别做分配和收集 分配:顺序扫描各个元素,若当前处理的关键字位 = x,则将元素插入 Qx 队尾 收集:把 Qr-1,Qr-2,· · · ,Q0 各个队列中的结点依次出队并链接
基数排序不是基于比较的排序算法
算法效率: 空间复杂度:O (r) 时间复杂度: 一趟分配 O (n), 一趟收集 O (r), 总共 d 趟分配、收集,总的时间复杂度 = O (d (n+r)) 稳定性:稳定
基数排序擅长解决的问题:
- 数据元素的关键字可以方便的拆分为 d 组,其 d 较小
- 每组关键字的取值范围不大,即 r 较小
- 数据元素个数 n 较大
外部排序
使用归并排序的方法,最少只需要在内存中分配 3 块大小的缓冲区,就可以对任意大小的文件进行排序 外部排序时间开销 = 读写外存的时间 + 内部排序所需时间 + 内部归并所需时间
优化方法:
- 多路归并 采用多路归并可以减少归并趟数,从而减少磁盘 I/O 次数 对于 r 个初始归并段做 k 路归并,则归并树可以用 k 叉树表示,若树高为 h,则归并趟数=h-1=[logkr] K 越大,r 越小,归并趟数越少,读写次数越少。 弊端:需要开辟 k 个输入缓冲区,内存开销增加;每挑一个关键字需要对比(k - 1)次
- 减少初始归并段数量 若能增加初始归并段的长度,则可以减少初始归并段数量r
一、败者树
用败者树减少关键字对比次数 败者树看可以视为一棵完全二叉树(多一个头头),k 个叶结点分别是当前参加比较的元素,非叶子结点用来记忆左右子树中的“失败者”,而让胜者往上继续进行比较,一直到根节点为止。
对于 k 路归并,第一次构造败者树需要对比关键字 k-1 次,有了败者树,选出最小元素只需要对比关键字[log 2k]次
二、置换-选择排序
用置换-选择排序减少初始归并段数量
三、最佳归并树
归并过程中磁盘 I/O 次数 = 归并树的 WPL * 2 要让磁盘 I/O 次数最少,就要让归并树的 WPL 最小 --- 哈夫曼树!
对于 k 叉归并,若初始归并段的数量无法构成严格的 k 叉归并树(无法整除),则需要补充几个长度为 0 的“虚段”,再进行哈夫曼树的构造
确定添加虚段的数量: k 叉的最佳归并树一定是一棵严格的 k 叉树(树中只包含度为 k、0 的结点)设度为 k 的结点有 nk 个,度为 0 的界定啊有 n0 个,归并树总结点数为 n,则: 初始归并段数量 + 虚段数量 = n0 n = n0 + nk N 0 = (K-1) nk + 1 nk = (n0-1)/(nk-1) K nk = n -1
若(初始归并段数量-1)%(k-1)= 0, 说明刚好可以构成严格 k 叉树 若(初始归并段数量-1)%(k-1)!= 0,则需要补充(k-1)- u 个虚段