快速排序是一种基于分治的排序算法，它选择一个元素作为枢轴，并通过将该枢轴置于排序后的数组中正确位置来划分。
该算法主要包含三个步骤：
选择枢轴：从数组中选择一个元素作为枢轴。枢轴的选择可以有所不同（例如，第一元素、最后元素、随机元素或中位数）。
数组划分：重新排列数组围绕枢轴。划分后，所有小于枢轴的元素位于其左侧，所有大于枢轴的元素位于其右侧。
递归调用：递归地将相同进程应用于两个分区子数组。
基础情况：当子数组中只剩一个元素时，递归停止，因为单个元素已被排序。
枢轴选择
选择枢轴有很多不同的选择。
始终选择第一个（或最后一个）元素作为枢轴。下面的实现选择了最后一个元素作为枢轴。这种方法的问题在于，最坏的情况往往是数组已经排序好。
随机选一个元素作为枢轴。这是一种首选方法，因为它没有最坏情况发生的模式。
选择中位数元素是枢轴。从时间复杂度角度看，这是一种理想的方法，因为我们可以在线性时间内找到中位数，且配分函数总是将输入数组分为两半。但平均来说需要更多时间，因为中位数的发现常数很高。
划分算法
快速排序中的密钥进程是一个分区（）。 有三种常见的划分算法。所有这些算法的时间复杂度均为O（n）。
朴素划分：这里我们创建数组的副本。先放所有较小的元素，然后放更大的。最后，我们将临时数组复制回原始数组。这需要 O（n） 额外的空间。
洛穆托分区：本文中使用了该分区。这是一个简单的算法，我们跟踪较小元素的索引并不断交换。本文中我们使用它，因为它非常简单。
霍尔分区：这是所有分区中最快的。这里我们从两侧遍历数组，并在数组未分割的情况下不断交换左侧较大元素与右侧较小元素。详情请参阅Hoare对Lomuto的对决。
Lomuto划分算法的工作原理及示意图
逻辑很简单，我们从最左边的元素开始，并跟踪较小（或相等）元素的索引，作为 i。在遍历过程中，如果发现一个较小的元素，我们会将当前元素与 arr[i] 交换。否则，我们忽略当前元素。
重定向图标
让我们通过以下示例来理解分区算法的工作原理：
快速排序算法示意
在前一步，我们研究了分区过程如何根据所选枢轴重新排列数组。接下来，我们递归地将同样的方法应用到枢轴左右两个较小的子数组 。每次我们都选择新的枢轴点并再次划分数组。这个过程会持续，直到只剩下一个元素，并且总是被排序。一旦每个元素都处于正确位置，整个数组就被排序。
下图展示了递归方法如何调用枢轴左右两个较小子数组：
import java.util.Arrays; class GfG { // partition function static int partition(int[] arr, int low, int high) { // choose the pivot int pivot = arr[high]; // index of smaller element and indicates // the right position of pivot found so far int i = low - 1; // traverse arr[low..high] and move all smaller // elements to the left side. Elements from low to // i are smaller after every iteration for (int j = low; j <= high - 1; j++) { if (arr[j] < pivot) { i++; swap(arr, i, j); } } // Move pivot after smaller elements and // return its position swap(arr, i + 1, high); return i + 1; } // swap function static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // the QuickSort function implementation static void quickSort(int[] arr, int low, int high) { if (low < high) { // pi is the partition return index of pivot int pi = partition(arr, low, high); // recursion calls for smaller elements // and greater or equals elements quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } public static void main(String[] args) { int[] arr = {10, 7, 8, 9, 1, 5}; int n = arr.length; quickSort(arr, 0, n - 1); for (int val : arr) { System.out.print(val + " "); } } }输出
1 5 7 8 9 10
快速排序的复杂度分析
时间复杂性：
最佳情况：（Ω（n log n）），当枢轴元素将数组分为两个相等的一半时发生。
平均情况 （θ（n log n）），平均而言，枢轴将数组分为两部分，但不一定相等。
最坏情况：（O（n²）），当始终选择最小或最大元素作为枢轴时（例如，已排序的数组）。
辅助空间：
最坏情况：由于不平衡划分导致递归树倾斜，需要调用栈大小为 O（n） 的 O（n）。
最佳情况：由于平衡分区，O（log n） 生成了一个具有调用栈大小为 O（log n） 的平衡递归树。
详情请参阅快速排序的时间与空间复杂性分析。
快速排序的优势
它是一种分而治之的算法，使解决问题变得更容易。
它在大数据集上效率很高。
它开销低，只需少量内存即可运行。
它对缓存友好，因为我们在同一数组上进行排序，且不会将数据复制到任何辅助数组。
在不需要稳定性的情况下，是处理大数据的最快通用算法。
它是尾部递归的，因此所有尾调用优化都是可以完成的。
快速排序的缺点
其最坏时间复杂度为 O（n）2），当枢轴选择不当时，就会发生这种情况。
对于小型数据集来说，它并不是一个好的选择。
它不是稳定排序，意味着如果两个元素键相同，快速排序时它们的相对顺序不会在排序输出中保持，因为这里我们根据枢轴的位置交换元素（不考虑它们的原始位置）。
快速排序的应用
高效地在内存中排序大型数据集。
用于库的排序函数（如 C++ std：：sort 和 Java Arrays.sort 用于原语）。
在数据库中整理记录以加快搜索速度。
需要排序输入的算法中的预处理步骤（例如，二分搜索、两点技术）。
使用快速选择（Quicksort 的一种变体）找到第 k 个最小/最大的元素。
基于多个键（自定义比较器）排序对象数组。
数据压缩算法（如霍夫曼编码预处理）。
图形学和计算几何（例如凸包算法）。
编程资源 https://pan.quark.cn/s/7f7c83756948 更多资源 https://pan.quark.cn/s/bda57957c548
