【算法】快速排序 Quick Sort

算法介绍

快速排序，又称分割交换排序，是目前公认的最佳排序算法，核心思想是在数列中找一个数作为中介点，将比中介点小的数放到数列的左边（将不比中介点小的数放到数列的右边，两者是同时成立的，只要记住一个就好），把中介点放到相应的位置上，再对左右两边的数列进行同样操作直到两边最多包含一个数字。

视频演示

视频地址：https://www.bilibili.com/video/av18980345

python代码

#-*- coding: utf-8 -*-

# 升序
def quick_sort(data):
    if len(data)<=1:
        return data
    pivot = data[-1] # 取最后一个数作为pivot
    i = 0 # i记录比pivot小的数的个数
    j = 0 # j用来遍历整个数列
    n = len(data)

    while j < n-1:
        if data[j]<pivot: # 比pivot小的数都放在前面
            data[i], data[j] = data[j], data[i]
            i += 1 
        j += 1

    data[i], data[-1] = data[-1], data[i] # 将pivot放在第 i 个位置

    if i>0:
        # 比 pivot 小的数据不为空，则对其进行快速排序
        data[:i] = quick_sort(data[:i])
    if i+1<n:
        # 比 pivot 大的数据不为空，则对其进行快速排序
        data[i+1:] = quick_sort(data[i+1:])

    return data

if __name__ == '__main__':
    data = [10, 80, 30, 90, 40, 50, 70]
    sorted_data = quick_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

快速排序的时间复杂度为：O(n^2)