[Java] 纯文本查看 复制代码
package sort;
public class QuickSort {
/**
* @param args
*快速排序：每次排序都将分为两半，左边的全部都小于基准元素，右边的都大于基准数组，
*/
public static void main(String[] args) {
int [] arr = {91,23,15,65,12,9,49,98};
ergodic(arr);
quickSort(arr, 0, arr.length - 1 );
ergodic(arr);
}
public static int [] quickSort(int [] arr , int start ,int end){
int i = start , j = end;//获取首位和末位元素的索引
int pivot = arr [start];//基准元素，通常将首位元素作为基准元素，三方变量（只存值不交换）
int emptyIndex = i;//将首位元素的索引放入空位中，
while( i < j){//start从左往右遍历，end从右往左遍历
while( i < j && pivot <= arr[j]){//基准元素从后往前比，寻找小于基准元素的元素,
j--;//没找到时，继续循环
}
//找到了小于基准元素的元素跳出循环
if( i < j ){//start 和 end 没有相遇时
arr[emptyIndex] = arr[emptyIndex = j];
//emptyIndex = j只作用于[]中，等号左边的emptyIndex的值还是0
//本行代码执行完后emptyIndex 的值是 j
//覆盖后arr[j]相当于空出来了，可以被直接覆盖
}
while( i < j && pivot >= arr){//基准元素从前往后比，寻找大于于基准元素的元素
i++;//没找到时，继续循环
}
//找到了大于基准元素的元素跳出循环
if( i < j ){//start 和 end 没有相遇时
arr[emptyIndex] = arr[emptyIndex = i];//直接覆盖arr[j]
// j
}
// i 直接覆盖arr
arr[emptyIndex] = pivot;//start 和 end 相遇后(start == end)将pivot 赋给 空位元素
if( i - start > 1){//i 和 start不相邻时，执行（不相邻时说明还有元素没有遍历到）
quickSort(arr, 0, i-1);//递归调用快速排序，对基准元素左边的所有元素进行排序
}
if( end - j > 1 ){//end 和 j 不相邻时执行（不相邻时说明还有元素没有遍历到）
quickSort( arr, j + 1, end);//递归调用快速排序，对基准元素右边的所有元素进行排序
}
}
return arr;
}
public static void ergodic(int [] arr){
System.out.print("数组元素:");
for(int i = 0 ; i < arr.length ; i ++){
System.out.print(arr + " ");
}
System.out.println();
}
}
