话不多说，上代码
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <random> #include <string.h> #define N 10000500 long long beg; int cnt,n; void show_time(){ long long now = clock(); printf("Case #%d:%12.1f ms ",++cnt,1.0*(now - beg)/CLK_TCK*1000); } void swap(int *a,int *b){ *a^=*b; *b^=*a; *a^=*b; } ///称这两个函数为比较函数，函数名即相当于指针，将其写入排序算法中，实现代码复用 char Ascending(int a,int b){ return a<b;} char Descending(int a,int b){ return a>b;}//没有bool我也很无奈 /** * @param s:开始指针 e：结束指针 * @param cmp 指向函数的指针 * @note 快速排序:平均时间复杂度 O(n*ln(n)) 最坏情况(倒序)O(n^2) */ void quick_sort(int *s,int *e,char (*cmp)(int ,int )){///对于左闭右开的区间中的数据(int)进行排序 ///中心思想:递归，分治求解 int *i = s,*j = e-1; if(i>j)return; int key = *i;///选择开始位置为"标记值" while (i!=j){ while(!cmp(*j,key)&&i<j)j--;///从后往前 *j 不小于 key 说明从j开始后面的元素都>=key，否则结束循环 while(!cmp(key,*i)&&i<j)i++;///与上同理 if(i<j){ ///到这里我们找到了位置不对的一组元素 swap(i,j); } } *s = *i;///把key放到适当的位置，这时满足key左边的元素均不大于（小于）key，右边元素均不小于（大于）key *i = key; quick_sort(s,i,cmp);///对key左，右侧进行同样 quick_sort(i+1,e,cmp); } /** * @param s:开始指针 e：结束指针 k：临时储存 * @param cmp 指向函数的指针 * @note 归并排序:时间复杂度 O(n*ln(n)) * @note 相较快速排序更加稳定 * @note 可以通过修改程序在 O(n*ln(n))时间内找出数据的逆序数(传统需要O(n^2)) */ void merge(int *s,int *e,char (*cmp)(int,int),int *k){ int *ori_beg = s; int *copy = k; int *mid = (e-s)/2+s;///将mid左右两侧的元素在线性时间内合并为有序的，要求:左右两侧区间内均有序 int *i = s,*j = mid+1; while (i<=mid&&j<=e){ if(cmp(*i,*j)){ *k=*i; ++i,++k; } else { *k = *j; ++k,++j; } } while(i<=mid){*k=*i,++i,++k;} while (j<=e){*k=*j,++j,++k;} while (ori_beg<=e){*ori_beg=*copy,++copy,++ori_beg;} } void merge_sort(int *s,int *e,char (*cmp)(int ,int),int *store){ if(s>=e)return; int *mid = (e-s)/2+s; merge_sort(s,mid,cmp,store); merge_sort(mid+1,e,cmp,store); merge(s,e,cmp,store);///经过上面的操作我们假设左右两边都已经排序完毕，然后进行归并操作 } void stable_sort(int *s,int *e,char (*cmp)(int ,int)){ ///中心思想:分治递归 int *tmp = (int *)malloc((e-s)* sizeof(int));///申请额外的空间用来支持排序 merge_sort(s,e-1,cmp,tmp);///左右均为闭区间，这里有讲究 free(tmp); } /** * @note 参考了 CSDN * @note 幂增长复杂度 中等数据规模有较好的表现 */ void shell_sort(int *s,int *e,char (*cmp)(int ,int)){ ///和插入排序放在一起理解，我们发现插入排序一次只移动一个单位，所以就更改移动的步长，慢慢减小以达到减少时间开销的目的 int dis_seq = 1,tmp; int maxs = (e - s)/3; int i,*j,*k; while(dis_seq<maxs){ dis_seq = dis_seq*3+1;///计算增量区间，有特别的讲究，要求元素非质 } maxs = e-s; while(dis_seq>0){///最后一个递增步长是1，否则很大概率排序不会成功 for(i = dis_seq ; i < maxs ; ++i){ tmp = *(s+i); j = s+i; k = s+dis_seq-1; while(j>k&&!cmp(*(j-dis_seq),tmp)){ *j = *(j-dis_seq);///将*j(tmp)插入到合适位置 j-=dis_seq; } *j = tmp; } dis_seq = (dis_seq-1)/3; } } void bubble_sort(int *s,int *e, char (*cmp)(int,int)){ int *i,*j = e-1;///不过多解释，较传统冒泡有两个特别的优化 int *last = e; char not_order; do{ not_order = 0;/// First optimize ,we don't need to sort if it is ordered. for(i = s ; i < j ; ++i){ if(cmp(*(1+i),*i)){ swap(i,i+1); not_order = 1; last = i; } } j = last;/// Second optimize ,we don't need to sort if the past sequence are order. }while (not_order); } void selection_sort(int *s,int *e,char (*cmp)(int ,int)){ int *i,*j,*mark;///正常思维下的排序 int key; for(i = s ; i<e ; ++i){ key = *i; mark = i; for(j = i+1 ; j < e ; ++j){ if(cmp(*j,key)) { key = *j; mark = j; } } if(key!=*i)swap(i,mark); } } void insertion_sort(int *s,int *e,char (*cmp)(int,int)){ int *i,*j,key;///和希尔(shell)排序一样 for(i = s+1 ; i!=e ; ++i){ j = i; key = *i; while (j>s&&!cmp(*(j-1),key)){ *j = *(j-1); j--; } *j = key; } } ///打印信息 void show(int *a,int *b){ while (a!=b){ printf("%d ",*a); ++a; } } int num[N]; int ori[N]; void init(int n){ memcpy(num,ori,n* sizeof(int)); beg = clock(); } int main(){ srand(time(NULL)); while (scanf("%d",&n),n){ for(int i = 0 ; i < n ; ++i){ ori[i] = rand()%n+1; } cnt = 0; init(n); quick_sort(num,num+n,Ascending); show_time(); init(n); stable_sort(num,num+n,Ascending); show_time(); init(n); shell_sort(num,num+n,Ascending); show_time(); init(n); insertion_sort(num,num+n,Ascending); show_time(); init(n); selection_sort(num,num+n,Ascending); show_time(); init(n); bubble_sort(num,num+n,Ascending); show_time(); } } /** * n(ln(n)) * 1 快速排序 * 2 归并排序 * 介于线性和二次方之间 * 3 希尔排序 * 二次方复杂度 * 4 插入排序 * 5 选择排序 * 5 冒泡排序 */ /***************** TEST one: 1000000 Case #1: 187.0 ms Case #2: 188.0 ms Case #3: 391.0 ms TEST two: 10000000 Case #1: 4172.0 ms Case #2: 2136.0 ms Case #3: 11986.0 ms TEST three: 10000 Case #1: 0.0 ms Case #2: 0.0 ms Case #3: 0.0 ms Case #4: 62.0 ms Case #5: 109.0 ms Case #6: 344.0 ms TEST four: 100000 Case #1: 15.0 ms Case #2: 15.0 ms Case #3: 32.0 ms Case #4: 6938.0 ms Case #5: 10611.0 ms Case #6: 35866.0 ms *****************/