企业网站软件下载,专业搜索引擎优化电话,网页制作模板关于我们,开发公司工程项目管理流程文件君兮_的个人主页 即使走的再远#xff0c;也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们#xff0c;这里是君兮_#xff0c;国庆长假结束了#xff0c;无论是工作还是学习都该回到正轨上来了#xff0c;从今天开始恢复正常的更新频率#xff0c;今天为大家带来的内容… 君兮_的个人主页 即使走的再远也勿忘启程时的初心 C/C 游戏开发 Hello,米娜桑们这里是君兮_国庆长假结束了无论是工作还是学习都该回到正轨上来了从今天开始恢复正常的更新频率今天为大家带来的内容是快速排序的两大优化和非递归实现 好了废话不多说开始我们今天的学习吧 快排优化与非递归实现 快速排序优化三数去中优化对递归次数的优化 非递归的快速排序总结
快速排序优化
有关快速排序的基本内容可以去看看这篇博客讲的已经非常详细了 【算法速查】万字图解带你快速入门八大排序(下我们在这里就以hoare版本的快速排序来讲讲还可以优化的地方以及为什么hoare版本的快速排序代码如下
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 (leftright){//右边先走while (left right a[right] a[key]){right--;}//左边走while (leftrighta[left]a[key]){left;}//交换Swap(a[left], a[right]);}//交换停下的位置的值把key换到此时左右相遇的位置Swap(a[key], a[left]);//此时key的左右都有序由于rightleft都指处于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, key1, 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;}}
}简单的来说上述这段代码表示的是这样的意思 取最左最右中间三个数分别对三个数进行比较最终取得的值就是处于三个值中中间的这个值。通过上述这个优化此时所需排序的数据中总要比我们取得的key值小以及比我们取得的key值大的值存在就能较大的提供我们的快排效率啦
对递归次数的优化
我们在使用递归版本的快速排序时当区间中的数比较少时仍然使用递归的方式进行是会消耗非常多不必要消耗的内存的还是举个例子假设此时区间中还有10个数需要排 我们递归返回的条件是leftright,递归是栈中开辟空间进行的当递归的层数过深栈的大小又不是很大就容易造成“爆栈”如上图所示为了排序这十个数我们又递归了这么多层是非常不明智的选择因此我们在数据较少的情况出现时可以使用插入排序等方法进行排序减少不必要的空间浪费也能提供我们快排的速度
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 [keyi1, 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 [keyi1, 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);//此时的栈顶为leftStackPop(st);int key PartSort1(a, left, right);//选key值if (key 1 right)//此时key1小于right 把key1作为下一次排序的左 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);//销毁栈
}和递归大致是一样的只不过我们是用栈的方式来模拟递归朝深度进行如果你能理解递归实现的快速排序相信非递归实现的快速排序对你来说也非常好理解唯一需要注意的是入栈和出栈的顺序当你开始先入右再入左的话由于后进先出的原因先出的是左其中是右这点在取栈顶元素作为排序的左右区间时一定要注意避免取错。
总结
好啦我们总算把八大排序算法都讲完了算法这一块光靠看代码不是那么容易理解的因此我花了大量的时间画图分析希望能对你有所帮助当然这篇文章创作的初衷是希望帮助初学者对排序算法有一个大致的了解对已经学过的人起到在需要使用的时候快速回忆的效果因此可能还有一部分细节不全之后我会挑出重点单独出博客讲解有任何的问题和对文章内容的疑惑欢迎在评论区中提出当然也可以私信我我会在第一时间回复的 新人博主创作不易如果感觉文章内容对你有所帮助的话不妨三连一下再走呗。你们的支持就是我更新的动力 **可莉请求你们三连支持一下博主点击下方评论点赞收藏帮帮可莉吧**
