排序--快速排序

概念

采用归并思想/分治法：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

时间复杂度

• 平均：O(nlog(n))
• 最好：O(nlog(n))
• 最坏：O(n²)

空间复杂度

O(1)

稳定性

不稳定

代码

public class QuickSort implements Sort {

    @Override
    public int[] sort(int[] arr) {
        return sort(arr, 0, arr.length - 1);
    }

    private int[] sort(int[] arr, int l, int h) {
        // 选择第一个元素作为分区点
        int pivot = arr[l];

        int i = l;
        int j = h;

        while (i < j) {
            while (arr[i] < pivot) {
                i++;
            }

            while (arr[j] > pivot) {
                j--;
            }

            if (arr[i] == arr[j]) {
                i++;
            } else {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }

        if (i - 1 > l) {
            sort(arr, l, i - 1);
        }

        if (j + 1 < h) {
            sort(arr, j + 1, h);
        }

        return arr;
    }
}