#include <bits/stdc++.h> using namespace std; void Merge(int A[], int p, int q, int r){ //We need extra O(n) space here! int* L = new int[q-p+2]; int* R = new int[r-q+1]; for(int i = p; i <= q; i++) L[i-p] = A[i]; for(int i = q + 1; i <= r; i++) R[i-q-1] = A[i]; L[q-p+1] = INT_MAX; R[r-q] = INT_MAX; int i = 0, j = 0; for(int k = p; k <= r; k++){ A[k] = L[i] <= R[j]? L[i++] : R[j++]; } delete[] L; delete[] R; } void MergeSort(int A[], int p, int r){ if(p >= r) return; int q = p + (r - p)/2; MergeSort(A, p, q); MergeSort(A, q + 1, r); Merge(A, p, q, r); } int main() { int arr[] = {33,12,19,9,34,32,27,51,8,11,42,29,18,65,5,38,14}; int len = sizeof(arr)/sizeof(arr[0]); //printf("%d\n", len); MergeSort(arr, 0, len-1); for(int i = 0; i < len; i++){ printf("%d ", arr[i]); } return 0; }
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 |
冒泡 | O(n2) | O(n2) | 稳定 | O(1) |
交换 | O(n2) | O(n2) | 不稳定 | O(1) |
选择 | O(n2) | O(n2) | 不稳定 | O(1) |
插入 | O(n2) | O(n2) | 稳定 | O(1) |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) |
Shel l | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(n) |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1)
|