快速排序（Python）

快速排序

排序算法	平均时间复杂度	空间复杂度	稳定性
冒泡排序	\(O(n^2)\)	\(O(1)\)	稳定
选择排序	\(O(n^2)\)	\(O(1)\)	不稳定
插入排序	\(O(n^2)\)	\(O(1)\)	稳定
希尔排序	\(O(n\log^2 n)\)	\(O(1)\)	不稳定
归并排序	\(O(n\log^2 n)\)	\(O(n)\)	稳定
快速排序	\(O(n\log n)\)	\(O(\log n)\)	不稳定
堆排序	\(O(n\log n)\)	\(O(1)\)	不稳定
计数排序	\(O(n+k)\)	\(O(k)\)	稳定
基数排序	\(O(n\times k)\)		稳定
桶排序	\(O(n)\)	\(O(m)\)	稳定

算法思路

快速排序是一个采用分而治之思路的递归算法，对于一个待排序数列，快速排序会从数列中挑出一个元素，称为“基准”(pivot)，将数列中所有比基准值小的元素移动到基准的前边，将所有比基准值大的元素移动到基准的后边，再递归的用该方法排序大于以及小于基准的子数列。

算法实现

话不多说直接上图！！！

def quick_sort(arr, start, end):
    if start >= end:
        return

    pivot = partition(arr, start, end)
    quick_sort(arr, start, pivot - 1)
    quick_sort(arr, pivot + 1, end)

def partition(arr, start, end):
    lt, pivot = start, end
    for i in range(start, end):
        if arr[i] < arr[pivot]:
            arr[lt], arr[i] = arr[i], arr[lt]
            lt += 1
    arr[lt], arr[end] = arr[end], arr[lt]
    return lt

图片及知识来源

«算法导论»第7章堆排序

---

本博客文章仅供博主学习交流，博主才疏学浅，语言表达能力有限，对知识的理解、编写代码能力都有很多不足，希望各路大神多多包涵，多加指点。