快速排序

一颗蔬菜 2019-08-20 PM 120℃ 1条

快速排序

本文参考并修改自Mr.Seven大佬的博客

1、基本思想

快速排序的基本思想:挖坑填数+分治法

从原序列中选取一个基准值,通过一次排序把小于或等于的元素放在基准值的左边,把大于或等于基准值的元素放在基准值的右边。这样,整个序列就分成了两个不同的序列。然后对两个子序列继续进行这样的排序,试想在不断的递归过程中,原序列不断地被分成子序列,不断地整体有序,当子序列只剩下俩个元素时,它们就是局部有序的,且此时原序列整体有序。
quick-sort09.gif

2、算法描述

快速排序使用分治策略来把一个序列(list)分为两个子序列(sub-lists)。步骤为:

①. 从数列中挑出一个元素,称为”基准”(pivot)。
②. 重新排序数列,所有比基准值小的元素摆放在基准前面,所有比基准值大的元素摆在基准后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
③. 递归地(recursively)把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归到最底部时,数列的大小是零或一,也就是已经排序好了。这个算法一定会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

3、代码实现

递归原地分治
public int[] quicksort(int[] array,int low, int high){
    if (array.length <= 0)
        return;
    if (low > high)
        return;
    int left = low;
    int right = high;
    int tmp = array[left]; // 保存基准值,把基准值的位置空出来,产生空位1
    
    while (left < right) {
        while (left < right && array[right] >= tmp) { // 从后往前查找比基准值小的值
            right--;
        }
        array[left] = array[right] // 把比基准值小的值插入到基准值的位置  填空位1,产生空位2
        System.out.println(Arrays.toString(array));
        while (left < right && array[left] <= tmp) { // 从前往后找
            left++;
        }
        array[right] = array[left]; // 把比基准值大的值插入到比基准值大的位 填空位2, 产生空位3
        System.out.println(Arrays.toString(array));
    }
    array[left] = tmp;  // 填空位3
    System.out.println(Arrays.toString(array));
    quicksort(array, low, left-1)
    quicksort(array, left + 1, high)
}

以上是Java描述的快速排序,在已经理解快速排序地情况下,理解上面代码是不难的。若不理解,可以参考下面的python描述。

def quicksort(array):
    if (len(array) < 2):  # 基准条件
        return array
    else:                 # 递归条件
        pivot = array[0]  
        less = [i for i in array[1:] if i < pivot] # 比基准值小的子数组
        greater = [i for i in array[1:] if i > pivot] # 比基准值大的子数组
        return quicksort(less) + [pivot] + quicksort[greater]

4.快速排序算法复杂度:

平均时间复杂度最好情况最坏情况空间复杂度
O(nlog₂n)O(nlog₂n)O(n²)O(1)(原地分区递归版)

快速排序排序效率非常高。 虽然它运行最糟糕时将达到O(n²)的时间复杂度, 但通常平均来看, 它的时间复杂为O(nlogn), 比同样为O(nlogn)时间复杂度的归并排序还要快. 快速排序似乎更偏爱乱序的数列, 越是乱序的数列, 它相比其他排序而言, 相对效率更高.

Tips: 同选择排序相似, 快速排序每次交换的元素都有可能不是相邻的, 因此它有可能打破原来值为相同的元素之间的顺序. 因此, 快速排序并不稳定.

标签: 算法

非特殊说明,本博所有文章均为博主原创。

上一篇 算法稳定性
下一篇 国庆出行规划


唉呀 ~ 仅有一条评论


  1. alimy
    alimy

    递归一层就要增加一层堆栈开销,空间复杂度似乎不应该是O(1).
    最好情况是logn层,空间复杂度最好的情况是O(logn)
    最差的情况是n层,空间复杂度对应最差的时候是O(n)

    回复 2019-08-23 16:44