排序方法总结
排序方法总结 排序方法 时间复杂度（平均） 时间复杂度（最好） 时间复杂度（最坏） 空间复杂度 稳定性 冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定 插入排序 O(n^2) O(n) O(n^2) O(1) 稳定 快速排序 O(nlogn) O(nlogn) O(n^2) O(nlogn) 不稳定 归并排序 O(nlogn) O(nlogn) O(nlogn) O(n^2) 稳定 堆排序 O(nlogn) O(nlogn) O(nlogn) O(1) 不稳定 冒泡排序 依次比较相邻元素，并把大数向后交换，比完一轮后最大的数换到了最后。
重复以上步骤，将第二大的元素放到倒数第二位…
插入排序 对于未排序元素，在已排序序列中从后向前扫描，找到相应位置并插入。
void merger_sort(Type A[], int left, int right) { if(left < right) { int middle = (left+right)/2; merger_sort(A, left, middle); merger_sort(A, middle, right); merge(A, B, left, middle, right);//合并到数组B copy(A, B, left, right);//复制回数组A } } void merge(Type A[], Type B, int left, int middle, int right) { int i = left, j = middle+1, k=1; while((i < middle) && (j <= right)) { if(c[i] <= c[j]) d[k++] = c[i++]; else d[k++] = c[j++]; } if(i > middle) { for(int q = j; q < m; q++) d[k++] = c[q]; } else { for(int q = i; q <= m; q++) d[k++] = c[q]; } } 快速排序 从数列中挑一个元素，作为“基准”(pivot)。
