nlog(n)排序

总结了下各种nlog(n)排序。

以下是代码(c和c++混搭的感觉总是让人很舒服~):

快速排序：

1. #include <iostream>
2. using namespace std;
4. void quick_sort(int *a, int left, int right) {
5.     if(left >= right) return;
6.     int p = left + 1;
7.     for(int i = left + 1; i <= right; i++) {
8.         if(a[i] <= a[left]) {
9.              swap(a[p], a[i]);
10.              p++;
11.         }
12.     }
13.      swap(a[left], a[p - 1]);
14.      quick_sort(a, left, p - 2);
15.      quick_sort(a, p, right);
16. }
18. int main() {
19.     int a[10];
20.     for(int i = 0; i < 10; i++) a[i] = rand() % 100;
21.     for(int i = 0; i < 10; i++) cout << a[i] << ' ';
22.     cout << endl;
23.      quick_sort(a, 0, 9);
24.     for(int i = 0; i < 10; i++) cout << a[i] << ' ';
25.     cout << endl;
26.     return 0;
27. }

归并排序：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
4. #define MAXN 0x7fffffff
6. void merge_sort(int *a, int left, int right) {
7.      if(left == right) return;
8.      int mid = (left + right) / 2;
9.       merge_sort(a, left, mid);
10.       merge_sort(a, mid + 1, right);
11.      int *L, *R, *b;
12.       L = new int[mid - left + 2];
13.       R = new int[right - mid + 1];
14.       b = new int[right - left + 1];
15.      for(int i = left; i <= mid; i++) L[i - left] = a[i];
16.       L[mid - left + 1] = MAXN;
17.      for(int i = mid + 1; i <= right; i++) R[i - mid - 1] = a[i];
18.       R[right - mid] = MAXN;
19.      int p1 = 0, p2 = 0, k = 0;
20.      while(p1 < mid - left + 1 || p2 < right - mid) {
21.          if(L[p1] <= R[p2]) {
22.               b[k++] = L[p1];
23.               p1++;
24.          }
25.          else {
26.               b[k++] = R[p2];
27.               p2++;
28.          }
29.      }
30.      for(int i = 0; i < k; i++) a[left + i] = b[i];
31.      delete L;
32.      delete R;
33.      delete b;
34. }
36. int main() {
37.     int a[10];
38.     for(int i = 0; i < 10; i++) a[i] = rand() % 100;
39.     for(int i = 0; i < 10; i++) cout << a[i] << ' ';
40.     cout << endl;
41.      merge_sort(a, 0, 9);
42.     for(int i = 0; i < 10; i++) cout << a[i] << ' ';
43.     cout << endl;
44.     return 0;
45. }

堆排序：

1. #include <iostream>
2. #include <algorithm>
3. using namespace std;
5. void max_heapify(int *a, int p, int n) {
6.     int left = 2 * p + 1, right = 2 * p + 2, largest = p;
7.     if(left < n) {
8.         if(a[left] > a[largest]) largest = left;
9.         if(right < n) {
10.             if(a[right] > a[largest]) largest = right;
11.         }
12.         if(largest != p) {
13.              swap(a[largest], a[p]);
14.              max_heapify(a, largest, n);
15.         }
16.     }
17. }
19. void heap_sort(int *a, int n) {
20.     for(int i = (n - 2) / 2; i >= 0; i--) max_heapify(a, i, n);
21.     int t = n;
22.     for(int i = 1; i < n; i++) {
23.          swap(a[0], a[t - 1]);
24.          t--;
25.          max_heapify(a, 0, t);
26.     }
27. }
29. int main() {
30. #define N 10
31.     int a[N];
32.     for(int i = 0; i < N; i++) a[i] = rand() % 100;
33.     for(int i = 0; i < N; i++) cout << a[i] << ' ';
34.     cout << endl;
35.      heap_sort(a, N);
36.     for(int i = 0; i < N; i++) cout << a[i] << ' ';
37.     cout << endl;
38.     return 0;
39. }

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有