算法复杂度以及稳定性分析
| 算法名称 | 平均时间 | 辅助空间 | 稳定性 |
| 冒泡排序 | O(n2) | O(1) | 是 |
| 选择排序 | O(n2) | O(1) | 否 |
| 插入排序 | O(n2) | O(1) | 是 |
| 自底向上归并排序 | O(nlog2n) | O(n) | 是 |
| 自顶向下归并排序 | O(nlog2n) | O(n) | 是 |
| 快速排序 | O(nlog2n) | O(n) | 否 |
| 堆排序 | O(nlog2n) | O(1) | 否 |
| 基数排序 | O(dn) | O(rn) | 是 |
| 希尔排序 | \ | O(1) | 否 |
排序的时间效率比较
下图表名了各种算法在不同数据规模下，完成排序所消耗的时间（毫秒为单位），从表中可以显然看出O(n2)的排序算法比O(nlog2n)的算 法 时间多出几百上千倍，而且随着数据数据规模增大时间比也会随着增大；因为排序的数据采用随机数，顺序将被打乱，快速排序算法优于其他排序算法！
| 算法名称 | 1万 | 2万 | 3万 | 4万 | 5万 | 6万 | 7万 | 8万 | 9万 | 10万 |
| 冒泡排序 | 1442 | 5497 | 12206 | 21861 | 34017 | 49148 | 67394 | 88880 | 111939 | 139071 |
| 选择排序 | 199 | 816 | 1790 | 3254 | 5062 | 7166 | 9645 | 12636 | 16102 | 19643 |
| 插入排序 | 178 | 717 | 1628 | 2882 | 4458 | 6446 | 8822 | 11649 | 14547 | 17914 |
| 自底向上归并排序 | 3 | 6 | 9 | 12 | 15 | 18 | 22 | 26 | 28 | 33 |
| 自顶向下归并排序 | 3 | 7 | 11 | 15 | 18 | 23 | 27 | 31 | 36 | 40 |
| 快速排序 | 2 | 5 | 8 | 11 | 14 | 18 | 21 | 25 | 29 | 32 |
| 堆排序 | 3 | 7 | 12 | 16 | 19 | 23 | 26 | 30 | 34 | 37 |
| 基数排序 | 9 | 21 | 30 | 40 | 49 | 59 | 66 | 75 | 90 | 98 |
| 希尔排序 | 3 | 8 | 11 | 15 | 24 | 24 | 29 | 35 | 40 | 41 |
下面是C代码
#include <stdio.h>
#include <stdlib.h> #define LENGTH(s) (sizeof(s)/sizeof(int))
#define SWAP(x,y) {long t; t=x; x=y; y=t;} //冒泡排序
void BubbleSort(int **p,int len){
int i,j; for(i=0;i<len;i++){//外层控制循环次数
for(j=0;j<len-i;j++){//控制交换次数
if((*p)[j]>(*p)[j+1]){
SWAP((*p)[j],(*p)[j+1]);
}
}
}
} //选择排序
void SelectSort(int **p,int len){
int i,j,k; for(i=0;i<len;i++){
k=i;
for(j=i+1;j<len;j++){
if((*p)[k]>(*p)[j]){
k=j;
}
}
if(k!=i){
SWAP((*p)[k],(*p)[i]);
}
} } //插入排序
void InsertSort(int **p,int len){
int i,j,k; for(i=1;i<len;i++){
k=(*p)[i];
for(j=i-1;j>=0;j--){
if((*p)[j]>k){
(*p)[j+1]=(*p)[j];
}else{
break;
}
}
(*p)[j+1]=k;
}
} //快速排序
void QuickSort(int **p,int min,int max){
int i,j,k;
if(min<max){
i=min;j=max;k=(*p)[i];
while(i<j){
while(i<j && (*p)[j]>k)
j--;
if(i<j)
(*p)[i++]=(*p)[j]; while(i<j && (*p)[i]<k)
i++;
if(i<j)
(*p)[j--]=(*p)[i];
}
(*p)[i]=k;
QuickSort(p,min,i-1);
QuickSort(p,i+1,max);
}
} void main(){
int arr[]={1233,22,38,99,90,1,23,45,394,2,384,45,100,-10,22};
int i,*p=arr;
int len=LENGTH(arr);
//BubbleSort(&p,len);
//SelectSort(&p,len);
//InsertSort(&p,len);
QuickSort(&p,0,len);
for(i=0;i<len;i++){
printf("%d\n",arr[i]);
}
}