我有基于以下场景的过去一年的问题：
当要排序的项目列表包含大量重复值时，我们可以通过将所有等于枢轴的值分组到中间来改进QuickSort，然后我们递归地QuickSort左边的那些值和右边的那些值。对分区方法进行必要的更改以实现该目的。
这是目前使用的实现：
// Quick Sort algorithm
public class QuickSort {
public static void quickSort(int[] a) {
quickSort(a, 0, a.length-1);
}
private static void quickSort(int[] a, int i, int j) {
if (i < j) {
int pivotIdx= partition(a, i, j);
quickSort(a, i, pivotIdx-1);
quickSort(a, pivotIdx+1, j);
}
}
private static void swap(int[] a, int pos1, int pos2) {
int temp = a[pos1];
a[pos1] = a[pos2];
a[pos2] = temp;
}
private static int partition(int[] a, int i, int j) {
// partition data items in a[i..j]
int p = a[i]; // p is the pivot, the i-th item
int m = i; // Initially S1 and S2 are empty
for (int k=i+1; k<=j; k++) { // process unknown region
if (a[k] < p) { // case 2: put a[k] to S1
m++;
swap(a,k,m);
}
}
swap(a,i,m); // put the pivot at the right place
return m; // m is the pivot's final position
}
public static void printArray(int[] a) {
for (int i = 0; i < a.length; i++)
System.out.print(a[i] + " ");
System.out.println();
}
public static void main(String[] args) {
int[] arr = { 7, 12, 3, 5, -6, 3, 8, 2, 10, -3 };
printArray(arr);
quickSort(arr);
printArray(arr);
}
}
我对这里介绍的quicksort算法有一些基本的了解，但我真的不明白这个问题是否真的给了我一个如何实现算法的提示，因为在我看来，quicksort必须遍历列表来制作2个分区，动态决定位置X放置枢轴的位置，在此实现中选择它作为输入数组的最左边元素。如果这个位置X是动态决定的，你究竟是如何“将等于枢轴的元素组合到中间”，以及它如何改进算法呢？
主要思想是使用三向分区策略解决此问题。有关详细信息，请参阅Dutch National Flag Problem。
如果你有很多重复元素，那么你的快速排序会尝试将每个重复元素分别放在正确的位置。但你不需要这样做。
让我们看一下我在上述声明中所声称的一个例子：
假设你有一个像{4,6,4,3,4,2,5,4,1,4}这样的数组。在这个数组中，你有重复5次的元素4。当应用快速排序，并将4放在正确的位置时，您将数组分成2个部分，使得左侧部分包含小于或等于4的所有元素（但没有特定的顺序），右侧部分包含所有元素比4更大的元素。但那是'天真的方法。
让我们看看我们如何改进这一点（鉴于我们有很多重复的元素）
当您的快速排序找到4并且它对数组进行分区以将此4放置在正确的位置时，您还可以跟踪所有相等的元素（数组的其他元素等于4）以及左侧和更大的较小值在右边。
因此，当分区而不是有2个索引left和right（子阵列0到left包含小于或等于枢轴和子阵列left到right的所有元素包含大于枢轴和right到len(array)-1的所有元素是元素还有待探索），你可以有3个索引，描述如下：
[0,left) - 元素等于pivot的子数组[left, mid) - 元素大于pivot的子数组[mid, right] - 尚待探索的元素。通过这种方式，您修改的快速排序将仅使用数据轮次数较少（具体而言，等于数组中唯一元素的数量）。因此，递归调用次数会减少。
因此，此解决方案利用特定输入的情况，其中有许多重复项（因此，您的数组中的重复元素越多，此快速排序的修改变体将执行的效果越好）
给我看一些代码。
[right, len(array))上面代码的输出是：
import java.util.Arrays;
import java.util.stream.IntStream;
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{2, 3, 4, 1, 2, 4, 3, 5, 6, 2, 2, 2, 1, 1, 1};
quickSort(arr);
System.out.print("Sorted array: ");
Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
System.out.println();
}
public static void quickSort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
private static void quickSort(int[] arr, int start, int end) {
if (start > end)
return; // base condition
System.out.print("Recursive call on: ");
IntStream
.rangeClosed(start, end)
.map(i -> arr[i])
.forEach(i -> System.out.print(i + " "));
System.out.println();
int n = arr.length;
if (start < 0 || start >= n || end < 0 || end >= n)
throw new IllegalArgumentException("the indices of the array are not valid");
int pivot = arr[end];
/*
[start,left) - sub-array with elements lesser than pivot
[left, mid) - sub-array with elements equal to pivot
[mid, right] - sub-array with elements greater than pivot
[right, end) - elements yet to be explored.
*/
int left = start, mid = start, right = start;
while (right != end) {
if (arr[right] < pivot) {
swap(arr, left, right);
swap(arr, mid, right);
left++;
right++;
mid++;
} else if (arr[right] == pivot) {
swap(arr, mid, right);
mid++;
right++;
} else if (arr[right] > pivot) {
right++;
}
}
swap(arr, mid, right);
System.out.println("Placed " + pivot + " at it's correct position");
System.out.println();
quickSort(arr, start, left - 1);
quickSort(arr, mid + 1, end);
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
上面的输出清楚地表明，在将枢轴放置在正确的位置之后，我们在两个不同的阵列上进行递归，但是这两个阵列中没有一个具有前一个枢轴。 （这是优化）