快速排序（java）

通过一趟排序将待排序的记录分割为独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两个记录继续进行排序，以达到整个序列有序的目的。时间复杂度为O(nlogn)，为不稳定的排序算法。

代码

void quitSort(int[] arr) {
    if (arr == null || arr.length <= 0) {
        return;
    }
    quitSort(arr, 0, arr.length - 1);
}

void quitSort(int[] arr, int start, int end) {
    if (start < end) {
        int pivot = partation(arr, start, end); // 算出中间值
        quitSort(arr, start, pivot);            // 对左侧序列进行递归排序
        quitSort(arr, pivot + 1, end);     // 对右侧序列进行递归排序
    }
}

int partation(int[] arr, int start, int end){
    // 三数取中，通过交换保证arr[start] 是中间值，这样比较合理
    int middle = start + (end - start) / 2;
    if (arr[start] > arr[end]) {
        swap(arr, start, end);
    }
    if (arr[middle] > arr[end]) {
        swap(arr, middle, end);
    }
    if (arr[start] > arr[middle]) {
        swap(arr, start, middle);
    }
    int tmp = arr[start];
    while (start < end) {
        while (start < end && arr[end] > tmp) {
            end --;
        }
        arr[start] = arr[end];
        while (start < end && arr[start] <= tmp) {
            start ++;
        }
        arr[end] = arr[start];
    }
    arr[start] = tmp;
    return start;
}