快速排序—一种使用D&C的排序算法

算法原理

快速排序是对冒泡排序算法的改进，基本思想是：选择一基准元素，以此将剩余元素中的小于该基准元素的值放在左边，大于该基准元素的值放在右边；然后再在左侧序列和右侧序列做同样的处理操作；以此类推，直至各个序列都剩余一个元素时，即排序完成。

算法实现步骤

  • 首先设定一基准值（pivot），通过该基准值将待排序序列分成左右两部分。
  • 将小于或等于基准值的元素放在序列左边，将大于基准值的元素放在序列的右边。此时左边序列的元素都是小于基准值的，右边的元素都是大于基准值的，这个基准值就叫做分区(partition)操作。
  • 此时，左边和右边的序列均可看作是新的序列，分别对左边、右边的序列进行基准值的选择，将序列再次分成两部分，同样的，左边部分的元素值小于基准值，右边部分的元素值大于基准值。
  • 重复上述操作，通过递归-recurive将左侧部分排好序后，在递归对右边进行排序，当左右两个部分个数据排序完成后，整个序列再次组合加起来就形成了一个有序的序列了。

    代码实现

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    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)


    print(quicksort([1, 5, 2, 12, 34, 9]))

关于复杂度

快速排序算法的性能高度依赖于基准值的选取。在上述代码中是将第一个元素作为基准值，且要处理的数据是有序的。它并不会检查数据的有序性，只会按部就班的进行排序操作。
最糟糕情况下，所有的元素都是已经排好序的，但此时算法仍会按照步骤进行排序，且选择的基准值是第一个元素，所花费的时间较长，复杂度为O(n²)；最好的情况是已排好序的序列，每次选取序列的中间位置元素作为基准值，这样复杂度大大减小，为O(nlogn)。

快速排序算法动图展示