快速排序【示例】

冒泡排序可以说是我们学习的第一个真正的排序算法，并且解决了桶排序浪费
空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了 O(N^2)。假如我
们的计算机每秒钟可以运行 10 亿次，那么对 1 亿个数进行排序，桶排序只需要 0.1 秒，而冒
泡排序则需要 1 千万秒，达到 115 天之久，是不是很吓人？那有没有既不浪费空间又可以快一点的排序算法呢？那就是“快速排序”啦！

public class QuickSort {

    public static void main(String[] args) {
        int[] array = {34, 7, 23, 32, 5, 62, 32, 2, 78, 1};
        System.out.println("原始数组:");
        printArray(array);

        quickSort(array, 0, array.length - 1);

        System.out.println("排序后的数组:");
        printArray(array);
    }

    // 快速排序的主函数
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            // pi是分区索引，array[pi]已经排好序
            int pi = partition(array, low, high);

            // 递归地对分区前后的元素进行排序
            quickSort(array, low, pi - 1);
            quickSort(array, pi + 1, high);
        }
    }

    // 分区函数，选择最后一个元素作为枢轴，将小于等于枢轴的元素放在左边，大于枢轴的元素放在右边
    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1); // 较小元素的索引
        for (int j = low; j < high; j++) {
            // 如果当前元素小于或等于枢轴
            if (array[j] <= pivot) {
                i++;

                // 交换array[i]和array[j]
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // 交换array[i + 1]和array[high] (即枢轴)
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    // 打印数组的辅助函数
    public static void printArray(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; ++i) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候
设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全
部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进
行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。当
然在最坏的情况下，仍可能是相邻的两个数进行了交换。

因此快速排序的最差时间复杂度和冒泡排序是一样的，都是 O(N^2)，

它的平均时间复杂度为 O (NlogN)。

其实快速排序是基于一种叫做“二分”的思想。