很早之前就已经接触过快速排序算法了，面试当中也屡屡被问到，虽然明白其原理，但从未真正的用代码敲出来。
写关于算法的代码之前一定要原理想明白，不然就是盲目，在参考有关资料及自己的沉思之后，写出如下代码，中间出现了一些bug，但都很快解决了
如果有更好的优化算法，还请不吝赐教！！！！
源代码：
package com.zken.test;
/**
* @author iamzken
* 排序算法
* 使用快速排序算法对一个数组从小到大排序
* 2015-8-27 13:40
*/
public class Sorter {
//获取中间索引，该索引对应的关键字把数组分为左右两部分，其中，左边的都比该索引对应的关键字小，右边的都比该索引对应的关键字大
public static int getMiddle(int[] a , int left , int right){
//随机取一个关键字，这里取left索引对应的关键字,相当于left索引对应的位置被挖了一个”坑“，需要下面的程序填补这个”坑“
int key = a[left];
//临界条件
while(left < right){
//当right > left && a[right] > key说明当前right索引所对应的关键字比key大，不需要交换
while(right > left && a[right] > key){
right--;
}
//程序能执行到这里说明当前right索引所对应的关键字比key小，需要交换，即补”坑“
a[left] = a[right];
//当left < right && a[left] < key说明当前left索引所对应的关键字比key小，不需要交换
while(left < right && a[left] < key){
left++;
}
//程序能执行到这里说明当前left索引所对应的关键字比key大，需要交换，即补”坑“
a[right] = a[left];
}
//程序跳出了while循环，说明left已经等于right,下面两句也可以改为a[right]=key;return right;
a[left] = key;
return left;
}
public static void quickSort(int[] a , int left , int right){
//临界条件
if(left < right){
//获取中间索引
int middle = getMiddle(a, left, right);
//对左边子数组递归排序
quickSort(a,left,middle-1);
//对右边子数组递归排序
quickSort(a, middle+1, right);
}
}
//测试程序
public static void main(String[] args) {
int[] a = new int[]{9,3,7,8,2,0,6};
System.out.println("快速排序前的数组:");
int i = 0;
while(i < a.length){
System.out.print(a[i]+"\t");
i++;
}
System.out.println();
Sorter.quickSort(a, 0, a.length-1);
System.out.println("快速排序后的数组:");
i = 0;
while(i < a.length){
System.out.print(a[i]+"\t");
i++;
}
}
}
执行结果：
快速排序前的数组: 9 3 7 8 2 0 6 快速排序后的数组: 0 2 3 6 7 8 9
转载于:https://www.cnblogs.com/iamconan/p/7383569.html
