快速排序算法定义
快速排序算法，英文是Quick Sort，是一种常见且高效的排序算法。
快速排序算法思想
快速排序基于分治（Divide and Conquer）的思想，通过不断地将数组分成两个子数组，并对子数组进行递归排序，最终将整个数组有序化。
主要分为如下步骤：
1、第一步：挑选基准
从数列中挑出一个元素，称为 “基准”，通常是数组中的某个元素。
2.第二步：分区操作
将数组中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在右边，这一步称为分区（Partition）操作。
3.第三步：递归操作
递归地把小于基准值元素的子数组和大于基准值元素的子数组排序，直到整个数组有序。
快速排序算法示例
假设有一个未排序的整数数组 [7, 2, 1, 6, 8, 5, 3, 4]。
首先，选择基准元素
选择基准元素，通常选择第一个或最后一个元素，这里选择第一个元素 7。
然后，进行分区操作
比 7 小的元素放在左边，比 7 大的元素放在右边：
[2, 1, 6, 5, 3, 4] 7 [8]
现在，我们分别对左右两个子数组进行递归排序。
对于左边的子数组 [2, 1, 6, 5, 3, 4]，选择基准元素 2，再次进行分区操作：
[1] 2 [6, 5, 3, 4]
继续递归排序，直到所有子数组都有序，最终整个数组变得有序。
快速排序算法优缺
优点：
- 在平均情况下，快速排序具有良好的性能，通常比其他常见的排序算法（如冒泡排序和插入排序）快得多。
- 快速排序适用于大型数据集和通用排序需求。
缺点：
- 在最坏情况下，快速排序的性能可能下降为 O(n^2)，这在已经有序或近乎有序的数组上发生，但可以通过一些优化手段来改善。
- 快速排序不适用于小型数组，因为递归调用的开销可能会显著影响性能。
快速排序算法实现
以下是一个使用Java编写的快速排序算法示例：
public class QuickSort {
public static void main(String[] args) {
int[] arr = {7, 2, 1, 6, 8, 5, 3, 4};
quickSort(arr, 0, arr.length - 1);
System.out.println("Sorted Array:");
for (int num : arr) {
System.out.print(num " ");
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
// 递归排序左边的子数组
quickSort(arr, low, pivotIndex - 1);
// 递归排序右边的子数组
quickSort(arr, pivotIndex 1, high);
}
}
public 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; // 返回基准元素的索引
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
这个示例演示了如何实现快速排序算法，这个示例的输出将是排序后的数组 [1, 2, 3, 4, 5, 6, 7, 8]。
快速排序算法总结
总之，快速排序是一种强大的排序算法，常用于实际应用中，特别是处理大型数据集。
mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
后台回复【架构】即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》