快速排序

思路

第一轮以0为基准数，确定基准数在数组中应存放的位置，比基准数小的全都在基准数左边，比基准数大的全都在基准数右边，第二轮后面在基准数左右两边分别以此类推

步骤

记录基准数
定义两个变量记录要查找的范围（排序范围的左右两端用于遍历）
如图，6为基准数，start和end为定义的两个变量，他们会分别向中间遍历
end，从后往前开始找，找比基准数小的数字然后记录
start,从前往后开始找，找到比基准数大的数字然后记录
让start和end指向的元素进行交换
如图，找到后让5和7进行交换：
当左右两边指针相遇，那么他们指向的位置左边都比基准数小，右边都比基准数大，这个位置就是基准数应该存放的位置，让基准数和该位置交换
如图，让6和3交换：

放好第一次的基准数，第一轮结束，然后左右两边分别重复刚刚的步骤（递归调用自己）

代码实现(java实现，逻辑相通)

/**  
 * 参数一：我们要排序的数组  
 * 参数二：要排序数组的起始索引  
 * 参数三：要排序数组的结束索引  
 */  
public static void quickSort(int[] arr,int i,int j){  
    //定义两个变量记录要查找的范围  
    int start = i;  
    int end = j;  
    //递归出口  
    if(start>end){  
        return;  
    }  
    //记录基准数  
    int baseNumber = arr[i];  
    //利用循环找到要交换的数字  
    while(start != end){  
        //利用end，从后往前开始找，找比基准数小的数字  
        while(true){  
            if(end<=start ||arr[end]<baseNumber){  
                break;  
            }  
            end--;  
        }  
        //利用start,从前往后开始找，找比基准数大的数字  
        while(true){  
            if(start>=end||arr[start]>baseNumber){  
                break;  
            }  
            start++;  
        }  
        //把end和start指向的元素进行交换  
        int temp=arr[start];  
        arr[start] = arr[end];  
        arr[end] = temp;  
    }  
    /**  
     * 当start和end指向了同一个元素的时候，那么上面的循环就会结束  
     * 表示已经找到了基准数在数组中应存入的位置  
     * 基准数归位  
     * 就是拿着这个范围中的第一个数字，跟start指向的元素进行交换  
     */  
    int temp = arr[i];  
    arr[i] = arr[start];  
    arr[start] = temp;  
    //递归调用自己，分别处理左右两边  
    quickSort(arr,i,start-1);  
    quickSort(arr,start+1,j);  
}