单位建网站的详细步骤,搬瓦工装WordPress,中国新闻,查询公司信息去哪里查迄今为止的排序算法总结 7.10 迄今为止的排序算法总结复杂度和稳定性时间复杂度测试程序sortAlgorithm.hsortAlgorithm.cpptest.cpp 时间复杂度测试结果 7.10 迄今为止的排序算法总结
复杂度和稳定性
排序算法平均情况最好情况最坏情况稳定性空间复杂度选择排序O(n^2)O(n^2)O… 迄今为止的排序算法总结 7.10 迄今为止的排序算法总结复杂度和稳定性时间复杂度测试程序sortAlgorithm.hsortAlgorithm.cpptest.cpp 时间复杂度测试结果 7.10 迄今为止的排序算法总结
复杂度和稳定性
排序算法平均情况最好情况最坏情况稳定性空间复杂度选择排序O(n^2)O(n^2)O(n^2)不稳定有的书或资料说稳定以自己的资料为准O(1)堆排序O(nlogn)O(nlogn)O(nlogn)不稳定O(1)新开辟堆来处理数据的堆排序为O(n)直接插入排序O(n^2)O(n)O(n^2)稳定O(1)希尔排序O(nlogn)~O(n^{2})O(n^{1.3})O(n^{2})不稳定O(1)冒泡排序O(n^2)这里的所有排序算法里效率最差的O(n)O(n^2)这里的所有排序算法里效率最差的稳定O(1)快速排序O(nlogn)O(nlogn)O(n^2)不稳定O(logn)~O(n)归并排序O(nlogn)O(nlogn)O(nlogn)稳定主要取决于比较规则若是数据大小则要用或O(n)计数排序O(nRange)理论上所有排序算法中最快的但局限性非常大O(nRange)理论上所有排序算法中最快的但局限性非常大O(nRange)理论上所有排序算法中最快的但局限性非常大稳定O(Range)取决于数据中的极端值
时间复杂度测试程序
这是一套用于测试在10个数据到100000个数据的情况下不同排序算法包括他们的优化版本、未优化版本的用时的c代码。计时用的是chrono库的高精度计时输出的单位是秒。
sortAlgorithm.h
#pragma once#includestdio.h
#includestdlib.h
#includetime.h
#includestdlib.h
#includestdbool.h
#includestring.htypedef int Datatype;//直接选择排序
void selectSort(Datatype a[], int n);//经优化的选择排序每次同时选出最小的和最大的
void selectSortplus(Datatype* a, int n);//堆排序
void heapSort(Datatype* a, int n);//拷贝方式的堆排序
void heapSortCopy(Datatype* a, int n);//直接插入排序未优化
void insertSort(Datatype* a, int n);//直接插入排序小优化
void insertSortPlus(Datatype* a, int n);//希尔排序gapgap/2
void shellSort(Datatype* a, int n);//希尔排序gapgap/31
void shellSort2(Datatype* a, int n);//冒泡排序因为性能实在太差只上优化版本
void bubbleSort(Datatype* a, int n);//快速排序hoare版本
void quickSortHoare(Datatype* a, int left, int right);//快速排序挖坑法
void quickSortHole(Datatype* a, int left, int right);//快速排序前后指针
void quickSortDPoint(Datatype* a, int left, int right);//快速排序三路划分优化
void quickSortTRoute(int* a, int begin, int end);//快排的非递归实现Hoare版本
void quickSortNonRHoare(Datatype* a, int left, int right);//快排的非递归实现挖坑法
void quickSortNonRHole(Datatype* a, int left, int right);//快排的非递归实现前后指针
void quickSortNonRDPoint(Datatype* a, int left, int right);//归并排序无小区间优化
void mergeSort(Datatype* a, int n);//归并排序小区间优化
void mergeSortPlus(Datatype* a, int n);//归并排序非递归
void mergeSortNonR(Datatype* a, int n);//计数排序
void countSort(Datatype* a, int n);sortAlgorithm.cpp
#define _CRT_SECURE_NO_WARNINGS 1#includesortAlgorithm.h//交换函数
void Swap(Datatype* a, Datatype* b) {Datatype t *a;*a *b;*b t;
}//直接选择排序
void selectSort(Datatype a[], int n) {int i 0, j 0, k 0;for (i 0; i n; i) {k i;//每次更新第一个或最后一个元素的位置 for (j i 1; j n; j)if (a[j] a[k])//遍历寻找最小值k j;if (k ! i) {//找到的最小值没有放在第一个位置int temp a[k];a[k] a[i];a[i] temp;}}
}//经优化的选择排序每次同时选出最小的和最大的
void selectSortplus(Datatype* a, int n) {int begin 0, end n - 1;//起标记作用的两个变量while (begin end) {//能不能加等于取决于交换数据时用的方法int maxi begin, mini begin;for (int i begin; i end; i) {if (a[i] a[maxi])maxi i;if (a[i] a[mini])mini i;}Swap(a[begin], a[mini]);if (begin maxi)//处理begin和maxi重叠时的情况maxi mini;Swap(a[end], a[maxi]);begin;//双指针思路--end;}
}//大堆向下调整
void adjustMaxDown(Datatype* a, int n, int parent) {int child parent * 2 1;while (child n) {if (child 1 n)if (a[child] a[child 1])child;if (a[child] a[parent]) {Swap(a[child], a[parent]);parent child;child parent * 2 1;}else break;}
}//堆排序
void heapSort(Datatype* a, int n) {int i 0;//向下调整建堆从倒数第一个父结点开始for (i (n - 1 - 1) / 2; i 0; i--)adjustMaxDown(a, n, i);int end n - 1;while (end 0) {int tmp a[0];a[0] a[end];a[end] tmp;adjustMaxDown(a, end, 0);--end;}
}//拷贝方式的堆排序
void heapSortCopy(Datatype* a, int n) {//2*N*logN//创建一个临时的堆Datatype* hp (Datatype*)malloc(sizeof(Datatype) * n);if (hp NULL)return;int i 0;for (i 0; i n; i)hp[i] a[i];for (i (n - 1 - 1) / 2; i 0; i--)adjustMaxDown(hp, n, i);int cnt 0, hpCap n;for (i n - 1; i 0; i--) {a[i] hp[0];Swap(hp[0], hp[hpCap - 1]);hpCap--;adjustMaxDown(hp, hpCap, 0);}free(hp);
}//直接插入排序未优化
void insertSort(Datatype* a, int n) {for (int i 0, j, k; i n; i) {for (j i - 1; j 0; j--)//这里并没有挪动操作所以是浪费了部分时间if (a[j] a[i])//修改这里的比较运算符为能使算法不稳定break;if (j ! i - 1) {Datatype temp a[i];for (k i - 1; k j; k--)a[k 1] a[k];a[k 1] temp;}}
}//直接插入排序小优化
void insertSortPlus(Datatype* a, int n) {for (int i 0; i n - 1; i) {// [0, end] 有序插入tmp依旧有序int end i;//int end;表示单趟int endi;和for表示整个过程Datatype tmp a[i 1];while (end 0) {if (a[end] tmp) {//修改这里的比较运算符为能使算法不稳定a[end 1] a[end];--end;}elsebreak;}a[end 1] tmp;}
}//希尔排序gapgap/2
void shellSort(Datatype* a, int n) {int gap n;while (gap 1) {gap gap / 2;//缩小增量int i 0;for (i 0; i n - gap; i) {//插入排序int end i;int tmp a[end gap];while (end 0) {if (a[end] tmp) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}
}//希尔排序gapgap/31
void shellSort2(Datatype* a, int n) {int gap n;while (gap 1) {gap gap / 3 1;//1可以保证最后一次一定是1int i 0;for (i 0; i n - gap; i) {//插入排序int end i;Datatype tmp a[end gap];while (end 0) {if (a[end] tmp) {a[end gap] a[end];end - gap;}else break;}a[end gap] tmp;}}
}//冒泡排序因为性能实在太差只上优化版本
void bubbleSort(Datatype* a, int n) {int i 0, j 0;for (i 0; i n; i) {//表示这是第i1轮排序int judg 0;for (j 1; j n - i; j)//表示正在比较的数据if (a[j - 1] a[j]) {Swap(a[j - 1], a[j]);judg 1;}if (judg 0) break;}
}int partSortHoare(Datatype* a, int left, int right) {int keyi left;//keyi记录下标, key记录值。while (left right) {//相遇时结束循环// 右边找小while (left right a[right] a[keyi])//利用c语言的短路特性去判断--right;// 左边找大while (left right a[left] a[keyi])left;Swap(a[left], a[right]);}Swap(a[keyi], a[left]);//相遇了就交换return left;
}//快速排序hoare版本
void quickSortHoare(Datatype* a, int left, int right) {if (right - left 0)//区间只有1个值或区间不存在时没必要继续分return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int keyi partSortHoare(a, left, right);// 划分成功后以keyi为边界形成了左右两部分 [left, keyi) 和 [keyi1, right)// 递归排[left, div)quickSortHoare(a, left, keyi - 1);// 递归排[div1, right)quickSortHoare(a, keyi 1, right);
}int partSortHole(Datatype* a, int left, int right) {int key a[left];int hole left;//坑while (left right) {// 右边找小while (left right a[right] key)--right;a[hole] a[right];hole right;//找到数据后就交换形成新坑// 左边找大while (left right a[left] key)left;a[hole] a[left];hole left;}a[hole] key;//相遇位置即为最后一个坑的位置return hole;
}//快速排序挖坑法
void quickSortHole(Datatype* a, int left, int right) {if (right - left 0)//区间只有1个值或区间不存在时没必要继续分return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int keyi partSortHole(a, left, right);// 划分成功后以keyi为边界形成了左右两部分 [left, keyi) 和 [keyi1, right)// 递归排[left, div)quickSortHole(a, left, keyi - 1);// 递归排[div1, right)quickSortHole(a, keyi 1, right);
}int partSortDPoint(Datatype* a, int left, int right) {int prev left;int cur left 1;int keyi left;while (cur right) {if (a[cur] a[keyi] prev ! cur)//prev和cur相等时无意义Swap(a[prev], a[cur]);cur;}Swap(a[prev], a[keyi]);//keyi prev; return keyi;return prev;
}//快速排序前后指针
void quickSortDPoint(Datatype* a, int left, int right) {if (right - left 0)//区间只有1个值或区间不存在时没必要继续分return;// 按照基准值对array数组的 [left, right)区间中的元素进行划分int keyi partSortDPoint(a, left, right);// 划分成功后以keyi为边界形成了左右两部分 [left, keyi) 和 [keyi1, right)// 递归排[left, div)quickSortDPoint(a, left, keyi - 1);// 递归排[div1, right)quickSortDPoint(a, keyi 1, right);
}//快排的三路划分再优化方案。
void quickSortTRoute(Datatype* a, int begin, int end) {if (begin end)return;int left begin;int right end;int cur left 1;Datatype key a[left];while (cur right) {if (a[cur] key) {Swap(a[cur], a[left]);left;cur;}else if (a[cur] key) {Swap(a[cur], a[right]);--right;}else {cur;}}quickSortTRoute(a, begin, left - 1);quickSortTRoute(a, right 1, end);
}//快排的非递归实现Hoare版本
void quickSortNonRHoare(Datatype* a, int left, int right) {int* st (int*)malloc(sizeof(int) * 100 * 10//floor(log(right - left 1) / log(2)) * 3);//栈开100个空间后就能处理平时99%的数据排列//开1000个是因为极端情况下越界严重if (st NULL) {printf(栈空间申请失败\n);return;}int top 0;//一个栈顶变量和一个数组构成的简易栈st[top] right;st[top] left;while (top ! 0) {int l st[top - 1];--top;int r st[top - 1];--top;int keyi partSortHoare(a, l, r);//单趟排序if (keyi 1 r) {st[top] r;//右边先入栈st[top] keyi 1;}if (l keyi - 1) {st[top] keyi - 1;//左边后入栈st[top] l;}}free(st);
}//快排的非递归实现挖坑法
void quickSortNonRHole(Datatype* a, int left, int right) {int* st (int*)malloc(sizeof(int) * 100 * 10//floor(log(right - left 1) / log(2)) * 3);//栈开100个空间后就能处理平时99%的数据排列//开1000个是因为极端情况下越界严重if (st NULL) {printf(栈空间申请失败\n);return;}int top 0;//一个栈顶变量和一个数组构成的简易栈st[top] right;st[top] left;while (top ! 0) {int l st[top - 1];--top;int r st[top - 1];--top;int keyi partSortHole(a, l, r);//单趟排序if (keyi 1 r) {st[top] r;//右边先入栈st[top] keyi 1;}if (l keyi - 1) {st[top] keyi - 1;//左边后入栈st[top] l;}}free(st);
}//快排的非递归实现前后指针
void quickSortNonRDPoint(Datatype* a, int left, int right) {int* st (int*)malloc(sizeof(int) * 100 * 10//floor(log(right - left 1) / log(2)) * 3);//栈开100个空间后就能处理平时99%的数据排列//开1000个是因为极端情况下越界严重if (st NULL) {printf(栈空间申请失败\n);return;}int top 0;//一个栈顶变量和一个数组构成的简易栈st[top] right;st[top] left;while (top ! 0) {int l st[top - 1];--top;int r st[top - 1];--top;int keyi partSortDPoint(a, l, r);//单趟排序if (keyi 1 r) {st[top] r;//右边先入栈st[top] keyi 1;}if (l keyi - 1) {st[top] keyi - 1;//左边后入栈st[top] l;}}free(st);
}void _mergeSort(Datatype* a, int begin, int end, Datatype* tmp) {if (begin end)return;//不可能出现beginend的情况//除非c语言的除法运算是向上取整 小区间优化优化效率在10%~20%//if (end - begin 1 10) {//区间选择[8,15]最佳// insertSort(a begin, end - begin 1);// return;//}int mid (begin end) / 2;//将这组数据分成两个区间 [begin, mid] [mid1, end]_mergeSort(a, begin, mid, tmp);_mergeSort(a, mid 1, end, tmp);// 归并两个区间int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2) {//合并区间if (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//将剩余的数接在临时数组的尾部//理论上下面这两个while循环只有一个能进行while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];for (i begin; i end; i)a[i] tmp[i];
}//归并排序无小区间优化
void mergeSort(Datatype* a, int n) {Datatype* tmp (Datatype*)malloc(sizeof(Datatype) * n);_mergeSort(a, 0, n - 1, tmp);free(tmp);
}void _mergeSortPlus(Datatype* a, int begin, int end, Datatype* tmp) {if (begin end)return;//不可能出现beginend的情况//除非c语言的除法运算是向上取整// 小区间优化优化效率在10%~20%if (end - begin 1 10) {//区间选择[8,15]最佳insertSort(a begin, end - begin 1);return;}int mid (begin end) / 2;//将这组数据分成两个区间 [begin, mid] [mid1, end]_mergeSortPlus(a, begin, mid, tmp);_mergeSortPlus(a, mid 1, end, tmp);// 归并两个区间int begin1 begin, end1 mid;int begin2 mid 1, end2 end;int i begin;while (begin1 end1 begin2 end2) {//合并区间if (a[begin1] a[begin2])tmp[i] a[begin1];elsetmp[i] a[begin2];}//将剩余的数接在临时数组的尾部//理论上下面这两个while循环只有一个能进行while (begin1 end1)tmp[i] a[begin1];while (begin2 end2)tmp[i] a[begin2];for (i begin; i end; i)a[i] tmp[i];
}//归并排序小区间优化
void mergeSortPlus(Datatype* a, int n) {Datatype* tmp (Datatype*)malloc(sizeof(Datatype) * n);_mergeSortPlus(a, 0, n - 1, tmp);free(tmp);
}//归并排序非递归实现
void mergeSortNonR(Datatype* a, int n) {Datatype* tmp (Datatype*)malloc(sizeof(Datatype) * n);if (tmp NULL)return;//通过控制每组要合并的数据个数控制排序本体//gap是每组的数据个数可以是124....n/2int gap 1;while (gap n) {int j 0, i 0;//每次循环跳过两个区间for (i 0; i n; i 2 * gap) {int begin1 i, end1 i gap - 1;//这样一个区间的数据个数为gap个int begin2 i gap, end2 i 2 * gap - 1;//int j i;//若j放在for循环内则要初始化为i。也就是最左边区间的左边界// 修正奇数分组归并时区间1囊括所有数据的情况if (end1 n || begin2 n)break;//修正奇数分组归并时区间2的组数不够导致右区间越界的情况if (end2 n)end2 n - 1;//之后就是正常的归并排序while (begin1 end1 begin2 end2)if (a[begin1] a[begin2])tmp[j] a[begin1];elsetmp[j] a[begin2];while (begin1 end1)tmp[j] a[begin1];while (begin2 end2)tmp[j] a[begin2];// 归并一组拷贝一组//将所有参与归并的数据进行拷贝// 参与归并的区间为[i,end2]//memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));//这里j的最终的值和end2是一样的即使经过这一轮拷贝for (j i; j end2; j)a[j] tmp[j];}//memcpy(a, tmp, sizeof(int) * n);//有用break阻止后续归并一次性拷贝一层无法处理越界的情况gap * 2;}free(tmp);
}//计数排序
void countSort(Datatype* a, int n) {Datatype min a[0], max a[0];int i;for (i 0; i n; i) {if (a[i] min)min a[i];if (a[i] max)max a[i];}int range max - min 1;//求数据的范围Datatype* countA (Datatype*)malloc(sizeof(Datatype) * range);if (countA NULL)return;memset(countA, 0, sizeof(Datatype) * range);//计数数组// 统计次数for (i 0; i n; i)countA[a[i] - min];// 排序int k 0, j 0;for (j 0; j range; j)while (countA[j]--)a[k] j min;free(countA);
}test.cpp
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif
/**/
#includesortAlgorithm.h
#includechrono
#includeiostream
using namespace std;int sortJudg(Datatype* a, int n) {//判断数据是否升序int i 0;for (i 0; i n - 1; i)if (a[i] a[i 1])break;return i n - 1;
}void f0() {//测试排序算法的可行性srand((size_t)time(0));
#define NUM 100Datatype* a (Datatype*)malloc(sizeof(Datatype) * NUM),* b (Datatype*)malloc(sizeof(Datatype) * NUM);if (a NULL) return;if (b NULL) return;for (int i 0; i NUM; i) {a[i] rand() 1;b[i] a[i];}//函数指针数组void (*f[13])(Datatype*, int) {selectSort,selectSortplus,heapSort,heapSortCopy,insertSort,insertSortPlus,shellSort,shellSort2,bubbleSort,mergeSort,mergeSortPlus,mergeSortNonR,countSort};void (*f2[7])(Datatype*, int, int) {quickSortHoare,quickSortHole,quickSortDPoint,quickSortTRoute,quickSortNonRHoare,quickSortNonRHole,quickSortNonRDPoint};for (int i 0; i 13; i) {f[i](a, NUM);printf(%d\n, sortJudg(a, NUM));for (int i 0; i NUM; i) a[i] b[i];}for (int i 0; i 7; i) {f2[i](a, 0, NUM - 1);printf(%d\n, sortJudg(a, NUM));for (int i 0; i NUM; i) a[i] b[i];}free(a);free(b);
#undef NUM
}void _f1(Datatype* a, int n,void (*f)(Datatype*, int), const char* st) {auto begin std::chrono::high_resolution_clock::now();f(a, n);auto end std::chrono::high_resolution_clock::now();std::chrono::durationdouble time1 end - begin;std::cout st : time1.count() endl;
}//c的函数重载
void _f1(Datatype* a, int n,void (*f)(Datatype*, int, int), const char* st) {auto begin std::chrono::high_resolution_clock::now();f(a, 0, n - 1);auto end std::chrono::high_resolution_clock::now();std::chrono::durationdouble time1 end - begin;std::cout st : time1.count() endl;
}void f1() {srand((size_t)time(0));int n 10;int i 0;while (n 100000) {Datatype* a (Datatype*)malloc(sizeof(Datatype) * n),* b (Datatype*)malloc(sizeof(Datatype) * n);if (a NULL)return;if (b NULL)return;for (i 0; i n; i) {a[i] (rand()*rand())%n 1;b[i] a[i];}printf(%d个数据的情况\n, n);_f1(a, n, selectSort, selectSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, selectSortplus, selectSortplus);for (i 0; i n; i) a[i] b[i];_f1(a, n, heapSort, heapSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, heapSortCopy, heapSortCopy);for (i 0; i n; i) a[i] b[i];_f1(a, n, insertSort, insertSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, insertSortPlus, insertSortPlus);for (i 0; i n; i) a[i] b[i];_f1(a, n, shellSort, shellSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, shellSort2, shellSort2);for (i 0; i n; i) a[i] b[i];_f1(a, n, bubbleSort, bubbleSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortHoare, quickSortHoare);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortHole, quickSortHole);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortDPoint, quickSortDPoint);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortTRoute, quickSortTRoute);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortNonRHoare, quickSortNonRHoare);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortNonRHole, quickSortNonRHole);for (i 0; i n; i) a[i] b[i];_f1(a, n, quickSortNonRDPoint, quickSortNonRDPoint);for (i 0; i n; i) a[i] b[i];_f1(a, n, mergeSort, mergeSort);for (i 0; i n; i) a[i] b[i];_f1(a, n, mergeSortPlus, mergeSortPlus);for (i 0; i n; i) a[i] b[i];_f1(a, n, mergeSortNonR, mergeSortNonR);for (i 0; i n; i) a[i] b[i];_f1(a, n, countSort, countSort);for (i 0; i n; i) a[i] b[i];free(a);free(b);n * 10;printf(\n);}
}int main() {//f0();//排序算法可行性分析f1();//测试排序耗时return 0;
}
这里只敢放10万个数据因为个别时间复杂度为 O ( n 2 ) O(n^2) O(n2)的排序算法实在太慢了。后面会对数据进行微调来测试不用的情况。
时间复杂度测试结果
其中最具有代表性的是10个数据的情况和大量数据的情况。受到设备的影响结果可能有差异所以这里只举其中一个样例。这里的浮点数例如1.4e-05表示的是 1.4 × 1 0 − 5 1.4\times10^{-5} 1.4×10−5单位是秒。
10个数据的情况
selectSort:1.04e-05
selectSortplus:3e-07
heapSort:3e-07
heapSortCopy:1.6e-06
insertSort:4e-07
insertSortPlus:1e-07
shellSort:3e-07
shellSort2:3e-07
bubbleSort:2e-07
quickSortHoare:4e-07
quickSortHole:4e-07
quickSortDPoint:4e-07
quickSortTRoute:4e-07
quickSortNonRHoare:1.8e-06
quickSortNonRHole:1.4e-06
quickSortNonRDPoint:1.7e-06
mergeSort:1.8e-06
mergeSortPlus:1.6e-06
mergeSortNonR:1.4e-06
countSort:7e-07可以看出插入排序在这种小数据的情况下性能是最优的这也是为什么小区间优化会选择插入排序的原因。
接下来是10w个数据的情况。可以看到时间复杂度为 O ( n 2 ) O(n^2) O(n2)的排序已经吃不消了冒泡排序直接蚌埠住了。
100000个数据的情况
selectSort:2.45815
selectSortplus:5.77021
heapSort:0.0047019
heapSortCopy:0.0050789
insertSort:1.43777
insertSortPlus:0.87611
shellSort:0.0112118
shellSort2:0.0087459
bubbleSort:12.4946
quickSortHoare:0.0050874
quickSortHole:0.0050904
quickSortDPoint:0.0054573
quickSortTRoute:0.005225
quickSortNonRHoare:0.0053119
quickSortNonRHole:0.004995
quickSortNonRDPoint:0.0051825
mergeSort:0.0092598
mergeSortPlus:0.0087718
mergeSortNonR:0.0075344
countSort:0.0006727之后将 O ( n 2 ) O(n^2) O(n2)的算法给注释掉测试极端情况下各个算法排序的性能。
100w是自己的设备在运行带有递归的排序算法时的极限再扩大10倍就会栈溢出。
1000000个数据的情况
heapSort:0.407758
heapSortCopy:0.468729
shellSort:0.217771
shellSort2:0.171042
quickSortHoare:0.185388
quickSortHole:0.133911
quickSortDPoint:0.218722
quickSortTRoute:0.251578
quickSortNonRHoare:0.153858
quickSortNonRHole:0.120381
quickSortNonRDPoint:0.204297
mergeSort:0.147725
mergeSortPlus:0.12035
mergeSortNonR:0.134911
countSort:0.0056529再将所有带有递归的排序算法注释掉。
1000000个数据的情况
heapSort:0.386531
heapSortCopy:0.408616
shellSort:0.202543
shellSort2:0.167401
quickSortNonRHoare:0.154687
quickSortNonRHole:0.120555
quickSortNonRDPoint:0.221774
mergeSortNonR:0.129261
countSort:0.005713910000000个数据的情况
heapSort:5.64962
heapSortCopy:5.85666
shellSort:2.93551
shellSort2:2.6005
quickSortNonRHoare:2.75501
quickSortNonRHole:3.13497
quickSortNonRDPoint:3.75697
mergeSortNonR:1.463
countSort:0.0653788100000000个数据的情况
heapSort:89.2091
heapSortCopy:89.406
shellSort:41.1887
shellSort2:27.0528
quickSortNonRHoare:146.442
quickSortNonRHole:172.822
quickSortNonRDPoint:179.666
mergeSortNonR:15.9719
countSort:0.66968快排的特点是重复越多效率越慢而rand函数返回的最大值为32767于是将数组初始化为rand()*rand()1以减少重复后的测试结果
1000000个数据的情况
heapSort:0.360787
heapSortCopy:0.368785
shellSort:0.240912
shellSort2:0.169701
quickSortNonRHoare:0.158003
quickSortNonRHole:0.116451
quickSortNonRDPoint:0.241888
mergeSortNonR:0.139041
countSort:0.001281810000000个数据的情况
heapSort:6.07863
heapSortCopy:6.02169
shellSort:3.52872
shellSort2:2.82663
quickSortNonRHoare:1.79774
quickSortNonRHole:1.33191
quickSortNonRDPoint:2.63835
mergeSortNonR:1.62083
countSort:0.0128354100000000个数据的情况
heapSort:89.2351
heapSortCopy:95.0854
shellSort:51.2792
shellSort2:36.6936
quickSortNonRHoare:20.3174
quickSortNonRHole:15.1538
quickSortNonRDPoint:30.2327
mergeSortNonR:18.416
countSort:0.130009到这个应该用外排序来操作的数据量这些算法能兼职足够说明它们都很优秀。我们能做的是根据平时的情况选择合适的排序算法来进行数据排序。
