快速排序
快速排序也是分治思想下的排序方法。时间复杂度O(n*log2n)，是不稳定的。比如前两个数字是一样的，明显就不稳定了。
1.首先理解如何分为两组：
假设有array[10]
a，选定一个用来比较的基数，就选第一个吧;（这里的算法就先不理了）
b.a中选定了一个基数，用另外一个空间去储存，那么位置array[0]就空缺出来了，来选择一个数字去填充它，如何选择呢，从后边开始与基数比，比他小的满足条件
c.然后从后边选出了一个数，把它放进array[0],那么现在后边又空出了一个数可以填了
d.现在，从array[1]开始比较，比基数大的数字放到刚刚的数组尾部那个空缺的可填入的地方
代码如下：
private static int adjustArray(int[] array , int start,int end){
//记录左边的那个可比较的元素位置
int i = start;
//记录右边的那个可比较的元素位置
int j = end;
//记录用来比较的基数
int tem = array[start];
//如果i<j，循环继续
while(i < j){
//从右边找满足条件的数（小于基数）放进左边可以填的那个地方，这里与下边的那个while循环都没有出现=号，但是并不会出现遗漏元素，因为与基数相等的元素待在原来的地方并不会影响排序的结果
while(i < j && tem < array[j])
j--;
if(i < j){
array[i] = array[j];
//下次左边比较的数字
i++;
}
//从左边找满足条件的数（大于基数）放进右边可以填的那个地方
while(i < j && tem > array[i])
i++;
if(i < j){
array[j] = array[i];
//下次右边比较的数字
j--;
}
}
//跳出循环时，必然有i = j,这个位置就是基数的位置，然后就会发现基数左边的全是小于基数的数字，基数右边的全是大于基数的数字。
array[i] = tem;
//另外需要返回基准值放的位置
return i;
}
2.递归调用1的方法
public static void quickSort(int[] array,int start,int end){
if(start < end){
int i = adjustArray(array, start, end);
quickSort(array,start,i - 1);
quickSort(array,i + 1,end);
}
}
完整代码：
public class QuickSort {
public static void main(String[] args) {
// TODO Auto-generated method stub
int size = 200000;
int[] array = new int[size];
Random r = new Random();
long start;
for(int i = 0; i < array.length ;i ++){
array[i] = r.nextInt(size);
}
start = System.currentTimeMillis();
quickSort(array, 0, array.length - 1);
System.out.println("quick:" + (System.currentTimeMillis() - start));
}
public static void quickSort(int[] array,int start,int end){
if(start < end){
int i = adjustArray(array, start, end);
quickSort(array,start,i - 1);
quickSort(array,i + 1,end);
}
}
private static int adjustArray(int[] array , int start,int end){
//use to record elements from left
int i = start;
//use to record elements from left
int j = end;
//save the elements that used to be compared(the first elements)
int tem = array[start];
while(i < j){
while(i < j && tem < array[j])
j--;
if(i < j){
array[i] = array[j];
i++;
}
while(i < j && tem > array[i])
i++;
if(i < j){
array[j] = array[i];
j--;
}
}
array[i] = tem;
return i;
}
private static void print(int[] array){
for(int i : array){
System.out.print(i + " ");
}
System.out.println("");
}
}
