快速排序是一种广泛应用的排序算法,其平均时间复杂度为O(n log n),最坏情况下为O(n^2)。快速排序的基本思想是通过一个“基准”元素将数组分为两个子数组,使得左边子数组的所有元素都小于基准元素,而右边子数组的所有元素都大于基准元素,然后递归地对这两个子数组进行排序。
快速排序的步骤
-
选择基准:从数组中选择一个元素作为基准,常见的选择方式有选择第一个元素、最后一个元素或者随机选择一个元素。
-
分区:通过一次遍历将数组按照基准元素分成左右两部分,左边部分小于基准,右边部分大于基准。同时我们还需要记录基准元素最后的位置。
-
递归排序:对左右两部分数组分别进行快速排序,直到数组的长度为1或者0为止。
快速排序的Java实现
以下是一个简单的Java实现:
public class QuickSort {
// 主函数
public static void main(String[] args) {
int[] array = {10, 7, 8, 9, 1, 5};
int n = array.length;
quickSort(array, 0, n - 1);
System.out.println("排序后的数组:");
printArray(array);
}
// 快速排序主函数
static void quickSort(int[] array, int low, int high) {
if (low < high) {
// 找到基准元素的位置
int pivotIndex = partition(array, low, high);
// 递归排序左侧
quickSort(array, low, pivotIndex - 1);
// 递归排序右侧
quickSort(array, pivotIndex + 1, high);
}
}
// 分区函数,返回基准元素的最终位置
static int partition(int[] array, int low, int high) {
int pivot = array[high]; // 选择基准元素为最后一个元素
int i = (low - 1); // 小于基准元素的最后一个元素的索引
for (int j = low; j < high; j++) {
// 如果当前元素小于或等于基准元素
if (array[j] <= pivot) {
i++;
// 交换array[i]和array[j]
swap(array, i, j);
}
}
// 将基准元素放到正确的位置
swap(array, i + 1, high);
return i + 1; // 返回基准元素的位置
}
// 交换函数
static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
// 打印数组
static void printArray(int[] array) {
for (int value : array) {
System.out.print(value + " ");
}
System.out.println();
}
}
代码解析
-
主函数:在
main
函数中,我们定义了一个待排序的数组,并调用quickSort
函数进行排序。 -
快速排序函数:
quickSort
函数实现了快速排序的主干逻辑,采用递归的方式对左侧和右侧子数组进行排序。 -
分区函数:
partition
函数的职责是将数组分为两个部分,并返回基准元素的最终位置。该函数通过遍历数组与基准元素进行比较,并逐步调整数组元素的位置。 -
交换函数:
swap
函数用于交换数组中两个元素的值。 -
打印数组函数:用于打印排序后的数组。
总结
快速排序以其简单的实现和优越的性能在实际应用中得到了广泛的使用。尽管在最坏情况下它的时间复杂度为O(n^2),但通过合理选择基准元素,快速排序在平均情况下表现出色,是许多标准库中排序算法的基础。