排序算法——快速排序

介绍

快速排序（Quicksort），又称分区交换排序（partition-exchange sort），是一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序 n {\displaystyle n} n个项目要   O ( n log ⁡ n ) {\displaystyle \ O(n\log n)}  O(nlogn)（大O符号）次比较。在最坏状况下则需要 O ( n 2 ) {\displaystyle O(n^{2})} O(n2)次比较，但这种状况并不常见。事实上，快速排序 Θ ( n log ⁡ n ) {\displaystyle \Theta (n\log n)} Θ(nlogn)通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

算法

快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。 步骤为：

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。 选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

代码 void quick_sort(int *arr, int left, int right) { LOG_TAG; int i = left, j = right, pivot_v = arr[left]; while (i <= j) { while (arr[i] < pivot_v) i++; while (arr[j] > pivot_v) j--; if (i <= j) { std::swap(arr[i], arr[j]); i++; j--; } } if (left < j) quick_sort(arr, left, j); if (right > i) quick_sort(arr, i, right); } 算法复杂度

平均时间复杂度 Θ ( n log ⁡ n ) {\displaystyle \Theta (n\log n)} Θ(nlogn) 最坏时间复杂度 Θ ( n 2 ) {\displaystyle \Theta (n^{2})} Θ(n2) 最优时间复杂度 Θ ( n log ⁡ n ) {\displaystyle \Theta (n\log n)} Θ(nlogn) 空间复杂度 根据实现的方式不同而不同

参考

快速排序