package sort_problem;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
 * 快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，
 * 右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
 *
 * 快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
 * 快速排序最好的情况下是每次都正好将数组对半分，这样递归调用次数才是最少的。
 * 这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
 *
 * 最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。
 * 因此最坏的情况下需要比较 N2/2。
 * 为了防止数组最开始就是有序的，需要在进行快速排序时随机打乱数组。
 */
public class QuickSort<T extends Comparable<T>> extends Sort<T> {

    @Override
    public void sort(T[] nums) {
        shuffle(nums);
        sort(nums, 0, nums.length - 1);
    }

    private void sort(T[] nums, int l, int h) {
        if (h <= l) {
            return;
        }

        int j = partition(nums, l, h);
        sort(nums, l, j - 1);
        sort(nums, j + 1, h);
    }

    private void shuffle(T[] nums) {
        List<Comparable> list = Arrays.asList(nums);
        Collections.shuffle(list);
        list.toArray(nums);
    }

    // 取 nums[l] 作为切分元素，然后从数组的左端向右扫描直到找到第一个
    // 大于等于它的元素，再从数组的右端向左扫描找到第一个小于它的元素，
    // 交换这两个元素。不断进行这个过程，就可以保证左指针 i 的左侧元素
    // 都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个
    // 指针相遇时，将切分元素 nums[l] 和 nums[j] 交换位置。此时的j就是切分元素
    private int partition(T[] nums, int l, int h) {
        int i = l, j = h + 1;
        T v = nums[l];
        while (true) {
            while (less(nums[++i], v) && i != h) ;
            while (less(v, nums[--j]) && j != l) ;
            if (i >= j)
                break;
            swap(nums, i, j);
        }
        swap(nums, l, j);
        return j;
    }

}
