第八章 排序

分类

1. 插入排序：
   • 直接插入排序：每次将一个待排序的记录按其关键字大小插入到前面已排好的子序列中，直到全部记录插入完成
   • 折半插入排序：插入排序的序列分为“[有序][无序]”，每次会从无序序列中取出第一个元素，插入到有序序列中。折半插入是优化了“在有序序列中找合适的位置”这一步，因此影响的只是插入时比较的次数。对于时间复杂度来说，直接插入算法的时间复杂度主要是因为元素的“移动”，而折半插入并没有改变这部分，因此复杂度不变
   • 希尔排序：设置增量d为n/2, n/4, …, 1。将整个表L分割成L[i, i+d, i+2d, …, i+kd]的特殊子表，对各个子表分别进行直接插入排序。即，希尔=分割子表+各子表插入排序
2. 交换排序：
   • 冒泡排序：从前往后（或从后往前）两两比较相邻元素，若为逆序就交换，直到序列比较完。最多需要n-1趟，每趟都可使一个元素移动到最终位置
   • 快速排序：在待排序表中取一个元素作为枢轴（通常取首元素），一趟排序将表划分为两部分，枢轴左边的元素全都小于它，右边的都大于它，而枢轴则落在其最终位置上，称为一次“划分”。分别递归地对两个子表重复上述过程，直至每部分只有一个元素或为空，即所有元素放在了其最终位置上
3. 选择排序：
   • 简单选择排序：每一趟在待排序元素中选取关键字最小的元素加入有序子序列，共需进行n-1趟处理
   • 堆排序：先将序列调整为大根堆，然后排序。排序方法是每一趟将堆顶元素加入有序子序列，然后再将剩下的待排序序列再次调整为大根堆
4. 归并排序：若low
5. 基数排序：
6. 外部排序：若要进行k路归并排序，就在内存中分配k个输入缓冲区和1个输出缓冲区

一些总结：

1. 选择排序（简单选择排序和堆排序）、冒泡排序的每一趟都会找到一个最大/小值归位
2. 插入排序某一次的有序数组只是当前的有序数组，并不完全，每次都会往这个不完全体的有序数组中添加一个元素
3. 快速排序每一趟都有一个枢轴值归位（不一定是最大最小值，如果是最大最小值，快排的效率会很低）
4. 通过比较（除基数排序外的所有排序方法）进行排序的算法的时间复杂度下界是$O(nlo{g}_{2}n)$。这样的排序算法有：堆排序、快排、归并排序

一、插入排序

1. 不带哨兵

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;
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

2. 带哨兵

void InsertSort(int A[], int n){
	int i, j;
	for (i=2; i<=n; i++){
		if (A[i]<A[i-1]){
			A[0] = A[i];
			for (j=i-1; A[0]<A[j]; --j){ // 不用每次循环都判断j>=0
				A[j+1] = A[j];
			}
			A[j+1] = A[0];
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

3. 折半插入排序

   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 = (high+low)/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];
   	}
   }
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18

二、 希尔排序

思想：先追求表中元素部分有序，再逐渐逼近全局有序
这里的A[0]只是暂存单元，不是哨兵（循环语句中会判断若j<=0就到了插入位置）

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];
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

三、冒泡排序

每一趟都能使最小的元素被放在最终位置（也可以改动以下代码使每一趟把最大的元素被放在最终位置）

void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

四、快速排序

void QuickSort(int A[], int low, int high){
	if (low<high){
		int pivotpos = Partition(A, low, high);
		QuickSort(A, low, pivotpos-1);
		QuickSort(A, pivotpos+1, high);
	}
}

int 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

五、简单选择排序（属于选择排序）

每一趟在待排序元素中选取关键字最小的元素加入有序子序列（即有序子序列放在整个序列的开头，每一趟找到的最小元素放在有序子序列的末尾）

void SelectSort(int A[], int n){
	for (int i=0; i<n-1; i++){
		int min = i;
		for (int j=i+1; i<n; j++){
			if (A[j]<A[min])
				min = j;
		}
		if (min!=i)
			swap(A[i], A[min]);
	}
}

void swap(int &a, int &b){
	int temp = a;
	a = b;
	b = temp;
}		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

六、堆排序（属于选择排序）

先建堆，再排序。建堆时让编号$\le \frac{n}{2}$的所有节点依次下坠（自底向上调整各分支节点），下坠规则就是小元素与关键字更大的孩子交换位置。排序时让堆顶元素加入有序子序列（大根堆排序时是让堆顶元素与堆底元素交换），堆底元素换到堆顶后，进行下坠调整，恢复大根堆的特性。将排序过程重复n-1趟

1. 大根堆
   • 建立大根堆（A[0]初始值为空）

     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];  // A[0]的作用为暂存子树根节点（即要下坠的那个小元素）
     	for (int i=2*k; i<=len; i*2){  // 让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];
     }
     1
     2
     3
     4
     5
     6
     7
     8
     9
     10
     11
     12
     13
     14
     15
     16
     17
     18
     19

     这里有个常考考点：若一个节点有两个孩子，则其“下坠”一层，需要对比关键字两次（孩子对比选最大，该节点再与大孩子对比）；若下方只有一个孩子，则“下坠”一层只需对比关键字1次

   • 基于建立的大根堆，进行堆排序：每一趟将堆顶元素加入有序子序列（即有序子序列放在整个序列的结尾，每一趟找到的最大元素放在有序子序列的开头），并将待排序元素再次调整为大根堆（又进行一轮小元素不断下坠）

     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);
     	}
     }
     1
     2
     3
     4
     5
     6
     7

七、归并排序

归并即把两个或多个已经有序的序列合并成一个

int *B = (int *)malloc(n*sizeof(int)); // 辅助数组B

void Merge(int A[], int low, int mid, int high){
	int i, j, k;
	for (k=low; k<=high; k++)
		B[k] = A[k]; // 将A中所有元素复制到B中
	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);  // 归并
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

八、基数排序

基数排序不是基于比较的排序算法
只考手动模拟，几乎不考代码

1. 基数排序擅长解决的问题
   • 数据元素的关键字可以方便地拆分为d组，且d较小
   • 每组关键字的取值范围不大，即r较小
   • 数据元素个数n较大
2. 基数排序通常基于链式存储实现：
   • 定义包含r个队列元素的数组，每个队列保存两个指针（*front和*rear），每个队列中的元素包含数据和指向下一个元素的指针

     typedef struct LinkNode{
     	ElemType data;
     	struct LinkNode *next;
     } LinkNode, *LinkList;
     
     typedef struct{
     	LinkNode *front, *rear;
     } LinkQueue;
     1
     2
     3
     4
     5
     6
     7
     8

九、外部排序

1. 败者树：
   • 解决的问题：使用多路平衡归并可减少归并趟数，但用老土方法从k个归并段选出一个最小/最大元素需要对比关键字k-1次，构造败者树可以使关键字对比次数减少到$\lceil lo{g}_{2}k\rceil$
   • 败者树可视为一棵完全二叉树（多了一个头头）。k个叶节点分别对应k个归并段中当前参加比较的元素，非叶子节点用来记忆左右子树中的“失败者”，而让胜者往上继续进行比较，一直到根节点
2. 置换-选择排序：

算法效率