君兮_的个人主页 即使走的再远,也勿忘启程时的初心 C/C++ 游戏开发 Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来
即使走的再远,也勿忘启程时的初心
Hello,米娜桑们,这里是君兮_,国庆长假结束了,无论是工作还是学习都该回到正轨上来了,从今天开始恢复正常的更新频率,今天为大家带来的内容是快速排序的两大优化和非递归实现
Swap(int* p1, int* p2){ int tmp = *p1; *p1 = *p2; *p2 = tmp;}int getMid(int* a, int left, int right){ assert(a); int mid = (left + right) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) return mid; else if(a[right]>a[left]) { return left; } else { return right; } } else { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) { return left; } else { return right; } }}int PartSort1(int* a, int left, int right){ int mid = getMid(a, left, right);//三数取中 //把取好的key放到left中 Swap(&a[left], &a[mid]); int key = left; while (left<right) { //右边先走 while (left < right && a[right] >= a[key]) { right--; } //左边走 while (left<right&&a[left]<=a[key]) { left++; } //交换 Swap(&a[left], &a[right]); } //交换停下的位置的值把key换到此时左右相遇的位置 Swap(&a[key], &a[left]); //此时key的左右都有序,由于right,left都指处于key的位置返回任意即可 return right;}void QuickSort(int* a, int left,int right){//只剩下一个值了,说明已经有序,不需要再排,递归结束 if (left >= right) return; int key = PartSort1(a,left,right); //key已经满足左右都有序了不需要再排 //排key的左边 QuickSort(a, left, key-1); //排key的右边 QuickSort(a, key+1, right);}
我们知道,快速排序是先取一个key值然后让左右两边有序来进行排序的,因此key值的取值对我们快速排序的速度是有比较大的影响的,举个最坏的例子,假设每次我们取到的key值都是此次所需排序数据中最小的,如下图所示
此时的时间复杂度就是O(N^2)了,因此,我们需要对快速排序进行优化,尽量减少出现图示的这种情况,就有了以下的代码
int getMid(int* a, int left, int right){ assert(a); int mid = (left + right) / 2; if (a[left] > a[mid]) { if (a[mid] > a[right]) return mid; else if(a[right]>a[left]) { return left; } else { return right; } } else { if (a[mid] < a[right]) return mid; else if (a[left] > a[right]) { return left; } else { return right; } }}
void QuickSort1(int* a, int begin, int end){if (begin >= end)return;// 小区间优化,小区间不再递归分割排序,降低递归次数if ((end - begin + 1) > 10){int keyi = PartSort1(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{InsertSort(a + begin, end - begin + 1);}}
void QuickSort1(int* a, int begin, int end){if (begin >= end)return;// 小区间优化,小区间不再递归分割排序,降低递归次数if ((end - begin + 1) > 10){int keyi = PartSort1(a, begin, end);// [begin, keyi-1] keyi [keyi+1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi + 1, end);}else{InsertSort(a + begin, end - begin + 1);}}
void QuickSortNonR(int* a, int left,int right){ Stack st; StackInit(&st);//初始化栈 StackPush(&st, left);//入栈 StackPush(&st, right); while (!StackEmpty(&st))//判断栈是否为空 { int right = StackTop(&st);//后进先出,取栈顶元素 StackPop(&st);//此时的栈顶元素出栈 int left = StackTop(&st);//此时的栈顶为left StackPop(&st); int key = PartSort1(a, left, right);//选key值 if (key + 1 < right)//此时key+1小于right 把key+1作为下一次排序的左 right作为右入栈 { StackPush(&st, key + 1); StackPush(&st, right); } if (left < key - 1)//key-1大于left key-1就为下一次循环的右,left为左 { StackPush(&st, left); StackPush(&st, key - 1); } } //当栈中没有元素了,说明此时的左大于等于右,此时已经没有数据未进行排序了 StackDestroy(&st);//销毁栈}
新人博主创作不易,如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力!!!
**(可莉请求你们三连支持一下博主!!!点击下方评论点赞收藏帮帮可莉吧)**
来源地址:https://blog.csdn.net/syf666250/article/details/133691828
--结束END--
本文标题: 【数据结构与算法】如何对快速排序进行细节优化以及实现非递归版本的快速排序?
本文链接: https://www.lsjlt.com/news/435929.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-04-03
2024-04-03
2024-04-01
2024-01-21
2024-01-21
2024-01-21
2024-01-21
2023-12-23
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0