本周将会介绍几种常见的排序算法。
简单排序
简单排序是几个简单的排序算法的统称，下面来一一介绍。
冒泡排序
冒泡排序的思想比较直观，每次循环时，会将数组（或链表）内相邻的两个元素进行比较，按照规定的递增（或递减）顺序向后移动，一直到重复到末尾，基本代码如下：1
2
3
4
5
6
7
8
9void Bubble_Sort(ElementType A[], int N) {
for(P=N-1; P>=0; P--) {
for(i=0; i<P; i++) {
if(A[i] > A[i+1]) {
Swap(A[i], A[i+1]);
}
}
}
}
代码框架十分简单，但是这样会有一个问题，那就是待排序列在已经有序的情况下，依然会进行两次循环，尽管不会交换相邻元素的值，但是还是会进行判断，会白白浪费时间。仔细想一下，如果输入序列是有序的，那么元素的值一次也不会交换，根据这个特点，可以对上述的代码进行一点小优化，添加一个标志位，一次有序后就可以直接跳出循环了。具体代码如下：1
2
3
4
5
6
7
8
9
10
11
12void Bubble_Sort(ElementType A[], int N) {
for(P=N-1; P>=0; P--) {
flag = 0;
for(i=0; i<P; i++) {
if(A[i] > A[i+1]) {
Swap(A[i], A[i+1]);
flag = 1;
}
}
if(!flag) break;
}
}
按照上述代码的思路，可以较为清晰的分析出冒泡排序算法的时间复杂度：
- 最好的情况，序列为顺序序列，$T = O(N)$
- 最坏的情况，序列为逆序序列，$T = O(N^2)$
另外，对于冒泡排序而言，每一次冒泡结束（内层循环结束一轮）后都会有一个元素被放到这个序列有序后的最终位置上，而且，冒泡排序也不会交换相同元素的位置（使用$>$而不是$\geq$），所以冒泡排序是稳定的排序算法，再者，冒泡排序还有一个优点，即排序的方向是一定的，只会按照一个方向遍历存储数据的数据结构，这是其他排序算法无法达到的。
插入排序
插入排序有个很形象的例子，就是打扑克牌时“理牌”的过程，不过可能有点差别。区别在于，理扑克牌时，手上是没有牌的，而需要理的牌在牌堆里面，也就是说，有两个空间可以放牌，但插入排序实际上只使用了一个内存空间，这样的话，每一次插入时就需要先找到插入的位置了。
按照“理牌”的过程来描述就是：先摸一张牌，从后往前找到合适的插入位置，将比这张牌大的牌向后移（腾出位置），再将新牌插入到这个位置下即可。基本代码如下：1
2
3
4
5
6
7
8
9void Insertion_Sort(ElementType A[], int N) {
for(P=1; P<N; p++) {
temp = A[P];
for(i=P; i>0 && A[i-1]>temp; i--) {
A[i] = A[i-1];
}
A[i] = temp;
}
}
插入排序和冒泡排序的时间复杂度类似：
- 最好的情况，序列为顺序序列，$T = O(N)$
- 最坏的情况，序列为逆序序列，$T = O(N^2)$
同时，插入排序也是稳定的排序算法。
时间复杂度下界
对于下标$i < j$，如果$A[i] > A[j]$，则称$(i, j)$是一对逆序对（Inversion）如序列${2, 3, 1}$中，$(2, 1)$和$(3, 1)$分别是一对逆序对，逆序对的个数称为逆序数，这与线性代数中的概念是一致的。
在冒泡排序和插入排序中，每次交换位置的两个相邻元素正好消去 1 个逆序对，那么它们的时间复杂度就是：$T(N, I) = O(N+I)$，其中$I$是逆序对的对数。很明显，如果序列基本有序，则$I$值可忽略不计，时间复杂度仅为$T(N)$，此时算法既简单，又高效。
定理：对于任意N个不同元素组成的序列平均具有$N(N-1)/4$个逆序对。
由上面的定理，我们可以得出：任何仅以交换相邻两元素来排序的算法，其平均时间复杂度为$\Omega(N^2)$。这意味着，如果想要提高算法的效率，就得在每次交换元素时，不止消去 1 个逆序对，这就要求每次交换的两个元素要在序列中相隔的比较远。
希尔排序
希尔排序的主要目的就是每次交换元素时，通过消去多个逆序对来达到提升算法效率。其主要思想：先定义增量序列$D_M > D_{M-1} > \dots > D_1 = 1$，然后对每个$D_k$进行“$D_k$-间隔”排序（$k=M, M-1, \dots,1$），值得注意的是，后面进行的“间隔”排序不会影响前面“间隔”排序的有序性，也即“$D_k$-间隔”有序的序列，在执行“$D_{k-1}$-间隔”排序后，仍然是“$D_k$-间隔”有序的。
原始希尔排序，增量依次减半，$D_M = \lfloor N/2 \rfloor, D_k = \lfloor D{k+1}/2 \rfloor$，此时最坏情况下的时间复杂度为$T = \Theta(N^2)$，基本代码如下：1
2
3
4
5
6
7
8
9
10
11void Shell_Sort(ElementType A[], int N) {
for(D=N/2; D>0; D/=2) {
for(P=D; P<N; P++) {
temp = A[P];
for(i=P; i>=D && A[i-D]>temp; i-=D) {
A[i] = A[i-D];
}
A[i] = temp;
}
}
}
在最坏的情况（每次进行间隔排序的序列都是有序的）下，希尔排序会退化成插入排序，原因在于增量元素不互质，则小增量可能根本不起作用。为了解决这个问题，引入了更多的增量序列：
- Hibbard增量序列，$D_k = 2^k - 1$，这样保证了相邻增量元素互质，最坏情况下$T = \Omega(N^{3/2})$，猜想$T_{avg} = O(N^{5/4})$
- Sedgewick增量序列，${1, 5, 19, 41, 109, \dots}$，也即增量序列的每一个元素是由$9 \times 4^i + 1$或$4^i - 3 \times 2^i + 1$计算得到，猜想$T_{avg} = O(N^{7/6}), T_{worst} = O(N^{4/3})$
由于希尔排序每次对增量序列进行排序，相邻的相等元素属于不同增量序列，则希尔排序可能会改变相等且相邻元素的相对位置，属于不稳定的排序。
选择排序
选择排序是一种简单直观的排序算法，基本工作原理是每一次从待排序的数据元素中选出最小（大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，重复此过程直到全部待排序的数据元素排完。
简单选择排序
简单选择排序的思路很简单，与选择排序的基本思想一致，基本代码如下：1
2
3
4
5
6
7
8void Selection_Sort(ElementType A[], int N) {
for(i=0; i<N; i++) {
//find the minimum from A[i] to A[n-1], and return to Position
MinPosition = ScanForMin(A, i, N-1);
//replace the minimum element to the last position of the ordered part
Swap(A[i], A[MinPosition]);
}
}
简单选择排序的时间复杂度主要有两个影响条件，第一个是查找最小值，第二个是交换，所以它的时间复杂度无论怎样都是$T=\Theta(N^2)$。
堆排序
分析了简单选择排序算法的时间复杂度后，发现简单选择排序的时间都耗费在了查找最小值上，如果能把这一操作变快，那么简单选择排序的效率就能提高。根据选择排序的特点，每次查找的值必须是最小（大）值，这与小（大）根堆的性质是一致的，那么使用堆来进行元素的查找，每次弹出最小（大）值，就可以提升排序效率。基本代码如下：1
2
3
4
5
6
7
8
9void Heap_Sort(ElementType A[], int N) {
BuildHeap(A);
for(i=0; i<N; i++) {
tempA[i] = DeleteMin[A];
}
for(i=0; i<N; i++) {
A[i] = tempA[i];
}
}
上述代码的过程比较简单，每次找出最小（大）元素后，保存在一个临时数组内，然后在将临时数组内的排序结果复制到原始数组中。这样即需要额外的空间（$O(N)$）去存储这部分数据，又要额外的时间去复制元素。那么如何去避免这部分开销呢？请看下面的代码：
1 | void Heap_Sort(ElementType A[], int N) { |
按照上述代码，建立一个大根堆，排序开始后，交换大根堆最大元素与最末尾元素的值，完成后，将这个最大值剔除出堆，紧接着再调整为大根堆，重复执行上述操作。
定理：堆排序处理N个不同元素的随机排列的平均比较次数是$2NlogN - O(N log logN)$
虽然堆排序给出最佳平均时间复杂度，但实际效果不如用Sedgewick增量序列的希尔排序。
归并排序
归并排序的核心就是有序子列的归并，首先，申请空间，保存合并后的有序序列，设定两个指针，最初位置分别为两个有序序列的起始位置，比较两个指针指向的元素，选择相对小的元素放到申请的空间内，并移动指针到下一位置，重复直至某一个子序列超出序列尾，接着将另一序列剩下的所有元素直接复制到申请空间的尾部。合并两个有序子列的基本代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16void Merge(ElementType A[], ElementType TempA[], int L, int R, int RightEnd) {
LeftEnd = R-1; //Suppose two subsequences are side-by-side
Tmp = L; //initial position
NumElements = RightEnd - L + 1;
while(L <= LeftEnd && R <= RightEnd) {
if(A[L] <= A[R]) TempA[Tmp++] = A[L++];
else TempA[Tmp++] = A[R++];
}
// copy the rest straightly
while(L <= LeftEnd) TempA[Tmp++] = A[L++];
while(R <= RightEnd) TempA[Tmp++] = A[R++];
//copy the result to A[] from right to left
for(i=0; i<NumElements; i++, RightEnd--) {
A[RightEnd] = TempA[RightEnd]
}
}
归并算法在实现的时候有两种不同的策略，下面先介绍递归。
递归
归并排序的递归算法的思想是基于分治法的，先将分开的子序列排好，在合并成一个大的序列。基本代码如下：1
2
3
4
5
6
7
8
9void MSort(ElementType A[], ElementType TempA[], int L, int RightEnd) {
int Center;
if(L < RightEnd) {
Center = (L + RightEnd)/2;
MSort(A, TempA, L, Center);
MSort(A, TempA, Center+1, RightEnd);
Merge(A, TempA, L, Center+1, RightEnd);
}
}
基于分治法的归并排序递归算法的时间复杂度为$T(NlogN)$，推导过程如下：
$$
\begin{align} T(N)
& = 2 T(N/2)) + cN \\
& = 2\ (2T(N/2^2) + c N/2) + cN \\
& = \dots = 2^k * O(1) + ckN \\
& = O(NlogN)
\end{align}
$$
可得$T(N) = O(NlogN)$，这个时间复杂度是很“强”的😆，也即是说在任何情况下（无论好坏）都是$NlogN$，另外，归并排序是稳定的排序算法。为了使它与上述其他排序算法的函数接口统一，再整理下代码：1
2
3
4
5
6
7
8void Merge_Sort_Recursion(ElementType A[], int N) {
ElementType *TempA;
TempA = malloc(N*sizeof(ElementType));
if(TempA != NULL) {
MSort(A, TempA, 0, N-1);
free(TempA);
} else Error("Insufficient Space.");
}
注意在上面的代码中，临时传递使用的数组是声明在Merge_Sort函数中的，这样做的好处就是避免了在MSort中重复声明和重复释放内存操作。
非递归
归并排序的非递归算法基本思想依然是分治法的思想，每次循环先归并相邻的两个子列，子列长度逐渐增加，直至最后左右两个子列之和大于序列总长度。基本代码如下：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
27
28
29
30void Merge_Sort_Non_Recursion(ElementType A[], int N) {
int length;
ElementType *TempA;
length = 1; //initialize the length of subsequence
TempA = malloc(N*sizeof(ElementType));
if(TempA != NULL) {
while(length < N) {
Merge_pass(A, TempA, N, length); //left
length *= 2;
Merge_pass(TempA, A, N, length); //right
length *= 2;
}
} else printf("Insufficient Space.\n");
}
/*Merge adjacent ordered subsequence in pairs accroding to the current
length of subsequence*/
void Merge_pass(ElementType A[], ElementType TempA[], int N, int length) {
int i, j;
for(i=0; i<=N-2*length; i+=length) {
Merge(A, TempA, i, i+length, i+2*length-1);
}
if(i+length < N) {
//Merge the last two subsequence
Merge(A, TempA, i, i+length, N-1);
} else {
//only one subsequence last
for(j=i; j<N; j++) TempA[j] = A[j];
}
}
注意上述代码中的细节，Merge_pass是一个按照序列长度进行一次归并的函数，当序列长度发生变化的时候，将再次调用此函数，另外，在此函数内，for循环内归并的序列是前N/length - 1对，而不是N/length对，如果N是奇数，最后一个子列就被单独出来了，它与其他子列的长度不等，所以针对最后一个子列的处理，要与前面区分开来。再者，上述代码中length增长的倍数是2，理论上即是二路归并。
小结
归并排序算法的优点很明显，那就是在任何情况（无论好坏）下，其时间复杂度都是$T(NlogN)$，同时，它还是稳定的排序算法，但是它有一个很明显的缺点，就是需要占用$O(N)$大小的空间，并且在内存内要频繁的进行倒换操作，所以，一般内部排序中不会使用归并排序，外部排序会使用归并排序。
Homework
09-1 排序
这个题专门用来检测自己实现的排序算法，最好把老师讲了的都实现一下。
冒泡排序
1 |
|
插入排序
1 |
|
希尔排序
1 |
|
堆排序
1 |
|
归并排序
非递归
1 |
|
递归
1 |
|
09-2 Insert or Merge
这个题形式简单，但是要想得满分，必须得对插入排序跟归并排序都很了解才行。
题目要求输出两样东西：
- 判断属于那一种排序
- 然后输出再进行下一次这种排序后所得的序列
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
int tar[maxn], arr[maxn], tmparr[maxn], n;
bool issame(int *a) {
for(int i = 0; i < n; i++) {
if(a[i] != tar[i]) return false;
}
return true;
}
void printarray(const int *array, int size) {
for(int i = 0; i < n; i++) {
printf("%d", array[i]);
if(i < n - 1) putchar(' ');
}
}
void insert_pass(int *array, int pos) {
int tmp = array[pos], j;
for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
for(int i = 1; i < n; i++) {
insert_pass(array, i);
if(issame(array)) {
*round = i + 1;
return true;
}
}
return false;
}
void merge(int *array, int *tmparr, int left, int right, int rightend) {
int leftend = right - 1, tmp = left;
int numofelements = rightend - left + 1;
while(left <= leftend && right <= rightend) {
if(array[left] < array[right]) tmparr[tmp++] = array[left++];
else tmparr[tmp++] = array[right++];
}
while(left <= leftend) tmparr[tmp++] = array[left++];
while(right <= rightend) tmparr[tmp++] = array[right++];
for(int i = 0; i < numofelements; i++, rightend--) {
array[rightend] = tmparr[rightend];
}
}
void merge_pass(int *array, int *tmparr, int n, int length) {
int i, j;
for(i = 0; i <= n - 2 * length; i += (2 * length)) {
merge(array, tmparr, i, i + length, i + 2 * length - 1);
}
if(i + length < n) merge(array, tmparr, i, i + length, n - 1);
else for(j = i; j < n; j++) tmparr[j] = array[j];
}
void merge_sort(int *array, int n) {
int *tmparr;
tmparr = (int*)malloc(n * sizeof(int));
if(tmparr != NULL) {
int length = 1;
while(length < n) {
merge_pass(array, tmparr, n, length);
length *= 2;
if(issame(tmparr)) {
merge_pass(tmparr, array, n, length);
printarray(array, n);
break;
}
merge_pass(tmparr, array, n, length);
length *= 2;
if(issame(array)) {
merge_pass(array, tmparr, n, length);
printarray(tmparr, n);
break;
}
}
free(tmparr);
} else return;
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
tmparr[i] = arr[i];
}
for(int i = 0; i < n; i++) {
scanf("%d", &tar[i]);
}
int round = 0;
if(isinsert(tmparr, n, &round)) {
printf("Insertion Sort\n");
insert_pass(tmparr, round);
printarray(tmparr, n);
} else {
for(int i = 0; i < n; i++) tmparr[i] = arr[i];
printf("Merge Sort\n");
merge_sort(tmparr, n);
}
return 0;
}
/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0
in:
10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6
out:
Merge Sort
1 2 3 8 4 5 7 9 0 6
*/
09-3 Insertion or Heap Sort
这个题与上题类型一致，只不过把归并排序换成了堆排序。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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
int tar[maxn], arr[maxn], tmparr[maxn], n;
void swap(int *p1, int *p2) {
int t = *p1;
*p1 = *p2;
*p2 = t;
}
bool issame(int *a) {
for(int i = 0; i < n; i++) {
if(a[i] != tar[i]) return false;
}
return true;
}
void printarray(const int *array, int size) {
for(int i = 0; i < n; i++) {
printf("%d", array[i]);
if(i < n - 1) putchar(' ');
}
}
void insert_pass(int *array, int pos) {
int tmp = array[pos], j;
for(j = pos; j > 0 && tmp < array[j - 1]; j--) {
array[j] = array[j - 1];
}
array[j] = tmp;
}
bool isinsert(int *array, int n, int *round) {
for(int i = 1; i < n; i++) {
insert_pass(array, i);
if(issame(array)) {
*round = i + 1;
return true;
}
}
return false;
}
void Percolatedown(int *heap, int pos, int size) {
int parent, child, tmp = heap[pos];
for(parent = pos; parent * 2 + 1 <= size - 1; parent = child) {
child = parent * 2 + 1;
if(child != size - 1 && heap[child] < heap[child + 1]) child++;
if(tmp >= heap[child]) break;
else heap[parent] = heap[child];
}
heap[parent] = tmp;
}
void heap_sort(int *array, int n) {
for(int i = n / 2 - 1; i >= 0; i--) {
Percolatedown(array, i, n);
}
int i;
for(i = n - 1; i > 0; i--) {
if(issame(array)) break;
swap(&array[0], &array[i]);
Percolatedown(array, 0, i);
}
swap(&array[0], &array[i]);
Percolatedown(array, 0, i);
printarray(array, n);
}
int main() {
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
tmparr[i] = arr[i];
}
for(int i = 0; i < n; i++) {
scanf("%d", &tar[i]);
}
int round = 0;
if(isinsert(tmparr, n, &round)) {
printf("Insertion Sort\n");
insert_pass(tmparr, round);
printarray(tmparr, n);
} else {
for(int i = 0; i < n; i++) tmparr[i] = arr[i];
printf("Heap Sort\n");
heap_sort(tmparr, n);
}
return 0;
}
/*
samples:
in:
10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0
out:
Insertion Sort
1 2 3 5 7 8 9 4 6 0
in:
10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9
out:
Heap Sort
5 4 3 1 0 2 6 7 8 9
*/
