文章目录 一、hoare版本二、挖坑法三、前后指针法四、非递归快排五、快速排序优化1、三数取中选key值2、小区间优化 六、代码测试 一、hoare版本 快速排序是Hoare于
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
算法思想:
hoare版本单趟排序图示:
hoare版本代码:
//交换void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}//hoare版本void QuickSort1(int* a, int begin, int end){//递归结束条件if (begin >= end){return;}int keyi = begin;int left = begin;int right = end;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= a[keyi]){right--;}//right找到比key值小的之后换到left走,找到比key值大的while (left < right && a[left] <= a[keyi]){left++;}//交换Swap(&a[left], &a[right]);}//将key值换到中间Swap(&a[keyi], &a[left]);//更新keykeyi = left;//对左右序列继续排序QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}
整体流程图:
挖坑法思想:
挖坑法单趟排序图示:
挖坑法代码:
//挖坑法void QuickSort2(int* a, int begin, int end){//递归结束条件if (begin >= end){return;}int left = begin;int right = end;int key = a[left];//坑最初与left一样在开始位置int hole = left;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= key){right--;}//将right找到的比key小的元素放进坑中a[hole] = a[right];//更新坑的位置hole = right;//然后左边走找到比key值大的元素停下来while (left < right && a[left] <= key){left++;}//将left找到的比key大的元素放进坑中a[hole] = a[left];//更新坑的位置hole = left;}//将key放入坑中a[hole] = key;//对左右序列继续排序QuickSort2(a, begin, hole - 1);QuickSort2(a, hole+1, end);}
前后指针法思想:
前后指针法单趟排序图示:
前后指针法代码:
//交换void Swap(int* a, int* b){int tmp = *a;*a = *b;*b = tmp;}//前后指针void QuickSort3(int* a, int begin, int end){//递归结束条件if (begin >= end){return;}int keyi = begin;int prev = begin;int cur = begin + 1;//每趟排序直到cur下标大于endwhile (cur <= end){//cur找比key小的值if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[cur], &a[prev]);}cur++;}//将key换到中间Swap(&a[keyi], &a[prev]);//更新key的下标keyi = prev;//对左右序列继续排序QuickSort3(a, begin, keyi - 1);QuickSort3(a, keyi + 1, end);}
快速排序是一种不稳定的排序,它的时间复杂度为O(N*logN),但最坏可以达到O(N2) ,它的空间复杂度为O(logN)
以上三种方法都是采用了分治法递归实现的快排,其实快速排序也可以非递归实现,非递归实现快排需要利用栈来实现
思路:
将数组首尾下标存入栈中,在循环中依次取出作为left和right对数组进行排序,然后对得到的key的左右两边序列也进行相同的操作,其中左边为left到keyi-1,右边为keyi+1到right,这些下标的入栈顺序需要看取出的顺序,如下面代码中是先取出后面元素下标的,所以入栈时要先入后面的,因为栈的特点是先入后出。
非递归快排代码:
(该代码中用到的栈需自己实现,C语言实现栈可参考:栈的实现)
//非递归快速排序void QuickSortNonR(int* a, int begin, int end){//创建一个栈ST st;//初始化栈STInit(&st);//插入尾元素下标STPush(&st, end);//插入首元素下标STPush(&st, begin);//栈为空停下while (!STEmpty(&st)){//取出栈顶元素作为leftint left = STTop(&st);//取出后在栈中删除STPop(&st);//取出栈顶元素作为rightint right = STTop(&st);//取出后在栈中删除STPop(&st);int keyi = begin;//每趟排序直到左右相遇while (left < right){//右边先走,找到比key值小的while (left < right && a[right] >= a[keyi]){right--;}//right找到比key值小的之后换到left走,找到比key值大的while (left < right && a[left] <= a[keyi]){left++;}//交换Swap(&a[left], &a[right]);}//将key值换到中间Swap(&a[keyi], &a[left]);//更新key的下标keyi = left;// 当前数组下标样子 [left,keyi-1] keyi [keyi+1, right]//右边还有元素,按顺序插入right和keyi+1if (keyi + 1 < right){STPush(&st, right);STPush(&st, keyi + 1);}//左边还有元素,按顺序插入keyi-1和leftif (left < keyi - 1){STPush(&st, keyi - 1);STPush(&st, left);}}STDestroy(&st);}
前面三种快速排序的方法起初都要随机选取一个值作为key,我们之前是直接默认为数组首元素的,这样不够随机,容易出现最坏的情况,使得它的时间复杂度接近O(N2),所以我们可以写一个函数来选取这个key,使得它比较随机,而不是直接为首元素。
三数取中:
在一个数组最前面、最后面,中间这三个位置的数中选出大小处于中间的数
// 三数取中int GetMidi(int* a, int left, int right){int mid = (left + right) / 2;if (a[left] > a[right]){if (a[right] > a[mid]){return right;}else if(a[mid]>a[right]&&a[mid]<a[left]){return mid;}else{return left;}}else{if (a[left] > a[mid]){return left;}else if (a[mid] > a[left] && a[mid] < a[right]){return mid;}else{return right;}}}
在快排时用三数取中法选取key值再将它换到数组开头,可以有效避免出现最坏的情况,大大提升算法效率
当递归到数据较小时可以使用插入排序,使得小区间不再递归分割,降低递归次数
//打印数组void PrintArray(int* a, int n){for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");}void TestQuickSort1(){int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort1(a, 0, sizeof(a) / sizeof(int) - 1);printf("hoare版本快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));}void TestQuickSort2(){int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort2(a, 0, sizeof(a) / sizeof(int) - 1);printf("挖坑法快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));}void TestQuickSort3(){int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };QuickSort3(a, 0, sizeof(a) / sizeof(int) - 1);printf("前后指针法快速排序:\n");PrintArray(a, sizeof(a) / sizeof(int));}int main(){TestQuickSort1();TestQuickSort2();TestQuickSort3();return 0;}
来源地址:https://blog.csdn.net/zcxyywd/article/details/133270717
--结束END--
本文标题: 【C语言】快速排序
本文链接: https://www.lsjlt.com/news/441782.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0