Question

下面的代码为快速排序，想请教一下parition方法中while(high>first&&list[high]>=pivot) high--;的作用

public class QuickSort {
public static void quickSort(int[] list) {
quickSort(list,0,list.length-1);
}

private static void quickSort(int[] list, int first, int last) {
if(last>first) {
int pivotIndex=parition(list,first,last);
quickSort(list,first,pivotIndex-1);//对上一主元左边的数组进行快排
quickSort(list,pivotIndex+1,last);//对上一主元右边的数组进行快排
}

}

private static int parition(int[] list,int first, int last) {
int pivot=list[first];
int low=first+1;
int high=last;

while(high>low) {
while(low<=high&&list[low]<=pivot)
low++;

while(low<=high&&list[high]>pivot)
high--;

if(high>low) {
int temp=list[high];
list[high]=list[low];
list[low]=temp;
}
}

while(high>first&&list[high]>=pivot)
high--;

if(pivot>list[high]) {
list[first]=list[high];
list[high]=pivot;
return high;
}
else
return first;
}

public static void main(String[] args) {
int[] a = new int[] {5,6,4,5,5,8,8,9,1,2};
quickSort(a);
for (int i = 0; i < a.length; ++i) {
System.out.print(a[i] + " ");
}
}

}

Answer 1

快速排序法是从两边往中间靠的，你说的那条语句作用为：如果高端大于等于枢轴，就把高端标志往前移，也就是往中间靠

追问

高端和枢轴是什么？能不能讲得通俗点，还有，为什么要往中间靠？

追答

最开始低端和高端就是第一个和最后一个元素，他们进行比较，把所有比枢轴大的元素都交换到后面，把所有比枢轴小的都交换到前面，到最后高端标志和低端标志在中间某个位置相遇，这时就能保证枢轴前的元素都比枢轴小，枢轴后的元素都比枢轴大