12八大排序算法的稳定性以及时间空间复杂度总结
一、排序的稳定性
假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
至于为什么有的排序不稳定,这和排序本身的实现算法逻辑有关,以快排的挖坑法为例: 如果a[begin]和key相等,begin会跳过这个数,最终交换以后key会到这个数的右边,顺序就不对了。 如果不这么做,将会出现死循环。
排序的稳定性非常重要,如果我们只对一串数字排序,那么稳定与否确实不重要,因为一串数字的属性是单一的,就是数字值的大小。但是排序的元素往往不只有一个属性,例如我们对一群人按年龄排序,但是人除了年龄属性还有身高体重属性,在年龄相同时如果不想破坏原先身高体重的次序,就必须用稳定排序算法。
二、八种排序方式的复杂度和稳定性
最后再来直观看一下各种排序算法的时间:
// 测试排序的性能对比 void TestOP() { srand(time(0)); const int N = 100000;//随机生成十万个数,然后排序 int* a1 = (int*)malloc(sizeof(int) * N); int* a2 = (int*)malloc(sizeof(int) * N); int* a3 = (int*)malloc(sizeof(int) * N); int* a4 = (int*)malloc(sizeof(int) * N); int* a5 = (int*)malloc(sizeof(int) * N); int* a6 = (int*)malloc(sizeof(int) * N); int* a7 = (int*)malloc(sizeof(int) * N); int* a8 = (int*)malloc(sizeof(int) * N); for (int i = 0; i < N; ++i) { a1[i] = rand(); a2[i] = a1[i]; a3[i] = a1[i]; a4[i] = a1[i]; a5[i] = a1[i]; a6[i] = a1[i]; a7[i] = a1[i]; a8[i] = a1[i]; } int begin1 = clock();//clock()可以记住程序运行到这里的时间,单位是ms InsertSort(a1, N); int end1 = clock(); int begin2 = clock(); ShellSort(a2, N); int end2 = clock(); int begin3 = clock(); SelectSort(a3, N); int end3 = clock(); int begin4 = clock(); HeapSort(a5, N); int end4 = clock(); int begin5 = clock(); QuickSort(a4, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); printf("InsertSort:%d ", end1 - begin1); printf("ShellSort:%d ", end2 - begin2); printf("SelectSort:%d ", end3 - begin3); printf("HeapSort:%d ", end4 - begin4); printf("QuickSort:%d ", end5 - begin5); printf("MergeSort:%d ", end6 - begin6); printf("BubbleSort:%d ", end7 - begin7); printf("CountSort:%d ", end8 - begin8); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } int main() { TestOP(); }
三、总结
- 不基于比较的排序,对样本数据有严格要求,不易改写。
- 基于比较的排序,只要规定好两个样本怎么比大小就可以直接复用基于比较的排序,时间复杂度的极限是O(NlogN)。
- 时间复杂度O(NlogN)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的。
- 为了绝对的速度选快排、为了省空间选堆排、为了稳定性选归并。