数据机构之排序算法 ————快排

快排：快速排序，是一种基于二分思想的快速，有效的排序方式，也是实际使用场景中经常会用到的排序算法，我们有必要了解他们；
注意本篇博客不涉及原理讨论，只提供一种实现的代码设计

基于霍尔划分的快速排序

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遍历完后，即代表一次快排完成
多轮完成快排
各位宝贝一点要看着代码看总结哦，这样更好理解，现在有了这样的认识，思考一下是不是还可以进行一定的优化呢？问题就留给你们啦
欢迎各位大佬批评指正，

你的鼓励让我更有动力

赞赏

0人进行了赞赏支持

总结

你的鼓励让我更有动力

更多相关文章

随机推荐