简介
QuickSort 是一种分治(Divide-and-Conquer)排序算法。它的工作原理是从数组中选择一个「基准」(pivot)元素,然后将其他元素根据是否小于或大于基准元素划分为两个子数组。接着,递归地对子数组进行排序。QuickSort 的平均时间复杂度为 O(n log n)。需要注意的是,QuickSort 不是一种稳定的排序算法,也就是说,相等元素的相对位置可能不会保持不变。
QuickSort 是一种分治(Divide-and-Conquer)排序算法。它的工作原理是从数组中选择一个「基准」(pivot)元素,然后将其他元素根据是否小于或大于基准元素划分为两个子数组。接着,递归地对子数组进行排序。QuickSort 的平均时间复杂度为 O(n log n)。需要注意的是,QuickSort 不是一种稳定的排序算法,也就是说,相等元素的相对位置可能不会保持不变。
在这一步中,你需要导入 java.util.Arrays
类。这个类包含了一些用于操作数组的方法,这些方法将用于将 int
数组转换为 String
。
import java.util.Arrays;
定义一个名为 partition()
的辅助方法。partition()
方法将接收一个数组 arr
、一个起始索引 low
和一个结束索引 high
作为输入。partition()
方法会选择一个元素作为基准(pivot),并将数组中的元素进行划分,使得所有小于基准元素的元素位于基准的左侧,所有大于基准元素的元素位于基准的右侧。基准元素将被放置在其正确的位置。
partition()
方法将返回划分后的元素的索引。划分后的元素是基准元素被放置的位置。
public static int partition(int[] arr, int low, int high) {
// 选择基准元素
int pivot = arr[high];
int i = (low - 1); // 较小元素的索引,表示当前找到的基准的正确位置
for (int j = low; j <= high - 1; j++) {
// 如果当前元素小于或等于基准
if (arr[j] <= pivot) {
i++; // 增加较小元素的索引
// 交换 arr[i] 和 arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换 arr[i + 1] 和 arr[high]
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回划分索引
}
定义一个名为 quicksort()
的排序方法。quicksort()
方法将接收一个数组 arr
、一个起始索引 low
和一个结束索引 high
作为输入。quicksort()
方法会递归地对 arr[]
数组进行排序。
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
// pi 是划分索引,arr[p] 现在位于正确的位置
int pi = partition(arr, low, high);
// 递归地对划分前后的元素进行排序
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
创建并分配需要排序的整数数组到 arr
字段。
int[] arr = {7, 9, 1, 2, 10, 15, 6};
调用 quickSort()
方法,将 arr
字段作为输入,同时传入数组的起始索引和结束索引。使用 Arrays.toString(arr)
方法对数组进行排序并显示结果。
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
使用具有不同特征的数组测试你的快速排序实现。
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
在这一步中,我们需要在每次迭代中随机选择基准值,以避免最坏情况的发生。为此,我们将更新 partition()
方法,并将以下代码行:
int pivot = arr[high];
替换为以下代码行:
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
使用随机基准值测试你的快速排序实现。
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
在这一步中,我们将覆盖快速排序可以处理的边界情况。将这些边界情况定义为整数数组。
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
以下是 Java 实验中的快速排序完整代码。
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;
int i = low - 1;
for (int j = low; j <= high - 1; ++j) {
if (arr[j] <= pivot) {
++i;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {
return;
}
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
public static void main(String[] args) {
System.out.println("Quick Sort Implementation in Java\n-----------------------");
int[] arr = {7, 9, 1, 2, 10, 15, 6};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};
quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);
System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));
int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};
quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);
System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));
int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);
System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));
}
}
本实验提供了在 Java 中实现快速排序算法的分步指南。我们了解到,选择基准值是快速排序中的关键步骤,而不同的基准值选择技术会影响算法的性能。快速排序最适合用于排序大量数据。快速排序的最坏时间复杂度为 O(N^2),而其平均和最佳时间复杂度为 O(NLogN)。