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

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

  1. 基于霍尔划分的快速排序

    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遍历完后,即代表一次快排完成
    多轮完成快排

  • 各位宝贝一点要看着代码看总结哦,这样更好理解,现在有了这样的认识,思考一下是不是还可以进行一定的优化呢?问题就留给你们啦
  • 欢迎各位大佬批评指正,
上一篇:JDK源码阅读—AtomicInteger


下一篇:leetcode——对链表进行插入排序