排序算法-快速排序-编程思维

原理

  1. 默认按照从小到大的排序规则。
  2. 每次取中位坐标,将比中位坐标对应数字大的部分放右边,小的部分放左边。
  3. 然后再分别比较左边和右边的部分,按照2的规则。
  4. 直到没有办法再分左边和右边,说明比较完成。

图示

代码演示

public static void Sort(int[] array, int left, int right)
{
    if(left < right)
    {
        var middleIndex = QueryIndex(array, left, right); //获取中位坐标
        Sort(array, left, middleIndex - 1); //比较左边的部分
        Sort(array, middleIndex + 1, right); //比较右边的部分
    }
}

private static int QueryIndex(int[] array, int left, int right)
{
    //把第一个元素当作被比较的元素
    var temp = array[left];
    while(left < right)
    {
        //从右边直到找到比temp小的数跳出循环
        while (left < right && array[right] >= temp)
            right--;
        array[left] = array[right];

        //从左边直到找到比temp大的数跳出循环
        while (left < right && array[left] <= temp)
            left++;
        array[right] = array[left];
    }

    array[left] = temp;

    return left;
}    

分析

  1. 最好的时间复杂度是O(nlog2n)。
  2. 最坏的时间复杂度是O(n2)。

源码地址: https://github.com/woniuSnail/BaseAlgorithm.git

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/snailZz/p/13691312.html