0、 各种排序的比较
| 内部算法 | 时间复杂度(最好) | 时间复杂度(评价) | 时间复杂度(最坏) | 空间复杂度 | 是否稳定 | 备注 |
|---|---|---|---|---|---|---|
| 直接插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 | n<50，默认有序为佳 |
| 简单冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 是 | n<50，默认有序为佳 |
| 简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 否 | n<50，元素信息量小为佳 |
| 希尔shell排序 | O(n^1.3) | O(n^1.3) | O(n^1.3) | O(1) | 否 | |
| 快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | 否 | 适用n大，元素随机分布最佳 |
| 堆排序 | O(n*log(n)) | O(n*log(n))) | O(n*log(n)) | O(1) | 否 | 适用n大 |
| 二路归并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 是 | 适用n大 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)), O(rd) | O(r) | 是 | n大且关键字位少 |
1、 内部排序
1-1 插入型排序
1-1-1 直接插入排序
#include <stdio.h>
void insert_simple(int a[], int n){
int i, j;
for(i = 2; i <= n;i++)
if(a[i] < a[i-1]){
a[0] = a[i];
for(j = i-1; a[0] < a[j]; j--)
a[j+1] = a[j];
a[j+1] = a[0];
}
}
int main()
{
int n, data[]={-99999,4,5,2,-4,5,0,9}; // the first is sentinel.
n = sizeof(data)/sizeof(int) - 1;
insert_simple(data,n);
for(int i = 1; i <= n; i++)printf("%d ", data[i]);
return 0;
}1-1-2 折半插入排序
#include <stdio.h>
void insert_half(int a[], int n){
int i, j, low, high, mid;
for(i = 2; i <= n;i++){
a[0] = a[i];
low = 1, high = i-1;
while(low <= high){
mid = (low + high) / 2;
if(a[mid] > a[0]) high = mid - 1;
else low = mid + 1;
}
for(j = i-1; j >= high + 1; j--) a[j+1] = a[j];
a[high+1] = a[0];
}
}
int main()
{
int n, data[]={-99999,4,5,2,-4,5,0,9}; // the first is sentinel.
n = sizeof(data)/sizeof(int) - 1;
insert_half(data,n);
for(int i = 1; i <= n; i++)printf("%d ", data[i]);
return 0;
}1-1-3 希尔shell排序
1-2 交换型排序
1-2-1 简单冒泡排序
1-2-2 高级冒泡排序
1-2-3 快速排序
- 《数据结构》C语言版 严蔚敏教材的方法（交换最少）
- 《算法》第4版 Robert Sedgewick and Kevin Wayne的方法（最直观）
- 《算法导论》第3版 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein的方法
1-3 选择型排序
1-3-1 简单选择排序
1-3-2 堆排序
1-4 归并排序
1-4-2 二路归并排序
1-5 基数排序
2、 外部排序
2-1 多路归并排序
Wu_Being 博客声明：本人博客欢迎转载，请标明博客原文和原链接！谢谢！
《【数据结构8】排序》
http://blog.csdn.net/u014134180/article/details/55506271
如果你看完这篇博文，觉得对你有帮助，并且愿意付赞助费，那么我会更有动力写下去。
