快速排序

快速排序（Quick sort）

  1.     快速排序是对递归的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。是对冒泡排序的一种改进。

算法思路

  1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；
  2. 将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
  3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理；
  4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

动画演示

9.6 快速排序 - 图1

代码实现

  1. def QS(nums):
  2.     if len(nums) >= 2:  # 递归入口及出口
  3.         mid = nums[len(nums) // 2]  # 选取基准值，也可以选取第一个或最后一个元素
  4.         left, right = [], []  # 定义基准值左右两侧的列表
  5.         nums.remove(mid)  # 从原始数组中移除基准值
  6.         for num in nums:    # 判断元素放左边还是右边
  7.             if num >= mid:
  8.                 right.append(num)
  9.             else:
  10.                 left.append(num)
  11.         return QS(left) + [mid] + QS(right)     # 递归
  12.     else:
  13.         return nums
  16. print(QS(nums=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]))
  1.     运行结果：
  1. [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
    排序过程：

[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

26
[3, 5, 15, 2, 4, 19] [44, 38, 47, 36, 27, 46, 50, 48]

2
[] [3, 5, 15, 4, 19]
15
[3, 5, 4] [19]
5
[3, 4] []
4
[3] []
27
[] [44, 38, 47, 36, 46, 50, 48]
36
[] [44, 38, 47, 46, 50, 48]
46
[44, 38] [47, 50, 48]
38
[] [44]
50
[47, 48] []
48
[47] []

[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

复杂度分析

    时间复杂度分析：快速排序过程分为两部分：分裂和移动。最好的情况：如果分裂总能把数据表分为相等的两部分，那么就是O(log n)的复杂度；而移动需要将每项都与中值进行比对，还是O(n)。综合起来就是O(nlog n)。而且，算法运行过程中不需要额外的存储空间。最坏的情况：每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)。

    空间复杂度：从空间性能上看，尽管快速排序只需要一个元素的辅助空间，但快速排序需要一个栈空间来实现递归。最好的情况下，即快速排序的每一趟排序都将元素序列均匀地分割成长度相近的两个子表，所需栈的最大深度为log(n+1)；但最坏的情况下，栈的最大深度为n。这样，快速排序的空间复杂度为O(logn)。

优缺点

    优点：通常认为在所有同数量级的排序算法中，快速排序的平均性能是最好的，这也是它被称为“快速排序”的原因。

    缺点：快速排序算法相比于其他排序算法来说比较耗费空间资源，因为快速排序需要栈空间来实现递归。而且快速排序的基准元素的选取非常重要，如果基准元素选取不当，可能影响排序过程的时间复杂度和空间复杂度

性能改进

    为了避免快速排序退化为冒泡排序以及递归栈过深等问题，通常依照“三者取中”的法则来选取基准元素。三者取中法是指在当前待排序的子序列中，将其首元素、尾元素和中间元素进行比较，在三者中取中值作为本趟排序的基准元素。

    我们也可以打乱原本的顺序，再进行快速排序。