nlog(n)排序

2018-06-17 21:58:08来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

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

快速排序:

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

归并排序:

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

堆排序:

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

标签:

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

上一篇:lintcode.44 最小子数组

下一篇:Ilya And The Tree CodeForces - 842C