目录

该算法主要包含三个步骤

选择枢轴点

分区算法

Lomuto分割算法的工作原理及图示

快速排序算法示意图

快速排序算法的复杂度分析

快速排序的优势

快速排序的缺点

快速排序的应用

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。

快速排序是一种基于分治法的排序算法，它选择一个元素作为枢轴，并将给定数组围绕该枢轴进行划分，最终将枢轴放置在排序数组中的正确位置。

该算法主要包含三个步骤

选择枢轴元素：从数组中选择一个元素作为枢轴元素。枢轴元素的选择可以是多种多样的（例如，第一个元素、最后一个元素、随机元素或中位数）。

对数组进行分区：围绕中心元素重新排列数组。分区后，所有小于中心元素的元素都将位于中心元素的左侧，所有大于中心元素的元素都将位于中心元素的右侧。

递归调用：递归地对两个分区子数组应用相同的过程。

基本情况：当子数组中只剩下一个元素时，递归停止，因为单个元素已经排序。

​

选择枢轴点

选择枢轴点有很多不同的方法。

• 始终选择第一个（或最后一个）元素作为枢轴。下面的实现选择最后一个元素作为枢轴。这种方法的缺点是，当数组已经排序时，最终结果会非常糟糕。
• 随机选择一个元素作为枢轴点。这种方法更可取，因为它不存在导致最坏情况发生的固定模式。
• 选择中位数作为枢轴元素。就时间复杂度而言，这是一种理想的方法，因为我们可以在线性时间内找到中位数，并且配分函数总是会将输入数组分成两半。但由于中位数查找的常数较大，因此平均耗时更长。

分区算法

快速排序的关键步骤是分区（partition()）。分区有三种常用的算法。所有这些算法的时间复杂度都是 O(n)。

1. 朴素分区：这里我们创建数组的副本。首先放入所有较小的元素，然后放入所有较大的元素。最后将临时数组复制回原始数组。这需要 O(n) 的额外空间。
2. Lomuto分区：本文使用了这种分区方法。这是一个简单的算法，它跟踪较小元素的索引并不断交换索引。之所以选择它，是因为它简单易用。
3. 霍尔分割法：这是所有分割方法中最快的。它从数组的两侧遍历，不断将左侧较大的元素与右侧较小的元素交换，但数组本身并未被分割。详情请参阅霍尔分割法与洛穆托分割法的比较。

以上红色部分参考链接：

以第一个元素为枢轴元素实现快速排序
C++ C++ (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序_c++ pivot-CSDN博客
C语言 C语言 (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
Java Java (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
Python Python (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
C# C# (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客
JavaScript JavaScript (Implement Quicksort with first element as pivot)以第一个元素为枢轴元素实现快速排序-CSDN博客

使用随机枢轴的快速排序
C++ C++ (QuickSort using Random Pivoting)使用随机枢轴的快速排序_霍尔分区-CSDN博客
C语言 C语言 (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
Java Java(QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
Python Python (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
C# C# (QuickSort using Random Pivoting)使用随机枢轴的快速排序-CSDN博客
JavaScript JavaScript (QuickSort using Random Pivoting)使用随机枢轴的快速排序_quick pivot(快速枢轴)插件-CSDN博客

数组的中位数
C++ C++ (Median of an Array)数组的中位数_c++如何查找数组中间元素-CSDN博客
Java Java (Median of an Array)数组的中位数-CSDN博客
Python Python (Median of an Array)数组的中位数-CSDN博客
C# C# (Median of an Array)数组的中位数_c#求数组中值-CSDN博客
JavaScript JavaScript (Median of an Array)数组的中位数_js 计算数组中位数-CSDN博客

朴素划分算法
C++ C++ (Naive Partition Algorithm)朴素划分算法-CSDN博客
C语言 C语言 (Naive Partition Algorithm)朴素划分算法-CSDN博客
Java Java (Naive Partition Algorithm)朴素划分算法-CSDN博客
Python Python (Naive Partition Algorithm)朴素划分算法-CSDN博客
C# C# (Naive Partition Algorithm)朴素划分算法-CSDN博客
JavaScript JavaScript (Naive Partition Algorithm)朴素划分算法-CSDN博客

Lomuto分区算法
C++ C++ Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
C语言 C语言 Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
Java Java Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
Python Python Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
C# C# Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客
JavaScript JavaScript Lomuto分区算法(Lomuto Partition Algorithm)-CSDN博客

霍尔分区算法
C++ C++ 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
C语言 C语言 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
Java Java 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
Python Python 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
C# C# 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客
JavaScript JavaScript 霍尔分区算法(Hoare‘s Partition Algorithm)-CSDN博客

Lomuto分割算法的工作原理及图示

逻辑很简单，我们从最左边的元素开始，并将小于（或等于）当前元素的索引记为i。遍历过程中，如果找到更小的元素，则将当前元素与arr[i]交换。否则，忽略当前元素。

让我们借助以下示例来理解分区算法的工作原理：

快速排序算法示意图

在上一步中，我们了解了分区过程如何根据选定的枢轴元素重新排列数组。接下来，我们将相同的方法递归应用于枢轴元素左右两侧的较小子数组。每次，我们都选择新的枢轴元素并再次分区数组。此过程持续进行，直到只剩下一个元素为止，该元素始终是有序的。一旦每个元素都位于其正确的位置，整个数组就排序完成了。

下图展示了递归方法如何调用枢轴元素左右两侧的较小子数组：

示例代码：

#include <stdio.h>

void swap(int* a, int* b);

// partition function
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], &arr[j]);
}
}

// Move pivot after smaller elements and
// return its position
swap(&arr[i + 1], &arr[high]);
return i + 1;
}

// The QuickSort function implementation
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);
}
}

void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}

int main() {
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, n - 1);
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

输出

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 用于基本数据类型）。
• 对数据库中的记录进行排序，以便更快地进行搜索。
• 需要排序输入的算法的预处理步骤（例如，二分查找、双指针技术）。
• 使用快速选择（快速排序的一种变体）查找第 k 个最小/最大的元素。
• 根据多个键（自定义比较器）对对象数组进行排序。
• 数据压缩算法（如霍夫曼编码预处理）。
• 图形学和计算几何（例如，凸包算法）。

更多详情请参阅快速排序的应用。

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。