快速排序详解（Java实现）

一、快速排序的基本思想

    每一轮的排序都会将区域分割成两个独立的分区，其中左分区的序列的所有值均会比右分区的所有值小。然后对子分区进行同样的分割操作，最后达到整体有序。在排序的过程中，由于已经分开的两部分的元素不需要进行比较，故减少了比较的次数，降低了排序时间。

二、快速排序的详细描述

    首先在要排序的区域a 中选取一个基准值，而后将区域分成两个分区，其中左分区 b 中的元素均小于或者等于基准值，右分区 c 的元素 均大于或者等于中轴值，而后通过递归调用快速排序的过程分别对两个分区再次进行排序，最后将两个分区产生的结果合并即可得到最后的排序序列。

　 “基准值”的选择有很多种方法。最简单的是使用分区中第一个元素值。但是如果输入的数组是正序或者逆序的，就会将所有的记录分到“基准值”的一边。较好的方法是随机选取“基准值”，这样可以减少原始输入对排序造成的影响。但是随机选取“基准值”的开销大。

三、快速排序的算法思想

　  为了实现一次划分，我们可以从数组（假定数据是存在数组中）的两端移动下标，必要时交换记录，直到数组两端的下标相遇为止。为此，我们附设两个指针（下标）i 和 j， 先通过 j 从当前区域的右端向左扫描，越过大于等于基准值的记录。当遇到小于基准值的记录时，扫描停止。然后，通过 i 从当前区域的左端向右扫描，越过小于基准值的记录。当遇到大于等于基准值的记录时，扫描停止。交换两个方向扫描停止的记录 a[j] 与 a[i]。 然后，继续扫描，直至 i 与 j 相遇为止，本轮扫描和交换的过程结束。这时i左边的记录的关键字值都小于基准值，右边的记录的关键字值都大于等于基准值。

最后，当前下标i=j,交换规则使得下标i左边的元素值一定会小于等于基准值，i右边元素值一定会大于等于基准值。所以最后一步是将当前i下标元素值与基准值交换。完成一轮快排，递归，同样对子分区进行操作，直至快排结束。

　通过两个不相邻元素交换，可以一次交换消除多个逆序，加快排序速度。快速排序方法在要排序的数据已经有序的情况下最不利于发挥其长处。

四、快速排序的核心算法

quickSort(int left,int right){
    int i = left;
    int j = right;
    int temp=a[left];
    int t;
    while(i!=j){	//①当i与j没有相遇的时候，执行移动查找
        while(j>i && a[j]>=temp){
            j--;    	//②略过大于等于基准值的下标
        }		//③当找到小于基准值，j下标停止移动
        while(i<j && a[i]<=temp){
            i++;		//②略过小于等于基准值的下标
        }   		 //③当找到大于基准值，i下标停止移动
        if(i<j){		//④交换下标i和j的元素值
            t = a[i];
            a[i]=a[j];
            a[j]=t;
        }
    }	//⑤当i与j相遇的时候，停止移动查找
    //⑥交换基准值和当前相遇下标的元素值
    a[left]=a[i]; 
    a[i]=temp; 

    //⑦完成一轮分区，已经将区域划分去左右两个分区，执行递归，对分区继续操作
    quickSort(left,i-1);
    quickSort(j+1,right);
}

五、快速排序源码实现

package sort;



public class QuickSort {

    private static int[] a = {6,1,2,7,9,3,4,5,10,8};

    public static void main(String[] args){
        System.out.println("原数组值：");
        for (int i : a) {
            System.out.print(i+" ");
        }
        System.out.println();
        quickSort(0, a.length-1);
    }

    public static void quickSort(int left,int right){
        int i,j,temp;
        if(left>right){
            return;
        }
        temp=a[left]; //temp中存的就是基准数
        i=left;
        j=right;
        while(i!=j){
            //顺序很重要，要先从右边开始找 ，直到找到一个小于基准的值
            while(a[j]>=temp && i<j){
                j--;
            }
            //再找右边的 ，直到找到一个大于基准的值
            while(a[i]<=temp && i<j){
                i++;
            }
            //交换两个数在数组中的位置
            if(i<j) {
                int t=a[i];
                a[i]=a[j];
                a[j]=t;      
                System.out.println("交换值后：");
                for (int k : a) {
                    System.out.print(k+" ");
                }
                System.out.println();
            }
       }
        //最终将基准数归位
        a[left]=a[i];
        a[i]=temp;
        System.out.println("基准值归位后：");
        for (int k : a) {
            System.out.print(k+" ");
        }
        System.out.println();
        if(left<i-1){
            quickSort(left,i-1);//继续处理左边的，这里是一个递归的过程
        }
        if(right>j+1){
            quickSort(i+1,right);//继续处理右边的 ，这里是一个递归的过程
        }
    }
}

六、结果值查看

原数组值：
6 1 2 7 9 3 4 5 10 8 
交换值后：
6 1 2 5 9 3 4 7 10 8 
交换值后：
6 1 2 5 4 3 9 7 10 8 
基准值归位后：
3 1 2 5 4 6 9 7 10 8 
基准值归位后：
2 1 3 5 4 6 9 7 10 8 
基准值归位后：
1 2 3 5 4 6 9 7 10 8 
基准值归位后：
1 2 3 4 5 6 9 7 10 8 
交换值后：
1 2 3 4 5 6 9 7 8 10 
基准值归位后：
1 2 3 4 5 6 8 7 9 10 
基准值归位后：
1 2 3 4 5 6 7 8 9 10