快速排序 Quicksort

Quick sort快速排序

@See https://en.wikipedia.org/wiki/Quick_sort @See https://github.com/jiek2529/java_algorithm - QuickSort

principle原理

把列表按中间值进行左右大小换位。 左边第一个比中间值大的，与右边自右向左第一个比中间值小的进行换位。

在根据左边循环后最大的位置为界，进行小范围的再按此方式循环置换，达到排序。

example示例

public void sort(int[] list) {
        if (list != null && list.length > 1) {
            quickSort(list, 0, list.length - 1);
        }
    }

    private void quickSort(int list[], int left, int right) {
        int index = partition(list, left, right);
        if (left < index - 1) {
            quickSort(list, left, index - 1);
        }
        if (index < right) {
            quickSort(list, index, right);
        }
    }

    /**
     * 分区折中交换
     *
     * @param list  int数组
     * @param left
     * @param right
     * @return
     */
    private int partition(int list[], int left, int right) {
        int i = left, j = right;
        int pivot = list[(left + right) / 2];//取折中点的值
        while (i <= j) {//如果是倒序，就是把以下两while条件判断修改
            while (list[i] < pivot)
                i++;
            while (list[j] > pivot)
                j--;
            if (i <= j) {
                swap(list, i, j);
                i++;
                j--;
            }
        }
        return i;
    }