当涉及到处理重复元素的快速排序时,可以使用荷兰国旗问题的方法,也就是三路划分。下面是使用 Java 实现的示例代码:
import java.util.Arrays;public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low < high) {int[] pivotIndices = partition(arr, low, high);quickSort(arr, low, pivotIndices[0] - 1);quickSort(arr, pivotIndices[1] + 1, high);}}public static int[] partition(int[] arr, int low, int high) {int pivot = arr[low];int smaller = low;int equal = low;int larger = high;while (equal <= larger) {if (arr[equal] < pivot) {swap(arr, smaller, equal);smaller++;equal++;} else if (arr[equal] == pivot) {equal++;} else {swap(arr, equal, larger);larger--;}}return new int[]{smaller, larger};}public 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 = {3, 6, 8, 2, 3, 8, 4, 6, 3, 2};System.out.println("Original Array: " + Arrays.toString(arr));quickSort(arr, 0, arr.length - 1);System.out.println("Sorted Array: " + Arrays.toString(arr));}
}
这段代码实现了一个快速排序算法,其中的 quickSort
方法用于递归地进行排序,partition
方法用于进行三路划分(小于、等于和大于 pivot)。在 main
方法中,展示了如何使用这个快速排序算法对含有重复元素的数组进行排序。
运行此 Java 代码将对数组进行排序,并保持重复元素的相对顺序。