O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

一、快速排序

快速排序（Quick Sort）是一种基于分治思想的排序算法，是目前使用最广泛的排序算法之一。其基本思想是选取一个基准元素，然后将数组分成小于等于基准的子数组和大于基准的子数组，再递归地对这两个子数组进行快速排序，最后将它们合并起来即可。

二、快速排序步骤

快速排序： 的核心操作是分割数组操作
划分操作采用两种方式：Lomuto 分割和 Hoare 分割。

• Lomuto 分割比较简单，但是在特定情况下会导致快速排序的时间复杂度退化为 O(n^2)
• Hoare 分割较为复杂，但是效率更高，通常被认为是优化后的快速排序算法 nlong

  复杂度
  最坏复杂度	n^2
  平均复杂度	nlong
  递归复杂度	nlong

快速排序的基本步骤：

1. 选择基准元素：从待排序数组中选择一个元素作为基准（通常选择第一个元素）
2. 分割数组： 重新排列数组，将所有小于基准的元素放在基准的左边，所有大于基准的元素放在基准的右边，等于基准的元素可以放在任意一边。此时，基准元素的位置也已经确定
3. 递归排序： 递归地对基准元素左边的子数组和右边的子数组进行快速排序
4. 合并结果： 将左边子数组、基准元素、右边子数组依次拼接起来，得到排好序的数组

三、应用例子

def quicksort(arr):# 如果数组长度小于等于1，则直接返回该数组if len(arr) <= 1:return arrelse:# 选择第一个元素作为基准pivot = arr[0]# 构造小于等于基准的元素构成的子数组 less  构造大于基准的元素构成的子数组 greaterless = [x for x in arr[1:] if x <= pivot]      # 输出比第一个元素小的列表greater = [x for x in arr[1:] if x > pivot]    # 输出比第一个元素大的列表print('less-----------', less)print('greater-----------', greater)# 递归地对这两个子数组进行快速排序，然后将它们合并起来，并加上基准元素return quicksort(less) + [pivot] + quicksort(greater)if __name__ == '__main__':arr = [3, 5, 2, 8, 1, 4]sorted_arr = quicksort(arr)print(sorted_arr)

1. 首先，检查数组的长度是否小于等于 1。如果是，则直接返回该数组，因为长度为 0 或 1 的数组已经是有序的。
2. 如果数组长度大于 1，则选择数组的第一个元素作为基准（pivot）。
3. 构造小于等于基准的元素构成的子数组 less 和大于基准的元素构成的子数组 greater。这里使用了列表推导式，它可以很方便地生成新列表。
4. 对 less 和 greater 递归地调用 quicksort 函数，这将对它们进行排序。
5. 最后，将 less 和 greater 排序后的结果合并起来，并加上基准元素，这就是最终的排序结果