快速排序

原理

从一组未排序的元素中，随机选取一个元素，作为枢纽元。然后让剩余的元素与枢纽元进行比较，将集合分为三部分：小于枢纽元的组成一部分，大于枢纽元的组成一部分，最后是枢纽元单独成为一部分。然后在递归的对小集合和大集合再重复此操作，最终完成排序。

实现

1. 选取枢纽元；

   1. 随机选取；

   2. 三数中值选取，取首、尾和中心的三个元素的中值；

2. 将枢纽元与数组的最后一个元素交换位置；

3. 创建两个指针，指针i指向第一个元素，指针j指向倒数第二个元素；

4. 当i在j的左侧时，将i向右移，移过那些小于枢纽元的元素，停留在大于枢纽元的元素上；同时将j向左移，移过那些大于枢纽元的元素，停留在小于枢纽元的元素上；然后将i上的元素与j上的元素互换位置；

5. 当i与j重合或i在j的右侧时，停止两个指针的移动，并将枢纽元与指针i指向的元素交换位置。

快速排序

public void queckSort(int[] array, int left, int right) {
    if (left < right) {
        int median = getMedian(array[left], array[(left + right) / 2], array[right]);
        // 将中数交换到数组的最后
        if (median == array[left]) {
            array[left] = array[right];
            array[right] = median;
        } else if (median == array[(left + right) / 2]) {
            array[(left + right) / 2] = array[right];
            array[right] = median;
        }
        // 比较
        int i = left;
        int j = right - 1;
        while (true) {
            while (array[i] < median) {
                i++;
            }
            while (array[j] > median) {
                j--;
            }
            if (i < j) {
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            } else {
                // 枢纽元与i位置的元素交换
                array[right] = array[i];
                array[i] = median;
                break;
            }
        }
        // 递归
        queckSort(array, left, i - 1);
        queckSort(array, i + 1, right);
    }
}

/**
 * 首、中、尾三数取中值 min(max(a, b), c)
 * @param first
 * @param mid
 * @param last
 * @return
 */
private int getMedian(int first, int mid, int last) {
    if (first > mid) {
        if (first > last) {
            if (mid > last) {
                return mid;
            } else {
                return last;
            }
        } else {
            return first;
        }
    } else {
        if (first > last) {
            return first;
        } else {
            if (mid > last) {
                return last;
            } else {
                return mid;
            }
        }
    }
}