快速排序

快速排序也是交换排序的一种，因为它需要数据交换位置。

算法原理

通过一趟排序将要排序的数据分割为独立的两部分，其中一部分的所有数据比另外一部分都要小，按照这个方法对这两部分进行快速排序，整个排序过程递归进行，使整个数据变得有序。

import random
import time
def quick_sort(array):
    if len(array) <= 1: #终止条件，如果数组长度小于等于1，就不需要再进行分类，直接返回
        return array
    pivot=array[0]
    left=[x for x in array[1:] if x <pivot]     #小于中间值的值
    right=[x for x in array[1:] if x>=pivot]    #大于中间值的值
    return quick_sort(left)+[pivot]+quick_sort(right)   #递归返回

#生成10000个值在0~10000的随机数
myList=[random.random()*10000 for i in range(10000)]
start_time=time.time()
print(quick_sort(myList))
#统计使用时间
print(f"--- {time.time() - start_time} seconds ---")

可以看到时间只使用了 0.03322243690490723 seconds

复杂度分析

当数据有序的时候，每次都是一个分到全部数据一个分到0个数据，这个时候执行效率最低，需要遍历N次，内部循环也是N次，这个时候最坏情况下的时间复杂度就是O(N^2)，平均情况和最好情况都是分logN次，需要O(NlogN)的时间复杂度，空间复杂度为O(logN)，因为需要保存基准值。同时是不稳定的排序算法。