排序算法之快速排序

概念

上篇文章我们讨论了归并排序，其核心思想是每次将待排的序列拆分为两部分，最终合并成一个序列。简单理解拆分为二叉排序树，从下往上一层一层的合并。
本文我们将讨论快速排序，其平均时间复杂度为O(nlogn)。

快速排序

假如有一组乱序序列：a1, a2, a3 ... an，现在要将它从小到大的排序。

思想

1. 选定一个pivot，将ai > pivot的放到右边，将aj < pivot的放到左边。
2. 递归对右边ai > pivot的排序
3. 递归对左边的aj < pivot的排序
   注意：快速排序的pivot选择非常重要，在极端的情况下时间复杂度为O(n*n)。通常快捷的解决方案是，在待排序列中选第一个，中间一个和最后一个中来取中位数来作为pivot。

案列

待排序列：1, 23, 3, 4, 8, 9，7
理论上快速排序也是一个二叉树，从上面的思想可以看到，每选定一个pivot都将待排序列划分为左右子树，左边小，右边大。然后递归对左右子树进行处理。

代码

···

public void testQuickSort() {
    int[] from = {1, 23, 3, 4, 8, 9, 7};
    quickSort(from, 0 , from.length - 1);
    Arrays.stream(from).forEach(System.out :: println);
}

public void quickSort(int[] array, int startIndex, int endIndex) {
    if (startIndex >= endIndex) {
        return;
    }
    int pivot = partition(array, startIndex, endIndex, array[endIndex]);
    quickSort(array, startIndex, pivot - 1);
    quickSort(array, pivot + 1, endIndex);
}

private int partition(int[] array, int startIndex, int endIndex, int pivotValue) {
    int fromIndex = startIndex - 1;
    int toIndex = endIndex;
    while (true) {
        while (array[++fromIndex] < pivotValue);
        while (array[--toIndex] > pivotValue);
        if (fromIndex >= toIndex) {
            break;
        } else {
            swap(array, fromIndex, toIndex);
        }
    }
    swap(array, fromIndex, endIndex);
    return fromIndex;
}

private void swap(int[] array, int from, int to) {
    int temp = array[to];
    array[to] = array[from];
    array[from] = temp;
}

···