快速排序（python）

深碍√TFBOYSˉ_ 2022-03-07 10:56 226阅读 0赞

# 前言 #

基于前面介绍的桶排序和冒泡排序的缺点，我们提出了快速排序，快速排序是以首个数字作为基准，将整个输入分为两部分，左边小于这个基准，右边大于这个基准；重复操作这个，就可以根据这个基准不断进行划分输入数据，最终会实现分类的功能

一趟快速排序的算法是：

1）设置两个变量i、j，[排序][Link 1]开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A\[0\]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A\[j\]，将A\[j\]和A\[i\]互换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A\[i\]，将A\[i\]和A\[j\]互换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A\[j\]不小于key,4中A\[i\]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

# 代码实现 #

1 def quicksort(array, start, end):
      2     key = array[start]
      3     i, j = start, end
      4     if start >= end:
      5         return
      6     while i != j:
      7         # 找到右边第一个小于基准的数
      8         while (array[j]>=key) and (i<j):
      9             j -= 1
     10         # 找到左边第一个大于基准的数
     11         # i += 1
     12         while (array[i]<=key) and (i<j):
     13             i += 1
     14         # 如果找到了那么就进行交换
     15         if i < j:
     16             temp = array[j]
     17             array[j] = array[i]
     18             array[i] = temp
     19 
     20     # 结束之后将基准与中间值进行交换
     21     temp = array[start]
     22     array[start] = array[i]
     23     array[i] = temp
     24     print(array)
     25     quicksort(array, start, i-1)
     26     quicksort(array, i+1, end)
     27 
     28 
     29 if __name__ == '__main__':
     30     array = [6, 33, 5, 6, 4, 6, 2, 8, 3]
     31     quicksort(array, 0, len(array)-1)
     32     print(array)
    ~

快速排序在每次交换的过程中不会向冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了，因此总的比较和交换的次数就变少了，速度自然就提高了；当然在最坏的情况下，仍然是相邻的两个数进行交换，因此快速排序的最坏最坏时间复杂度和冒泡排序是一样的，都是O(N\*2)，它的平均时间复杂度是O(NlogN)

[Link 1]: http://baike.baidu.com/view/58783.htm