package util;
public class Pub {
public static void beforeSort(int[] arr){
System.out.println("before sort: ");
for(int i:arr){
System.out.print(i+" ");
}
System.out.println();
}
public static void afterSort(int[] arr){
System.out.println("after sort: ");
for(int i:arr){
System.out.print(i+" ");
}
}
}
以0位为基准 代码如下：
package swap;
import java.util.Arrays;
import util.Pub;
public class FastSort {
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,38,65,97,76,13,27};
Pub.beforeSort(a);
quick(a);
Pub.afterSort(a);
}
private static int getMiddle(int[] arr,int left,int right){
int base=arr[left]; //关键一点 当从左边第一个数作为基数的时候，先从右边开始判断
while(left<right){
while(left<right&&arr[right]>=base){
right--;
}
arr[left]=arr[right];
while(left<right&&arr[left]<=base){
left++;
}
arr[right]=arr[left];
}
arr[left]=base;
return left;
//System.out.println(left);
}
private static void quickSort(int[] a, int low, int high) {
if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
int middle = getMiddle(a,low,high);
quickSort(a, 0, middle-1);
quickSort(a, middle+1, high);
}
}
private static void quick(int[] a) {
if(a.length>0){
quickSort(a,0,a.length-1);
}
}
}
运行结果：
before sort:
1 38 65 97 76 13 27
after sort:
1 13 27 38 65 76 97
以末尾为基准，代码如下：
package swap;
import java.util.Arrays;
import util.Pub;
public class FastSortReverse {
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,38,65,97,76,13,27};
Pub.beforeSort(a);
quick(a);
Pub.afterSort(a);
}
private static int getMiddle(int[] arr,int left,int right){
// 关键一点 选数组哪边开始作为基数点进行比较，需要从另一头开始进行判断,否则会进行错误的替换。
int base=arr[right];
while(left<right){
while(left<right&&arr[left]<=base){
left++;
}
arr[right]=arr[left];
while(left<right&&arr[right]>=base){
right--;
}
arr[left]=arr[right];
}
//因为这种方法 总是会将最初的base基准数字覆盖掉，所以 需要找到合适的地方，放入基准数字。
arr[left]=base;
return left;
//System.out.println(left);
}
private static void quickSort(int[] a, int low, int high) {
if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
int middle = getMiddle(a,low,high);
quickSort(a, 0, middle-1);
quickSort(a, middle+1, high);
}
}
private static void quick(int[] a) {
if(a.length>0){
quickSort(a,0,a.length-1);
}
}
}
运行结果：
before sort:
1 38 65 97 76 13 27
after sort:
1 13 27 38 65 76 97