使用单遍历指针与两个左右指针的java快速排序分区逻辑
我已经实现了如下的快速排序。在分区逻辑中,我在任何地方都看到了两个指针(通过指针我不希望指的是C/C++指针,但要遍历的简单变量),一个从开始遍历数组(查找大于pivot的元素),另一个从结束遍历数组(查找小于pivot的元素)
两个指针遍历的元素之和为N,即传递给分区逻辑的数组部分的大小
为了方便起见,我只使用了一个指针,开始遍历元素,从开始到距离轴元素所在的末端少一步。我假设我的轴心位置在起始位置,所以我保留另一个变量来存储轴心索引。如果我发现任何元素小于我的pivot元素,那么我在假设的pivot索引和当前遍历的索引之间进行交换,并将pivot-index增加1。在循环结束时,我准备好了旋转的位置,然后返回
我只想知道,与从两端遍历传递给分区逻辑的数组的方法相比,我的方法是否有缺点[在左遍历中找到较大的元素,在右遍历中找到较小的元素,然后交换这两个元素,继续这样做,直到左遍历指针和右遍历指针相互交叉]
请帮忙。 谢谢&;问候
package com.algorithm.sorting;
public class QuickSort {
public static void main(String[] args) {
int a[] = { 5, 33, 45454, 43254, 2, 67, 8, 78, 8, 8, 8, 85654, 5, 4, -1, -1, 1, 234, 24, 43, 4, -7, 45, 4, -5,
544, 9, 8, 7, 6, 5, 4, 3, 2, 11, 2, 3, 4, 5, 6, 7, 8, 9 };
quicksort(a);
for (Integer i : a) {
System.out.println(i);
}
}
public static void quicksort(int[] array) {
quicksort(array, 0, array.length - 1);
}
private static void quicksort(int[] array, int start, int end) {
if (start < end) {
int pivotIndex = partition(array, start, end);
quicksort(array, start, pivotIndex - 1);
quicksort(array, pivotIndex + 1, end);
}
}
private static int partition(int[] array, int start, int end) {
int pIndex = start;
int mid = start + ((end - start) / 2);
int temp = array[mid];
array[mid] = array[end];
array[end] = temp;
int pivot = array[end];
for (int i = start; i <= end - 1; i++) {
if (array[i] < pivot) {
temp = array[i];
array[i] = array[pIndex];
array[pIndex] = temp;
pIndex++;
}
}
array[end] = array[pIndex];
array[pIndex] = pivot;
return pIndex;
}
}
(该程序与我在http://krishnalearnings.blogspot.in/2015/07/implementation-in-java-for-quicksort.html中发布的程序相同,但现在我头脑中有了这种困惑,我希望纠正我自己和我发布的内容)
# 1 楼答案
pivot index是第二个指针,因此该算法具有相同的基本属性。但是,请注意,它可能不太稳定:刚刚超过枢轴索引的值可能会被交换,即使它小于枢轴,而传统算法会保留它