常用的排序算法之快速排序（Quick Sort）
快速排序（Quick Sort）起源
快速排序是由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出的一种排序算法。它的基本思想是分治法（Divide and Conquer）的应用。
定义
快速排序是一种高效的排序算法，它采用分治法的策略，将一个大的数组分割成两个小的子数组，并使左边子数组的所有元素都小于右边子数组的元素，然后递归地对这两个子数组进行快速排序。
引伸义
快速排序的“快速”一词指的是它的平均时间复杂度较低，为O(n log n)，其中n是待排序数组的长度。然而，在最坏情况下，其时间复杂度会退化为O(n^2)。
优缺点
优点：
- 平均时间复杂度低，为O(n log n)。
- 原地排序算法，只需要O(log n)的额外空间（递归栈空间）。
- 可以处理大量数据。
缺点：
- 在最坏情况下，时间复杂度退化为O(n^2)。
- 不稳定排序算法，即相等的元素在排序后可能会改变顺序。
使用场景
快速排序适用于大多数排序场景，特别是当数据量较大时。然而，由于它的不稳定性，对于需要保持相等元素顺序的场合，可能需要考虑其他排序算法。
使用数据一步步举例
假设有一个数组[4, 2, 8, 9, 5, 7, 1, 3, 6]，我们选取第一个元素4作为基准（pivot）。
- 划分过程：
- 小于基准的元素放在左边。
- 大于基准的元素放在右边。
- 相等的元素可以放在任意一边。
划分后得到
[2, 1, 3, 4, 9, 7, 6, 8, 5]，其中基准4现在在中间位置。
- 递归处理左右子数组：
- 对左边子数组
[2, 1, 3]进行快速排序。 - 对右边子数组
[9, 7, 6, 8, 5]进行快速排序。
- 对左边子数组
- 合并：
- 由于左右子数组已经是有序的，所以直接合并即可得到最终排序结果
[1, 2, 3, 4, 5, 6, 7, 8, 9]。
- 由于左右子数组已经是有序的，所以直接合并即可得到最终排序结果
Java示例代码
代码语言：javascript代码运行次数：0运行复制public class QuickSort {
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int pivotIndex = partition(array, left, right);
quickSort(array, left, pivotIndex - 1);
quickSort(array, pivotIndex + 1, right);
}
}
private static int partition(int[] array, int left, int right) {
int pivot = array[left]; // 选择最左边的元素作为基准
int i = left + 1; // 从左边第二个元素开始扫描
for (int j = i; j <= right; j++) {
if (array[j] < pivot) {
// 交换array[i]和array[j]
swap(array, i, j);
i++;
}
}
// 将基准元素放到正确的位置
swap(array, left, i - 1);
return i - 1; // 返回基准元素的新位置
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {4, 2, 8, 9, 5, 7, 1, 3, 6};
quickSort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array)); // 输出: [1, 2, 3, 4, 5, 6, 7, 8, 9]
}
} 
发布评论