计算机随机生成10000个数，让算法排序。花费时间如下：
代码：
// KindsOfSort.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <cstdlib> #include <ctime> using namespace std; #define N 10000 //插入排序 稳定的排序算法 时间复杂度O（n^2） void insert_sort(int *a,int len) { int i,j; int temp; for (int i=1;i<len;i++) { temp=a[i]; //暂存的目的是为了后移时a[i]数据不会被a[i-1]填充掉 for (j=i-1;j>=0&&temp<a[j];j--) //从数组的后部开始比较 { a[j+1]=a[j]; //后移数组元素 for循环保证是依次后移 } a[j+1]=temp; //之所以是j+1，是因为for循环的特性决定 i--总是在下一次循环时生效 } } //希尔排序 不稳定的排序算法 void shell_sort(int *a,int len) { int i,j,h; //表示分组 int temp; for (h=len/2;h>0;h=h/2) //初始时取后半段数组排序 { for (i=h;i<len;i++) //这里其实就是直接插入排序的代码 只不过步长不是1 而是h 即把原来直接插入排序代码中的1全部换成h { temp=a[i]; for (j=i-h;j>=0&&temp<a[j];j-=h) { a[j+h]=a[j]; } a[j+h]=temp; } } } //冒泡排序 void bubble_sort(int *a,int len) { int temp; int i,j; for (i=0;i<len-1;i++) { for (j=0;j<len-i-1;j++) //循环的目的就是为了把大的元素王素组尾部放 { if (a[j+1]<a[j]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } } //改进的冒泡排序 void bubble_sort2(int *a,int len) { int temp; int i,j; int is_exchange; for (i=0;i<len-1;i++) { is_exchange=0; for (j=0;j<len-i-1;j++) { if (a[j+1]<a[j]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; is_exchange=1; } } if (is_exchange!=1) return; } } //快速排序 //快拍参考网址http://developer.51cto.com/art/201403/430986.htm //写的相当通俗易懂 尤其是那几张图片 void quick_sort(int *a,int low,int high) { int i,j,pivot; int temp; if (low<high) //递归结束条件 { pivot=a[low];//一般 基准值取数列的第一个元素值 i=low;j=high; //while()循环的目的是为了找到基准值应该放在数列中的哪个位置 //使得基准值放在这里后 它左边的都比他小 右边的都比它大 while(i<j) { while(i<j&&a[j]>=pivot) //从数列的末端寻找一个比基准值小的数 j--; while(i<j&&a[i]<=pivot) //从数列的始端寻找一个比基准值大的数 i++; if (i<j) { temp=a[i]; //交换上述两个讯混找到的两个元素 a[i]=a[j]; a[j]=temp; } } a[low]=a[i]; a[i]=pivot;//将基准值放入找到的位置中 quick_sort(a,low,i-1); //递归处理基准值左边的子数组 quick_sort(a,i+1,high); //递归处理基准值右边的子数组 } } //直接选择排序 //算法思想：从未排序数组中选出最小的 放到数组前端 循环执行 void select_sort(int *a,int len) { int i,j,temp,index; int min; for (i=0;i<len;i++) { temp=a[i]; min=a[i]; for (j=i+1;j<len;j++) { if (a[j]<min) { min=a[j]; index=j; } } a[i]=min; a[index]=temp; } } //堆排序 //交换两个数 void swap_2num(int &a,int &b) //使用a和b的引用 { a=a^b; b=a^b; a=a^b; } //调整堆 使其满足最大堆性质 //index表示堆顶元素下标 //创建大顶堆 void heap_adjust(int a[],int index,int size) { int max=index; //最大值的下标 先假设最大值为堆顶元素 int left=(index<<1)+1; //左子节点下标 int right=left+1; //右子节点下标 if(index<=size/2) //如果index是叶子节点就不用进行调整 { if (left<=size&&a[index]<a[left]) max=left; if (right<=size&&a[index]<a[right]&&a[right]>a[left]) max=right; if (max!=index) { swap_2num(a[max],a[index]); heap_adjust(a,max,size); } } } //建堆 //自底向上建立堆 大顶堆 void build_heap(int a[],int size) { int index; for (index=size>>1;index>=0;index--) heap_adjust(a,index,size); } // void heap_sort(int a[],int heapsize) { int index; build_heap(a,heapsize-1); //自底向上建立堆 for (index=heapsize-1;index>=1;index--) { swap_2num(a[0],a[index]); //heapsize--; heap_adjust(a,0,index-1); } } //归并排序 合并 void merge(int *a,int low,int high) { int mid=(low+high)>>1; int R[N]; int i=low; int j=mid+1; int k=low; for (;i<=mid&&j<=high;k++) { if (a[i]<=a[j]) //比较两端的元素值 把较小的放入临时数组 { R[k]=a[i++]; } else R[k]=a[j++]; } //拷贝剩下的数组 while(i<=mid) //左边没拷贝完 { R[k++]=a[i++]; } while(j<=high) //右边没拷贝完 { R[k++]=a[j++]; } for (i=low;i<=high;i++) //注意i的起始值 { a[i]=R[i]; } } //归并排序 void merge_sort(int *a,int low,int high) { if (low>=high) { return; } int mid=(low+high)>>1; merge_sort(a,low,mid); merge_sort(a,mid+1,high); merge(a,low,high); } //打印输出数组 void display(int *a,int len) { for (int i=0;i<len;i++) { cout<<a[i]<<" "; } cout<<endl; } int _tmain(int argc, _TCHAR* argv[]) { /*int a[6]={12,32,1,6,126,21}; //int b=sizeof(a)/sizeof(int); 可使用该方法求数组长度 //shell_sort(a,5); //bubble_sort2(a,5); //select_sort(a,5); display(a,6); cout<<endl; heap_sort(a,6); display(a,6);*/ srand((unsigned)time(NULL)); int min=0; int max=N; int a[N]; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } //cout<<endl; int start_time=clock(); insert_sort(a,N); cout<<"直接插入排序花费时间："<<clock()-start_time<<"毫秒"<<endl; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); shell_sort(a,N); cout<<"希尔排序花费时间："<<clock()-start_time<<"毫秒"<<endl; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); bubble_sort(a,N); cout<<"冒泡排序花费时间："<<clock()-start_time<<"毫秒"<<endl; /*for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); bubble_sort2(a,N); cout<<"改进后的冒泡排序花费时间："<<clock()-start_time<<"毫秒"<<endl;*/ for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); quick_sort(a,0,N-1); cout<<"快速排序花费时间："<<clock()-start_time<<"毫秒"<<endl; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); select_sort(a,N); cout<<"选择排序花费时间："<<clock()-start_time<<"毫秒"<<endl; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); merge_sort(a,0,N-1); cout<<"归并排序花费时间："<<clock()-start_time<<"毫秒"<<endl; for (int i=0;i<N;i++) { a[i]=rand()%(max-min+1)+min; //cout<<a[i]<<" "; } start_time=clock(); heap_sort(a,N); cout<<"堆排序花费时间："<<clock()-start_time<<"毫秒"<<endl; return 0; }
说明：源码中归并排序空间复杂度应该是O（N），而不是O（1）.