快速排序

摘要：主要是快速排序的思想和2种常见的写法

思想：

快速排序流程：
(1) 从数列中挑出一个基准值。
(2) 将所有比基准值小的摆放在基准前面，所有比基准值大的摆在基准的后面(相同的数可以到任一边)；在这个分区退出之后，该基准就处于数列的中间位置。
(3) 递归地把"基准值前面的子数列"和"基准值后面的子数列"进行排序

代码实现:

方式一：

public static void main(String[] args) {
	    int[] a = {0,5,4,5,3,2,8,6,5};
	    quickSort(a,0,a.length-1);
	    for (int i=0;i<a.length ;i++ ){
	        System.out.print(a[i]+" ");
	    } 
	}
	static void quickSort(int[] arrs,int left,int right){
	    if(left>right) return;
	    int mid = 0; //定义轴值应该放的下标
	    mid = partition(arrs,left,right);
	    quickSort(arrs,left,mid-1);
	    quickSort(arrs,mid+1,right);
	    
	}
	
	static int partition(int[] arrs,int left,int right){
	    int temp = arrs[left];
	    int i=left; //定义哨兵i和j
	    int j=right;  
	    int t = 0;
	    while(i!=j){
	        while(arrs[j]>=temp && i<j)
	            j--; //当i到达指定位置
	        while(arrs[i]<=temp && i<j)
	            i++; //j到达指定位置
	       if(i<j){   //i 和 j交换不能用swap函数
	           t =arrs[i];
	           arrs[i]=arrs[j];
	           arrs[j]=t;
	       }     
	    }
	    // i 等于j时结束，此时找到了轴值对应的下标
	    arrs[left]=arrs[i]; 
	    arrs[i]=temp;
	    
	    return i;
	}

方式二：

/*
 * 快速排序
 *
 * 参数说明：
 *     a -- 待排序的数组
 *     l -- 数组的左边界(例如，从起始位置开始排序，则l=0)
 *     r -- 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
 */
public void quick_sort(int a[], int l, int r)
{
    if (l < r)
    {
        int i,j,x;

        i = l;
        j = r;
        x = a[i];
        while (i < j)
        {
            while(i < j && a[j] > x)
                j--; // 从右向左找第一个小于x的数
            if(i < j)
                a[i++] = a[j];
            while(i < j && a[i] < x)
                i++; // 从左向右找第一个大于x的数
            if(i < j)
                a[j--] = a[i];
        }
        a[i] = x;
        quick_sort(a, l, i-1); /* 递归调用 */
        quick_sort(a, i+1, r); /* 递归调用 */
    }
}