快速排序算法

快排是好多算法的基础，还是比较常用的，尤其是在面试中很容易被问到。

代码

public class QuickSort {
    
    public void sort(int [] arr) {
        if (arr == null || arr.length <= 1)
            return;
        quickSort(arr, 0, arr.length - 1);
    }
    
    private void quickSort(int[] arr, int low, int high) {
        if (low >= high) 
            return;
        int middle = getMid(arr,low,high);//将数组一分为二
        //继续排序
        quickSort(arr, low, middle - 1);
        quickSort(arr, middle + 1, high);
    }
    
    private int getMid(int[] arr, int low, int high) {
        int temp = arr[low]; // 将第一个数作为标准
        while(low < high){
            while(low < high && temp < arr[high]) {
                high --;
            }
            arr[low] = arr[high];
            while(low < high && temp > arr[low]) {
                low ++;
            }
            arr[high] = arr[low];
        }
        arr[low] = temp;
        return low;
    }

}

原理

快速排序的原理其实挺简单的，选择一个值作为标准，通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比标准值小，另一部分关键字均比标准值大，然后分别对这两部分继续重复上面的步骤，直到整个序列有序。