总结了下各种nlog(n)排序。
以下是代码(c和c++混搭的感觉总是让人很舒服~):
快速排序:
- #include <iostream>
- using namespace std;
- void quick_sort(int *a, int left, int right) {
- if(left >= right) return;
- int p = left + 1;
- for(int i = left + 1; i <= right; i++) {
- if(a[i] <= a[left]) {
- swap(a[p], a[i]);
- p++;
- }
- }
- swap(a[left], a[p - 1]);
- quick_sort(a, left, p - 2);
- quick_sort(a, p, right);
- }
- int main() {
- int a[10];
- for(int i = 0; i < 10; i++) a[i] = rand() % 100;
- for(int i = 0; i < 10; i++) cout << a[i] << ' ';
- cout << endl;
- quick_sort(a, 0, 9);
- for(int i = 0; i < 10; i++) cout << a[i] << ' ';
- cout << endl;
- return 0;
- }
归并排序:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- #define MAXN 0x7fffffff
- void merge_sort(int *a, int left, int right) {
- if(left == right) return;
- int mid = (left + right) / 2;
- merge_sort(a, left, mid);
- merge_sort(a, mid + 1, right);
- int *L, *R, *b;
- L = new int[mid - left + 2];
- R = new int[right - mid + 1];
- b = new int[right - left + 1];
- for(int i = left; i <= mid; i++) L[i - left] = a[i];
- L[mid - left + 1] = MAXN;
- for(int i = mid + 1; i <= right; i++) R[i - mid - 1] = a[i];
- R[right - mid] = MAXN;
- int p1 = 0, p2 = 0, k = 0;
- while(p1 < mid - left + 1 || p2 < right - mid) {
- if(L[p1] <= R[p2]) {
- b[k++] = L[p1];
- p1++;
- }
- else {
- b[k++] = R[p2];
- p2++;
- }
- }
- for(int i = 0; i < k; i++) a[left + i] = b[i];
- delete L;
- delete R;
- delete b;
- }
- int main() {
- int a[10];
- for(int i = 0; i < 10; i++) a[i] = rand() % 100;
- for(int i = 0; i < 10; i++) cout << a[i] << ' ';
- cout << endl;
- merge_sort(a, 0, 9);
- for(int i = 0; i < 10; i++) cout << a[i] << ' ';
- cout << endl;
- return 0;
- }
堆排序:
- #include <iostream>
- #include <algorithm>
- using namespace std;
- void max_heapify(int *a, int p, int n) {
- int left = 2 * p + 1, right = 2 * p + 2, largest = p;
- if(left < n) {
- if(a[left] > a[largest]) largest = left;
- if(right < n) {
- if(a[right] > a[largest]) largest = right;
- }
- if(largest != p) {
- swap(a[largest], a[p]);
- max_heapify(a, largest, n);
- }
- }
- }
- void heap_sort(int *a, int n) {
- for(int i = (n - 2) / 2; i >= 0; i--) max_heapify(a, i, n);
- int t = n;
- for(int i = 1; i < n; i++) {
- swap(a[0], a[t - 1]);
- t--;
- max_heapify(a, 0, t);
- }
- }
- int main() {
- #define N 10
- int a[N];
- for(int i = 0; i < N; i++) a[i] = rand() % 100;
- for(int i = 0; i < N; i++) cout << a[i] << ' ';
- cout << endl;
- heap_sort(a, N);
- for(int i = 0; i < N; i++) cout << a[i] << ' ';
- cout << endl;
- return 0;
- }
内容来源于网络如有侵权请私信删除
- 还没有人评论,欢迎说说您的想法!