八十一、最快最优的快速排序和优化

昵称10087950 2022-07-26 发布于江苏

展开全文

作者丨小sen

来源丨Python之王

「@Author：Runsen」

❝
编程的本质来源于算法，而算法的本质来源于数学，编程只不过将数学题进行代码化。「---- Runsen」
❞

快速排序

不久前，我在牛客中看到这样一个笑话，面试官让他写一个快速排序，结果他写了一个冒泡排序，虽说不是计算机专业的，还一直说没有写错，都不知道面试官为什么这么PASS。其实，一共有十大排序算法，最快最稳定的就是快速排序，简称快排。

quicksort 可以说是应用最广泛的排序算法之一，它的基本思想是分治法。基础的快速排序算法思想很简单，核心就是一句话：找到基准值的位置。

具体的过程其实和把大象装进冰箱这个问题一样，都可以分成三步：

「第一步，选择一个值作为基准值。」

「第二步，找到基准值的位置，并将小于基准值的元素放在基准值的前面，大于基准值的元素放在基准值的后面。」

「第三步，对基准值的左右两侧递归地进行这个过程。」

以 arr = [ 8, 1, 4, 6, 2, 3, 5, 7 ]为例，选择一个支点, index= (L+R)/2 = (0+7)/2=3, 支点的值 pivot = arr[index] = arr[3] = 6，接下来需要把 arr 中小于 6 的移到左边，大于 6 的移到右边，最后然后对基准值的左右两侧递归地进行这个过程。

快速排序最好用递归的代码实现，代码简单可读性前。

def quick_sort(b):
    """快速排序"""
    if len(b) < 2:
        return arr
    # 选取基准，随便选哪个都可以，选中间的便于理解
    mid = arr[len(b) // 2]
    # 定义基准值左右两个数列
    left, right = [], []
    # 从原始数组中移除基准值
    b.remove(mid)
    for item in b:
        # 大于基准值放右边
        if item >= mid:
            right.append(item)
        else:
            # 小于基准值放左边
            left.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

def quicksort(array):
  if len(array) < 2:
    # 基本情况下，具有0或1个元素的数组是已经“排序”的
    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([10, 5, 2, 3]))

快排优化

快排优化的方法就是：「合理选择pivot。」。我们知道，如果基准值选取不合理的话，快速排序的时间复杂度有可能达到这个量级，也就是退化成和选择排序、插入排序等算法一样的时间复杂度。只有当基准值每次都能将排序区间中的数据平分时，时间复杂度才是最好情况下的 O(nlogn)。

关于基准值选取的一个优化策略，「三点取中法。」

谓三点取中法，就是每一轮取排序区间的头、尾和中间元素这三个值，然后把它们排序以后的中间值作为本轮的基准值。调整要选取的这三个值的位置。

我们就以上图为例，假设本轮的三个值分别为 2、9、7，中间值是 7，所以，本轮的基准值就是 7。

快排优化：「更快地分区」。快速排序的做法是从左向右依次与 pivot 比较，做交换，这样做其实效率并不高。

举个简单的例子，一个数组 [2, 1, 3, 1, 3, 1, 3]，选第一个元素作为 pivot 是2，每次发现比2小的数会引起一次交换，一共三次。

然而，直观来说，其实只要将第一个3和最后一个1交换就可以达到这三次交换的效果。所以更理想的分区方式是从「两边向中间遍历」的双向分区方式，而不是从左到右，当然前提是基准值选择数组的中位数。

具体快速排序优化的代码如下所示。

'''
@Author：Runsen
@WeChat：RunsenLiu
@微信公众号：Python之王
@CSDN：https://blog.csdn.net/weixin_44510615
@Github：https://github.com/MaoliRUNsen
@Date：2020/12/21
'''
def quick_sort(nums, start, end):
    if start >= end:
        return
    pivot = nums[start]  # 基准值
    low = start  # 左指针
    high = end  # 右指针
    while low < high:
        while low < high and nums[high] >= pivot:
            high -= 1
        nums[low] = nums[high]

        while low < high and nums[low] < pivot:
            low += 1
        nums[high] = nums[low]
    nums[low] = pivot
    quick_sort(nums, start, low - 1)
    quick_sort(nums, low + 1, end)

if __name__ == '__main__':
    nums = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    quick_sort(nums, 0, len(nums) - 1)
    print(nums)

快速排序的名字起的是简单粗暴，因为一听到这个名字你就知道它存在的意义，就是快，而且效率高！它是处理大数据最快的排序算法之一了，而且Python内置的sorted就是快速排序。

虽然 Worst Case 的时间复杂度达到了O(n²)，比如说顺序数列的快排。但是就是优秀，在大多数情况下都比平均时间复杂度为 O(n logn)的排序算法表现要更好，，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。