算法原理
- 分区（Partition）： 选择一个基准元素，将数组分为两个子数组，小于基准的放在左边，大于基2准的放在右边。
- 递归排序： 对左右两个子数组分别进行快速排序。
- 合并： 不需要实际的合并操作，因为在分解和递归排序阶段已经完成了排序。
算法描述
快速排序是一种基于分治思想的高效排序算法，由英国计算机科学家 Tony Hoare 于1960年提出。它的核心思想是选择一个基准元素，将数组分成两个子数组，小于基准的在左边，大于基准的在右边，然后对子数组进行递归排序。这一过程持续进行，直到整个数组有序。
算法原理可以简要概括为以下步骤：
- 选择基准元素： 从待排序的数组中选择一个元素作为基准（pivot）。选择基准的方法有多种，常见的包括选择第一个元素、最后一个元素、中间元素，或者随机选择一个元素。
- 分区过程： 将数组中的其他元素按照与基准的大小关系划分到基准的两侧，使得基准左边的元素都小于基准，右边的元素都大于基准。这个过程称为分区（partition）。具体的分区算法有多种，其中一种常见的是
Lomuto分区方案和Hoare分区方案。
- Lomuto分区方案： a. 从左到右遍历数组，将比基准小的元素放到基准的左侧。 b. 使用一个索引i来记录当前小于基准的元素的位置，初始时i指向数组的起始位置。 c. 遇到小于基准的元素时，将它与索引i指向的元素交换，并将i递增。 d. 最后，将基准元素与索引i指向的元素交换，这样基准元素就放置在了其最终的位置。
- Hoare分区方案： a. 使用两个指针，一个从数组的左端移动到右端，另一个从右端移动到左端，分别找到大于和小于基准的元素。 b. 交换这两个元素的位置。 c. 重复这个过程，直到两个指针相遇。最后，基准元素的位置就是两指针相遇的位置。
- 递归排序： 对基准左右两侧的子数组分别递归地应用快速排序算法。即，对左侧的子数组和右侧的子数组分别进行步骤1和步骤2，直到每个子数组只有一个元素，此时整个数组就是有序的。
- 合并结果：不需要实际的合并操作，因为在分区和递归排序阶段已经完成了排序。
动画演示
能看懂动画你就理解了快速排序
代码实现
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 获取分区索引
int partitionIndex = partition(arr, low, high);
// 递归排序左右子数组
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
// 选择最右边的元素作为基准
int pivot = arr[high];
// 将小于基准的元素移动到左边，大于基准的元素移动到右边
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
// 将基准元素放到正确的位置
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}算法复杂度
时间复杂度（最坏） | 时间复杂度（最好） | 时间复杂度（平均） | 空间复杂度 | 稳定性 |
O(n^2) | O(n log n) | O(n log n) | O(log n) | 不稳定 |
- 最好情况：在最优情况下，快速排序的时间复杂度是O(n log n)。这通常发生在每次分区都能将数组均匀地分成两半的情况下。
- 平均情况：在平均情况下，快速排序的时间复杂度是O(n log n)。这是因为每次分区都将数组分成两部分，每一部分都需要O(log n)次分区操作。
- 最坏情况：最坏情况下的时间复杂度是O(n^2)，当每次分区都选择最大或最小的元素作为基准时，会导致分区不均衡。
- 空间复杂度：快速排序是一种原地排序算法，它不需要额外的存储空间来存储临时数据。因此，其空间复杂度是O(1)。这是因为所有的操作都是在输入数组上进行的，只需要常数级别的辅助空间用于存储一些变量，如循环索引、基准元素等。
快速排序的优化方式
快速排序是一种高效的排序算法，但在某些情况下可能面临最坏情况，即分区不均衡，导致性能下降。
- 随机选择基准元素：在每次排序开始时，随机选择数组中的一个元素作为基准元素，而不是固定选择第一个或最后一个元素。这可以避免在某些情况下导致最坏情况发生。
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 随机选择基准元素
int randomIndex = getRandomIndex(low, high);
swap(arr, randomIndex, high);
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private static int getRandomIndex(int low, int high) {
Random random = new Random();
return random.nextInt(high - low + 1) + low;
}- 三数取中法：选择基准元素时，不是简单地选择第一个或最后一个元素，而是选择第一个、中间和最后一个元素中的中间值作为基准元素。
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 三数取中法选择基准元素
int mid = low + (high - low) / 2;
int pivotIndex = getMedianIndex(arr, low, mid, high);
swap(arr, pivotIndex, high);
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
private static int getMedianIndex(int[] arr, int i, int j, int k) {
if ((arr[i] - arr[j]) * (arr[k] - arr[i]) >= 0) {
return i;
} else if ((arr[j] - arr[i]) * (arr[k] - arr[j]) >= 0) {
return j;
} else {
return k;
}
}这两种优化方式可以在某些情况下提高快速排序的性能，特别是在面对特定输入数据的时候。随机选择基准和三数取中法都有助于减少最坏情况的发生概率，提高算法的鲁棒性。
相关概念
• 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
• 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
• 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
• 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。