当前位置：首页 > news >正文

java算法：快速排序

news 来源：原创 2024/9/21 0:47:12

快速排序是一种常用的排序算法，它利用分治的思想将一个数组分成两个子数组，然后递归地对子数组进行排序，最终将整个数组排序完成。

快速排序的基本思想如下：

选择一个基准元素（pivot），通常选择数组的第一个或最后一个元素。
将数组分成两个部分，使得左边的元素都小于等于基准元素，右边的元素都大于基准元素。这个过程称为分区（partition）。
对左右两个部分分别递归地进行快速排序。
合并左右两个部分，得到最终的排序结果。

以下是用Java实现快速排序的示例代码：

public class QuickSort {public static void quickSort(int[] arr) {quickSort(arr, 0, arr.length - 1);}private 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);}}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;}public static void main(String[] args) {int[] arr = {4, 2, 6, 8, 3, 1, 5, 7};quickSort(arr);System.out.println("Sorted array:");for (int num : arr) {System.out.print(num + " ");}}
}

在上述代码中，quickSort()方法是快速排序的入口方法，它调用了私有的辅助方法quickSort()和partition()。quickSort()方法通过递归调用对子数组进行排序，而partition()方法用于将数组分区并返回基准元素的最终位置。

可以看到，快速排序算法成功地对数组进行了排序。快速排序的平均时间复杂度为O(nlogn)，其中n是数组的长度。

快速排序的优点：

高效：快速排序的平均时间复杂度为O(nlogn)，其中n是数组的长度，是一种较快的排序算法。
原地排序：快速排序使用了原地排序，不需要额外的空间来存储临时数据，只需要对数组进行原地交换操作。快速排序的缺点：

快速排序的缺点：

不稳定性：在分区过程中，相同元素的相对顺序可能会改变，因此快速排序是一种不稳定的排序算法。
对于特定的输入情况，快速排序的性能可能会下降。当输入数组已经有序或近乎有序时，快速排序的时间复杂度会退化到O(n^2)，其中n是数组的长度。为了避免这种情况，可以采用一些优化技巧，如随机选择基准元素或使用三数取中法来选择基准元素。

随机选择基准元素：

在每次分区之前，随机选择数组中的一个元素作为基准元素。
这样可以降低出现最坏情况的概率，使得快速排序的期望时间复杂度更接近O(nlogn)。

private static void quickSort(int[] arr, int low, int high) {if (low < high) {// 随机选择基准元素int randomIndex = low + new Random().nextInt(high - low + 1);swap(arr, randomIndex, high);// 分区操作，返回基准元素的最终位置int pivotIndex = partition(arr, low, high);// 递归排序基准元素左边的子数组quickSort(arr, low, pivotIndex - 1);// 递归排序基准元素右边的子数组quickSort(arr, pivotIndex + 1, high);}
}

三数取中法选择基准元素：

从待排序数组的起始、中间和末尾位置各选取一个元素。
对这三个元素进行排序，并选择其中位于中间位置的元素作为基准元素。
这样可以尽量选择一个接近中间值的元素作为基准元素，减少最坏情况的概率。

private static void quickSort(int[] arr, int low, int high) {if (low < high) {// 三数取中法选择基准元素int mid = low + (high - low) / 2;if (arr[low] > arr[mid]) {swap(arr, low, mid);}if (arr[mid] > arr[high]) {swap(arr, mid, high);if (arr[low] > arr[mid]) {swap(arr, low, mid);}}// 分区操作，返回基准元素的最终位置int pivotIndex = partition(arr, low, high);// 递归排序基准元素左边的子数组quickSort(arr, low, pivotIndex - 1);// 递归排序基准元素右边的子数组quickSort(arr, pivotIndex + 1, high);}
}