/*
* 快速排序：选一个值pivokey(一般是第一个),小于pivokey放在左边，大于pivokey放在右边，分成两个序列，递归直到low >= high
* 步骤：
* 1，设定两个指针low,high。初值是0和数组长度-1，指定关键字pivokey
* 2，从high所指的位置向前找，找到一个比pivokey小的，和关键字交换值(arr[low] = arr[high])
* 3，从low所指的位置向后找，找到一个比pivokey大的，和关键字交换值
* 4，直到low>=high，把关键字赋值arr[low]=pivokey
* 5，递归分出的两个序列[lowStart,low-1] [low+1,highEnd]
* */
public class QuickSortTest2{
public static int[] quickSort(int[] arr, int low, int high) {
//为后面的递归使用
int lowStart = low;
int highEnd = high;
if (low < high) {
int pivokey = arr[low];
while (low < high) {
//如果都是大于pivokey，high指针往前移
while (low < high && arr[high] > pivokey) {
high--;
}
//这里low++是先把arr[low]赋值为arr[high]，再low+=1，因为这个值是比pivokey小的，下一次不用比较了
if (low < high)
arr[low++] = arr[high];
//如果都是小于pivokey，low指针往后移
while (low < high && arr[low] < pivokey) {
low++;
}
//这里的high--和上面同理
if (low < high)
arr[high--] = arr[low];
}
arr[low] = pivokey;
quickSort(arr, lowStart, low - 1);
quickSort(arr, low + 1, highEnd);
}
return arr;
}
public static void main(String[] args){
int[] a={2,1,4,5,7,1,9,3};//等待排序的数组值可以有重复
for(int a1: a)
{
System.out.print(a1 + " ");
}
System.out.println();
int index = a.length;
a=QuickSortTest2.quickSort(a,0,a.length-1); // qucikly sort
for(int a1: a)
{
System.out.print(a1 + " ");
}
}
}