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);
}
}
}
}
