package com.zq.sf;
/**

• 快速排序
• 关键点
• 通过数组下标开始 i = l ; 下标结束 j= h ,待排序的数组int source [] ,key 关键字
• 通过下标 i(++)开始向后遍历 找到第一个比 key 大的A[i] ,将 A[i] = A[j]
• 通过下标j(--)开始向前遍历 找到比key 小的第一个小于key换 A[j] =A[i]
• @author zhangqi
• @version 1.0, 2018-12-4
• @since 1.0, 2018-12-4
  */

public class quickSortTest {

public static void main(String[] args) {
     int [] source = {1,3,9,4,5,6,7,8,2};
     int low = 0 ;
     int high = source.length-1;
     
     quickSort(low, high, source);
     
     for(int i = 0; i<source.length; i++){
         System.out.println(source[i]);
     }
    
}

public static void quickSort(int low ,int high,int []source ) {
    
    int start = low;
    int end = high;
    int key = source[low];
    
    while(end>start){
        //从后往前进行比较
        while(end > start && source[end] > key){
            end --;
        }
        if (source[end] <= key) {
            int temp = source[end];
            source[end] = source[start];
            source[start] = temp;
        }

        //从前往后进行比较
        while (end > start && source[start] < key ){
            start ++ ;  
        }

        if (source[start] >= key) {
            int temp = source[start];
            source[start] = source[end];
            source[end] = temp;

        }

/* for(int i = 0; i<source.length; i++){
System.out.print(source[i]);
}*/
//此时第一次循环比较结束,关键值的位置已经确定了,左边的值都比关键值小,右边的值都比关键值打,
//但两遍的顺序还有可能不一样,进行下面的递归

        //递归(前部分)
        if(start > low){
            quickSort(low,start-1,source);
        }
        //递归(后部分)
        if(end < high){
            quickSort(end+1,high, source);
        }
        
    }
}

}