2022年 11月 8日

Python实现快速排序

Python实现快速排序

一、快速排序简介

快速排序(Quick Sort)是一种效率很高的排序算法,是对冒泡排序的一种改进排序算法。

快速排序首先任意选取一个数据(通常选待排序列表中的第一个数)作为基准数据,将待排序列表中的数据分割成独立的两部分,所有比基准数据小的数都放到它左边,所有比基准数据大的数都放到它右边,此时基准数据排序完成,第一轮快速排序完成。然后再按此方法对两部分的数据分别进行快速排序,整个排序过程可以递归进行,直到被分割的数据只有一个或零个时,递归结束,列表排序完成。

快速排序的名字起得简单直接,因为这种排序算法速度快,效率高,是处理大数据最快的排序算法之一。

二、快速排序原理

快速排序的原理如下:

1. 从待排序列表中选取一个基准数据(通常选取第一个数据)。

2. 将待排序列表中所有比基准数据小的元素都放到基准数据左边,所有比基准数据大的元素都放到基准数据右边(升序排列,降序反之)。用基准数据进行分割操作后,基准数据的位置就是它最终排序完成的位置,第一轮排序完成。

3. 递归地对左右两个部分的数据进行快速排序。即在每个子列表中,选取基准,分割数据。直到被分割的数据只有一个或零个时,列表排序完成。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。列表的初始状态如下图。

要进行升序排列,则每轮排序都将比基准数据小的数据放在左边,比基准数据大的数据放在右边。

1. 从待排序列表中任意选一个数据作为基准数据 mid_data,然后设置两个游标 left 和 right,分别指向列表的起始数据和末尾数据。将游标right的数据与基准数据比较,如果大于或等于基准数据,则right往左移动。基准数据为10,21大于10,right左移。

2. 当游标right的数据小于基准数据时,right停止移动,将游标right指向的数据赋值给游标left。然后将游标left的数据与基准数据比较,如果小于基准数据,则left往右移动。right移动到5时小于10,停止移动并将5赋值给left,left开始右移。

3. 当游标left的数据大于或等于基准数据时,left停止移动,将游标left指向的数据赋值给游标right。然后将游标right的数据与基准数据比较,如果大于或等于基准数据,则right往左移动。left移动到17时大于10,停止移动并将17赋值给right,right开始左移。

4. 重复步骤2,right移动到7时小于10,停止移动并将7赋值给left,left开始右移。

5. 重复步骤3,left移动到50时大于10,停止移动并将50赋值给right,right开始左移。

6. 当left与right相遇时,移动结束,将基准数据10赋值给相遇的位置,此时第一轮排序完成,列表被基准数据分割成了两个子列表,基准数据10的位置就是排序完成时的位置。

7. 递归地对分割的两个子列表进行相同的操作。以左表为例,取第一个数据5作为基准数据,设置两个游标left和right指向子表的起始和末尾,将游标right的数据与基准数据比较,如果大于或等于基准数据,则right往左移动。

8. 左表中只有两个数据,经过一次移动,left和right就相等了,移动结束,左表排序完成。对右表也使用相同方法进行递归,这里就不再赘述了。

9. 继续进行多轮递归排序,每一轮当子表只有一个或零个数据时(left>=right),递归结束。排序结果如下图。

三、Python实现快速排序

  1. # coding=utf-8
  2. def quick_sort(array, start, end):
  3. if start >= end:
  4. return
  5. mid_data, left, right = array[start], start, end
  6. while left < right:
  7. while array[right] >= mid_data and left < right:
  8. right -= 1
  9. array[left] = array[right]
  10. while array[left] < mid_data and left < right:
  11. left += 1
  12. array[right] = array[left]
  13. array[left] = mid_data
  14. quick_sort(array, start, left-1)
  15. quick_sort(array, left+1, end)
  16. if __name__ == '__main__':
  17. array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
  18. quick_sort(array, 0, len(array)-1)
  19. print(array)

运行结果:

[5, 7, 10, 15, 17, 21, 24, 27, 30, 36, 45, 50]

在代码中,先将列表中的第一个数据作为基准数据mid_data,设置两个游标left和right分别标记待排序列表起始和末尾的数据。然后按照上面分析的步骤,left和right两个游标交替向中间移动,当left与right相遇时,将mid_data赋值给相遇位置的索引。此时完成了分割,mid_data左边子表中的数据都小于基准数据,右边子表中的数据都大于基准数据,第一轮排序完成。然后递归对左右两个子列表执行相同操作,递归结束的条件就是列表的长度小于2时(start>=end),此时直接返回。

快速排序除了需要传入待排序列表以外,还需要传入排序的开始索引和结束索引,也就是说快速排序可以指定排序列表中的部分数据,在递归的时候就是排序部分数据。

快速排序也可以使用非递归的方式实现,在非递归实现时,代码思路不变,但必须借助栈或队列,代码会稍微长一点。

四、快速排序的时间复杂度和稳定性

1. 时间复杂度

在快速排序中,最坏的情况是元素列表的初始状态是完全逆序排列的,这使得每次分割所得的子表中一个为空表,另一个的长度为原表的长度减1,所以需要进行 n 轮分割,每一轮需要进行 n/2 次比较。时间复杂度为 T(n)=n(n-1)/2 ,再乘每次操作的步骤数(常数,不影响大O记法),所以快速排序的时间复杂度为 O(n^2) 。

与时间复杂度是 O(n^2) 的其他排序算法相比,为什么快速排序的效率会比其他排序算法高呢?因为时间复杂度计算的是最坏情况的时间复杂度,但最坏的情况并不常见。快速排序的最优时间复杂度是 Ο(nlogn) ,很容易改变取基准数据的方法避免最坏情况的发生(如“三者值取中”),去接近最优时间复杂度。

2. 稳定性

在快速排序中,每轮排序会将数据与基准数据进行比较和分割。如果有相等的数据,可以自己决定将相等的数据放在左边还是右边(上面的代码是右边),不会影响排序结果。

在快速排序的实现过程中,有两个游标从列表的两边向中间移动,游标right向左移动的过程中,如果数据小于基准数据,则会将数据赋值给left游标。在这个过程中,如果有相等的数据,相对位置很可能会发生变化,如 [10, 5, 5] 。所以快速排序是一种不稳定的排序算法。