在乱序的世界中,快速排序如同一位智慧的园丁,
以轻盈的手法,将无序的花朵们重新安排,
在每一次比较中,沐浴着理性的阳光,
终使它们在有序的花园里,开出绚烂的芬芳。
快速排序是一种高效的排序算法,它采用了分治的策略。它的基本思想是选择一个基准值,将数组分为两个子数组,一个子数组中的所有元素都小于基准值,另一个子数组中的所有元素都大于基准值,然后对这两个子数组递归地进行排序。
具体来说,快速排序的步骤如下:
快速排序的关键在于分割操作,通过这个操作,它可以将一个大问题分解成两个规模较小的子问题,然后分别解决,最终达到整体有序的目的。
快速排序是由英国计算机科学家 Tony Hoare
在
1960
1960
1960 年代提出的。Hoare 最初将这一算法称为 “分区交换排序”,后来更广泛地称为快速排序。他的灵感来自于合并排序和插入排序。
场景假设:我们需要将下列无序序列使用快速排序按从小到大进行排序。
快速排序的流程如下:
// 快速排序入口
void quickSort(int[] arr, int low, int high) {
if (low < high) {
// 对数组进行分区操作
int pivot = partition(arr, low, high);
// 递归排序左半部分
quickSort(arr, low, pivot - 1);
// 递归排序右半部分
quickSort(arr, pivot + 1, high);
}
}
// 分区操作
int partition(int[] arr, int low, int high) {
// 选择最后一个元素作为 pivot
int pivot = arr[high];
int i = low - 1; // 指向小于 pivot 的区域的边界
// 遍历数组,将小于 pivot 的元素放到左侧
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将 pivot 放到正确位置
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
// 返回 pivot的位置
return i + 1;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
// 调用快速排序算法
quickSort(arr, 0, arr.length - 1);
// 输出排序后的数组
System.out.print("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
算法时间复杂度分析:
情况 | 时间复杂度 | 计算公式 | 公式解释 |
---|---|---|---|
最好情况 | O ( n l o g n ) O(nlogn) O(nlogn) | T ( n ) = 2 T ( n 2 ) + n T(n) = 2T(\frac{n}{2}) + n T(n)=2T(2n)+n | 在最优情况下,每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 2 T ( n 2 ) 2T(\frac{n}{2}) 2T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 2 T ( n 2 ) + n 2T(\frac{n}{2}) + n 2T(2n)+n |
平均情况 | O ( n l o g n ) O(nlogn) O(nlogn) | T ( n ) = T ( n 2 ) + T ( n 2 ) + n T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + n T(n)=T(2n)+T(2n)+n | 在平均情况下,我们假设每次划分都能将数组均匀地分成两部分。因此,我们有两个大小为 n 2 \frac{n}{2} 2n 的子问题,所以有 T ( n 2 ) + T ( n 2 ) T(\frac{n}{2}) + T(\frac{n}{2}) T(2n)+T(2n)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n 2 ) + T ( n 2 ) + n T(\frac{n}{2}) + T(\frac{n}{2}) + n T(2n)+T(2n)+n |
最坏情况 | O ( n 2 ) O(n^2) O(n2) | T ( n ) = T ( n − 1 ) + n T(n) = T(n - 1) + n T(n)=T(n−1)+n | 在最坏情况下,每次划分只能将数组划分为一份有 n − 1 n - 1 n−1 个元素,另一份有 0 0 0 个元素。因此,我们有一个大小为 n − 1 n - 1 n−1 子问题,所以有 T ( n − 1 ) T(n - 1) T(n−1)。然后,我们需要 n n n 的时间来进行划分操作。所以,总的时间复杂度就是 T ( n − 1 ) + n T(n - 1) + n T(n−1)+n |
快速排序具有以下特性:
不稳定的
,即相同元素在排序后可能会改变相对位置。快速排序是一种非常重要且高效的排序算法,适用于各种数据类型和应用场景。其原地性、高效性以及简单直观的实现使得它成为了排序算法中的经典之作。