首页 > 代码库 > 《算法导论》(CLRS)第三版 第1、2章总结(二)
《算法导论》(CLRS)第三版 第1、2章总结(二)
5. 归并排序 (Merge Sort)
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 void print(int arr[], int n) { 5 int i; 6 for (i = 0; i < n; i++) { 7 printf("%d ", arr[i]); 8 } 9 printf("\n");10 }11 12 void merge(int arr[], int s, int n) {13 int* L = (int*)malloc(s * sizeof(int));14 int* R = (int*)malloc((n-s) * sizeof(int));15 int i, j, k, t = n - s;16 for (i = 0; i < s; i++) {17 L[i] = arr[i];18 }19 for (j = 0; i < n; i++, j++) {20 R[j] = arr[i];21 }22 i = j = k = 0;23 while (i < s && j < t) {24 if (L[i] <= R[j]) {25 arr[k++] = L[i++];26 } else {27 arr[k++] = R[j++];28 }29 }30 while (i < s) {31 arr[k++] = L[i++];32 }33 while (j < t) {34 arr[k++] = R[j++];35 }36 free(L), free(R);37 }38 39 void merge_sort(int arr[], int n) {40 if (n > 1) {41 int s = n / 2, t = (n+1) / 2;42 merge_sort(arr, s);43 merge_sort(arr+s, t);44 merge(arr, s, n); // [0, s) & [s, n)45 }46 }47 48 int main() {49 int arr[10] = {1, 4, 2, 8, 5, 7, 9, 3, 0, 6};50 int n = 10;51 merge_sort(arr, n);52 print(arr, n);53 return 0;54 }
上面程序中，merge_sort 的时间复杂度为 O(nlgn), 空间复杂度为 O(nlgn)。
下面给出一种原地归并排序的C语言代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 void print(int arr[], int n) { 5 int i; 6 for (i = 0; i < n; i++) { 7 printf("%d ", arr[i]); 8 } 9 printf("\n");10 }11 12 void reverse(int arr[], int n) {13 int i = 0, j = n-1;14 while (i < j) {15 int t = arr[i];16 arr[i] = arr[j];17 arr[j] = t;18 i++, j--;19 }20 }21 22 void rotate(int arr[], int n, int k) {23 reverse(arr, n-k);24 reverse(arr+n-k, k);25 reverse(arr, n);26 }27 28 void merge(int arr[], int s, int n) {29 int i = 0, j = s, k = s;30 while (j < n) {31 while (i < j && arr[i] <= arr[j]) i++;32 if (i == j) break;33 while (j < n && arr[j] < arr[i]) j++;34 rotate(arr+i, j-i, j-k);35 i += j-k, k = j;36 }37 }38 39 void merge_sort(int arr[], int n) {40 if (n > 1) {41 int s = n / 2, t = (n+1) / 2;42 merge_sort(arr, s);43 merge_sort(arr+s, t);44 merge(arr, s, n); // [0, s) & [s, n)45 }46 }47 48 int main() {49 int arr[10] = {1, 4, 2, 8, 5, 7, 9, 3, 0, 6};50 int n = 10;51 merge_sort(arr, n);52 print(arr, n);53 return 0;54 }
6. 冒泡排序 (Bubble Sort)
1 void bubble_sort(int arr[], int n) { 2 int i, j; 3 for (i = 0; i < n; i++) { 4 for (j = n-1; j > i; j--) { 5 if (arr[j] < arr[j-1]) { 6 int tmp = arr[j]; 7 arr[j] = arr[j-1]; 8 arr[j-1] = tmp; 9 }10 }11 }12 }
对其做一点小的优化，使得最好情况下时间复杂度为 O(n)，平均情况下执行时间有所减少，但是不会改变平均情况和最坏情况下渐近复杂度的上界 O(n^2)。
1 void bubble_sort(int arr[], int n) { 2 int i, j; 3 for (i = 0; i < n; i++) { 4 int flag = 0; 5 for (j = n-1; j > i; j--) { 6 if (arr[j] < arr[j-1]) { 7 int tmp = arr[j]; 8 arr[j] = arr[j-1]; 9 arr[j-1] = tmp;10 flag = 1;11 }12 }13 if (flag == 0) break;14 }15 }
7. 选择排序 (Selection Sort)
1 void what_sort(int arr[], int n) { 2 int i, j; 3 for (i = 0; i < n; i++) { 4 for (j = i+1; j < n; j++) { 5 if (arr[i] > arr[j]) { 6 int tmp = arr[i]; 7 arr[i] = arr[j]; 8 arr[j] = tmp; 9 }10 }11 }12 }13 14 void selection_sort(int arr[], int n) {15 int i, j;16 for (i = 0; i < n; i++) {17 int mini = i, tmp = arr[i];18 for(j = i+1; j < n; j++) {19 if (arr[j] < arr[mini]) {20 mini = j;21 }22 }23 arr[i] = arr[mini];24 arr[mini] = tmp;25 }26 }
what_sort 其实也是一种选择排序，但是它在性能上比 selection_sort 差一些。
8. 逆序对 (Inversions)
在一个序列 A[0 .. n-1] 中，对任意 i, j, 若 i < j 且 A[i] > A[j], 那么 A[i] 和 A[j] 构成一个逆序对。
求序列的逆序对数的最简单的方法就是枚举，时间复杂度为 O(n^2)。
1 int count_inversions(int arr[], int n) { 2 int inversions = 0; 3 int i, j; 4 for (i = 0; i < n; i++) { 5 for (j = i+1; j < n; j++) { 6 if (arr[i] > arr[j]) inversions++; 7 } 8 } 9 return inversions;10 }
在合并排序的基础上做一些修改，我们能得到一个时间复杂度为O(nlgn)的算法：
1 void reverse(int arr[], int n) { 2 int i = 0, j = n-1; 3 while (i < j) { 4 int t = arr[i]; 5 arr[i] = arr[j]; 6 arr[j] = t; 7 i++, j--; 8 } 9 }10 11 void rotate(int arr[], int n, int k) {12 reverse(arr, n-k);13 reverse(arr+n-k, k);14 reverse(arr, n);15 }16 17 int merge(int arr[], int s, int n) {18 int inversions = 0;19 int i = 0, j = s, k = s;20 while (j < n) {21 while (i < j && arr[i] <= arr[j]) i++;22 if (i == j) break;23 while (j < n && arr[j] < arr[i]) j++;24 rotate(arr+i, j-i, j-k);25 inversions += (j-k) * (k-i);26 i += j-k, k = j;27 }28 return inversions;29 }30 31 int count_inversions(int arr[], int n) {32 int inversions = 0;33 if (n > 1) {34 int s = n / 2, t = (n + 1) / 2;35 inversions += count_inversions(arr, s);36 inversions += count_inversions(arr+s, t);37 inversions += merge(arr, s, n);38 }39 return inversions;40 }
* 最后，顺便提一下，本文所介绍的三种排序算法都是稳定的。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。