快排:快速排序,是一种基于二分思想的快速,有效的排序方式,也是实际使用场景中经常会用到的排序算法,我们有必要了解他们;
注意本篇博客不涉及原理讨论,只提供一种实现的代码设计
-
基于霍尔划分的快速排序
int haroPart(int* array, int begin, int end) { int start = begin;//保留一下最初的begin,逻辑最后需要交换 //先从后往前找,第一个比begin位置小的 while (begin < end) { while (begin < end && array[end] >= array[start]) { --end; }//当前end所在位置一定比begin位置小 //从前往后找,第一个比begin位置大的值 while (begin < end && array[begin] < array[start]) { ++begin; } Swap(array, begin, end); } if (begin == end) { Swap(array, start, begin); } return begin; }
2.基于挖坑法的快速排序
int digPart(int* array, int begin, int end) { int key = array[begin]; while (begin < end) { while (begin < end && array[end] >= key) { --end; } array[begin] = array[end]; while (begin < end && array[begin] <= key) { ++begin; } array[end] = array[begin]; } array[begin] = key; return begin; }
3.基于快慢指针(思想)的一种快速排序方法
int prevPart(int* array, int begin, int end) { int prev = begin; int cur = prev + 1;//最开始的时候,cur是prev的下一个 int key = array[begin];//基准值 while (cur <= end)//cur 移动的快,找每次小于基准值得位置 { //判断条件是,prev和cur如果不连续的话,说明prev的下一个位置是大于基准值的, if (array[cur] < key && ++prev != cur)//这里我们判断条件里写了++prev,其实是有风险的,如果调换判断位置,排序就会失效了 { Swap(array, prev, cur); } cur++;//处理完成后cur后移,prev已经后移; } Swap(array, begin, prev); return prev; }
4.快排主体--递归写法
void quickSort(int* array, int begin, int end) { //cout << "我是霍尔划分哦:" << endl; if (begin >= end) { return; }//如果begin位置大于等于end,那排序就结束了,end开始表示最后一个位置 //获取基准值 int keyPos = prevPart(array, begin, end); //递归写法 quickSort(array, begin, keyPos - 1); quickSort(array, keyPos + 1, end); }
总结
- 无论哪种划分思想,首先必须注意的是排序后我们要求的序列式哪种,递增or递减,这个对我们的代码设计有很大影响(其实也不能绝对这么说,但是不注意就会出错,划不来)
- 基于霍尔排序的快排思想:
对于要求为递增序列来说,首先应该循环的,由后向前找到第一个比基准值小的值,再由前向后,找到第一个比基准值大的值,跳出各自遍历的循环,交换找到的这俩个值的位置
当二者在同一个位置的时候,代表本轮排序完成,交换基准值和这个共同位置,然后执行下一轮快排 - 基于挖坑划分的快排思想:
对于要求递增结果的排序来说,首先,借助第三变量保留基准值,将本来基准值的位置“挖空”,
然后循环的,由后向前的找到第一个小于基准值的位置,交换它去“空坑”
循环的,由前向后找到第一个大于基准值的位置,交换它去“空坑”,这个时候这个空坑位置其实是“我们标记的由后向前寻找的那个位置的索引(各位看官不理解请看代码哦)”
待到俩个方向的“索引”到同一位置时,将基准值填入其中,一轮快排结束
循环多轮结束排序 - 基于前后指针思想的快排:(快慢指针)
对于要求递增序列结果的排序来说,首先是建立索引位置,快指针思想的索引cur,慢指针思想的prev; 加上begin,end
从前向后找,cur位置是prev的下一个(最开始),prev是begin位置
循环的,找到下一个比基准值小的,标记为cur, prev是目前已经有序的子序列中最后一个元素的位置
判断cur 是否为prev的下一个位置,是的话说明俩索引共同移动,不是的话说明,prev的下一个元素就是无序子序列的第一个大于基准值的值,prev指向这个位置,并且将这个位置利用prev和cur进行交换,
当快索引cur遍历完后,即代表一次快排完成
多轮完成快排 - 各位宝贝一点要看着代码看总结哦,这样更好理解,现在有了这样的认识,思考一下是不是还可以进行一定的优化呢?问题就留给你们啦
- 欢迎各位大佬批评指正,