4.快排的改进(三数取中版本和小区间优化)
1.快排的时间复杂度
> 理想状态下 > 假设我们所取的key每一次都能将它所在区间二分,也就构成了一颗完全二叉树 > 这时一共有N个结点,一共有大概log(2)(N)层 > (假设为满二叉树,但其实完全二叉树在节点个数多的情况下那几个空缺的结点可以忽略不计) > 也就是说理想状态下我们要进行log(2)N次单趟排序,而每一次单趟排序的时间复杂度都是O(N) > 所以时间复杂度为O(N*log(2)N)
我们呢来测一下性能
// 测试排序的性能对比 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); 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]; } int begin1 = clock();//clock()获取到系统运行到这里的毫秒数 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(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a5, 0, N - 1); int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); }
我们可以看到快排排序100000个随机数仅仅用了6ms,已经很快了,我们还可以看出插入排序就是比直接选择排序要强
但是,上面的是理想状态下的时间复杂度
那么不理想的情况呢?
快排什么情况下最坏呢?最坏的时候的时间复杂度是多少呢?
注意:不只是逆序的情况下最坏
而是有序的情况下最坏:
因为这时
每一趟排序只能排一个数
这就意味着快排的执行情况是这样的
(N+(N-1)+(N-2)+(N-3)+…+1)*N -> O(N^2)
所以快排有致命的缺陷
下面我们来测试一下快排排序有序数组的情况
// 测试排序的性能对比 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); 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]; } int begin1 = clock();//clock()获取到系统运行到这里的毫秒数 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(a4, N); int end4 = clock(); int begin5 = clock(); QuickSort(a4, 0, N - 1);//将a5改为a4即可,因为a5是无序数组,a4已经被排好序了,是有序数组 int end5 = clock(); int begin6 = clock(); MergeSort(a6, N); int end6 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("HeapSort:%d\n", end4 - begin4); printf("QuickSort:%d\n", end5 - begin5); printf("MergeSort:%d\n", end6 - begin6); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); }
我们可以看出快排这时候花了2563ms,比起堆排序和希尔排序来说太慢了
但是有人想到了一种优化的方法,这个方法极大地挽救了快排,让快排即使在有序的情况下也并不比无序的情况差多少
这个方法叫做:三数取中法
下面我们来介绍这个方法
2.三数取中方法
三数取中指的是:
从第一个数,最后一个数,中间那个数这三个数里面找出值为中间的那个数,让那个数去做key
可以有效避免有序状态下快排的致命缺陷,也可以避免无序状态下因为取key的随机性所导致的不可控的时间效率问题.
上代码,先让大家看一下
//三数取中: int GetMidIndex(int* a, int left, int right) { //下面两行的意思一样 //int mid = (left + right) / 2; int mid = (left + right) >> 1; if (a[left] < a[mid]) { if (a[mid] < a[right]) { return mid; } else if (a[left] > a[right])//mid是最大的,那么left和right中更大的那个就是中间值 { return left; } else { return right; } } else//a[left] >= a[mid] { if (a[mid] > a[right]) { return mid; } else if (a[left] < a[right])//mid是最小的,那么left和right中更小的那个就是中间值 { return left; } else { return right; } } }
void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int index = GetMidIndex(a, left, right); Swap(&a[left], &a[index]);//为了保证下面的代码不会发生改变,所以交换了a[index]和a[left]这两个数, int begin = left; int end = right; int pivot = begin; int key = a[begin]; while (begin < end) { while (end > begin && a[end] >= key) { --end; } a[pivot] = a[end]; pivot = end; while (begin < end && a[begin] <= key) { ++begin; } a[pivot] = a[begin]; pivot = begin; } pivot = begin; a[pivot] = key; QuickSort(a, left, pivot - 1); QuickSort(a, pivot + 1, right); }
然后,我们现在已经完成了三数取中的优化,接下来我们让我们测一下优化后的快排对于有序数组的效率.
在这里我们可以看出三数取中优化后的快排从2600多ms降为了1ms,可见三数取中拯救了快排
但是快排虽好,它也是使用递归来进行操作的,既然是递归,就免不了会有开辟函数栈帧的消耗,也有可能会出现栈溢出的情况,所以有人发明了小区间优化的方法,也有人发明了快排的非递归版本.
下面我们来剖析一下小区间优化
3.小区间优化版本
每调用一次函数,就会调用两次函数:左区间和右区间,所以函数调用次数是呈等比数列的形式增长的,所以说当基数越大(即调用层数越深时)时,函数调用的增长量越大,也就是说整个函数递归调用的次数很大一部分取决于最后几次调用
例如:最后一次调用就会使总的递归调用层数翻倍
所以有人就想能不能想个办法把最后几次的递归调用给消除掉呢?
于是就发明了小区间优化
小区间优化的整体思想:
下面上代码:
void QuickSort(int* a, int left, int right) { if (left >= right) { return; } int index = GetMidIndex(a, left, right); Swap(&a[left], &a[index]);//为了保证下面的代码不会发生改变,所以交换了a[index]和a[left]这两个数, int begin = left; int end = right; int pivot = begin; int key = a[begin]; while (begin < end) { while (end > begin && a[end] >= key) { --end; } a[pivot] = a[end]; pivot = end; while (begin < end && a[begin] <= key) { ++begin; } a[pivot] = a[begin]; pivot = begin; } pivot = begin; a[pivot] = key; //[left,pivot-1] pivot [pivot+1,right] if(pivot-1-left>10) { QuickSort(a, left, pivot - 1); } else { //对于闭区间[a,b]而言,这个区间内的元素个数为b-a+1,即右下标-左下标+1 InsertSort(a+left,pivot-1-left+1);//pivot-1-left-left+1 就是待排序数组的长度 //a+left:就是待排序数组的起始下标 } if(right-(pivot+1)>10) { QuickSort(a, pivot + 1, right); } } else { InsertSort(a+pivot+1,right-(pivot+1)+1); } }
1.其实小区间优化的效果并不明显,差不多100w次调用能减少10几ms的时间 2.C++的官方库里这个小区间也没有给很高,建议给10就行 因为小区间优化的目的 就是消除掉函数调用最后几层时所递归调用的巨大的次数 给个10,大概小区间优化的目的就完成了. 3.这里为什么要用插入排序呢? 因为我们只需要排序10个数字,所以直接用直接插入排序即可, 再去用快排会形成巨多栈帧不值得,用堆和希尔去做这么小的数据量的排序也很大材小用 因为上面的三个排序都是数据量越多相比于直接插入排序而言越有优势,而现在数据量很小,优势显不出来 而且本来进行了很多次快速排序的单趟排序后这个小区间内的数据有很多都已经是部分或整体有序的了 而直接插入排序对部分有序或整体有序的数组的排序有奇效(甚至时间复杂度有可能能达到O(N)),所以我们用直接插入排序即可
5.左右指针法
1.算法剖析
下面给大家介绍一下左右指针法,即挖坑法的一种变形
就是实现单趟排序的另一种方法
注意:
这两种方法得到的序列并不一定相同
下面给大家画个图
2.代码实现
void PartSort(int* a, int left, int right) { int index = GetMidIndex(a, left, right); Swap(&a[left], &a[index]); int begin = left; int end = right; int keyi = begin; while (begin < end) { while (a[end] >= a[keyi] && begin < end)// begin < end: //防止有序且没有三数取中的优化的情况下出现数组越界访问的情况 //不加=的话可能会死循环 //死循环:例如 // 5 .......... 5 // begin end //因为a[begin]==a[end] 都等于5 //所以如果没有加=的话begin和end就不会动了,也就是会导致死循环 //挖坑法也是 { end--; } while(a[begin] <= a[keyi] && begin < end) { begin++; } //注意:在这里我们必须先从右边开始找小,再从左边开始找大 //因为我们这个方法是挖坑法的一种变形, //而初始状态我们选定最左边的元素为key值,即为"坑位",所以根据左边有坑,右边找小的口诀, //我们要从右侧开始找起 Swap(&a[begin], &a[end]); } Swap(&a[begin], &a[keyi]); }
6.前后指针法
1.算法剖析
下面给大家介绍一下前后指针法,即挖坑法的一种变形
就是实现单趟排序的另一种方法
下面大家看一下这张图片
2.代码实现
下面我们来实现一下这个代码
void PartSort3(int* a, int left, int right) { int keyi = left; int prev = left; int cur = left + 1; while (cur <= right) { if (a[cur] < a[keyi]) { ++prev; Swap(&a[prev], &a[cur]); } //这是优化版本,使得当两数相同时无需进行交换,即防止自己和自己交换 // if (a[cur] < a[keyi] && ++prev!=cur) // { // Swap(&a[prev], &a[cur]); // } ++cur; } Swap(&a[prev], &a[keyi]); }
以上就是快速排序和冒泡排序的讲解,
希望能对大家有所帮助
关于快速排序的非递归版本我后续会给大家去单独写一篇博客去讲解
