考虑如下数组,
int[] a = {100, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 16};
考虑到中间元素总是作为轴心。
pivot = 10
标准的快速排序算法如下所示
public void quickSort(int[] a, int low, int high) {
if (a == null || a.length == 0)
return;
if (low >= high)
return;
int pivotIndex = partition( a, low, high );
quickSort(a, low, pivotIndex-1);
quickSort(a, pivotIndex, high);
}
public int partition ( int[] a, int low, int high )
{
// pick the pivot
int middle = low + (high - low) / 2;
int pivot = a[middle];
while (low <= high) {
while (a[low] < pivot) {
low++;
}
while (a[high] > pivot) {
high--;
}
if (low <= high) {
swap( a, low, high );
low++;
high--;
}
}
return low;
}
完成while循环的一次迭代后(以10为中心),数组如下所示
high low
10 1 2 3 4 5 100 11 12 13 14 15 16
如您所见,pivot元素位于索引0处,这不是10的正确位置。
我的问题是,如何修改上述算法,以便在每次迭代结束时,pivot元素都位于正确的位置,并且在不考虑pivot的情况下继续在左半部分和右半部分递归
1条答案
按热度按时间vwoqyblh1#
如果目标是让pivot值在开始时处于正确的位置,那么代码可以对数组进行一次扫描,检查值是否小于、等于或大于pivot,例如生成三个计数:ltpivot=#elements<pivot value,eqpivot=#elements==pivot,gtpivot=#elements>pivot value(扫描只需要生成两个计数,第三个计数是(高+1-低-(计数的2))。然后所有的pivot值都应该移动到索引位置low+ltpivot到low+ltpivot+eqpivot-1。这可以通过另一个过程来完成,以将枢轴值交换到位。然后可以执行第三步,将小于或大于pivot的元素交换到pivot的左侧或右侧。
问题是,这种方法比标准快速排序慢,需要对阵列进行3次扫描,而标准快速排序只能进行一次扫描。标准的快速排序只会正确放置一个pivot元素,而将其他元素==pivot分散放置,但在典型情况下,这不是问题(标准快速排序的最坏情况之一是所有值都相同)。