算法原理
- 分区(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,直到每个子数组只有一个元素,此时整个数组就是有序的。
- 合并结果:不需要实际的合并操作,因为在分区和递归排序阶段已经完成了排序。
动画演示
能看懂动画你就理解了快速排序
好吧,可能这个图不好理解,看个视频讲解把>>>B站小姐姐讲解快速排序
代码实现
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的函数。