Java 数据结构与算法：快速排序法

算法简介

快速排序（Quick Sort）是一种非常常用的基于比较的排序算法，它的时间复杂度为O(nlogn)，是一种效率较高的内部排序方法。

快速排序算法基于分治思想，它把一个大的问题划分成若干个小的问题来解决。快速排序的基本思想是：通过一趟排序将待排序的数据分成两部分，其中一部分数据都比另一部分要小，然后再按照同样的方法对这两个部分数据分别进行快速排序，以达到整个数据变成有序序列的目的。

具体来说，快速排序算法采用分治策略（Divide and Conquer）实现排序。其主要思想是选取一个基准元素，将序列分为两个子序列，依次对子序列进行排序，最终完成排序操作。整个快速排序算法的递归过程如下：

1. 选取基准元素pivot。
2. 将序列以pivot为界限分为左右两部分。
3. 对左右两个子序列分别进行快速排序，直到子序列只有一个元素。
4. 合并所有子序列得到有序序列。

快速排序法示例

示例一

现在给出一个待排序的数组arr：[4,5,1,8,3,7,9,6,2]，如何利用快速排序算法把这个数组排序呢？

Step 1： 选取基准元素，通常可以选择第一个或者最后一个元素作为基准元素，这里我们选择第一个元素4作为基准元素。

Step 2： 将序列以基准元素4为界限分为两个子序列：小于等于4的为左子序列，大于4的为右子序列。

左子序列：[1,3,2]

右子序列：[5,8,7,9,6]

Step 3： 对左右两个子序列分别进行快速排序，即递归进行步骤1和步骤2，最终我们可以得到有序序列。

左子序列排序后为：[1,2,3]

右子序列排序后为：[5,6,7,8,9]

Step 4： 合并左右两个子序列，得到有序序列：[1,2,3,4,5,6,7,8,9]

示例二

再来一个稍微复杂一点的示例，现在给出一个待排序的数组arr：[5,7,6,3,4,2,1,8]。我们按照上面的方法逐步进行快速排序。

Step 1： 选取基准元素5。

Step 2： 将序列以基准元素5为界限分为两个子序列。

左子序列：[3,4,2,1]

右子序列：[7,6,8]

Step 3： 对左右两个子序列分别进行快速排序，左子序列中最小的元素是1，所以它是整个序列的第一个元素，右子序列中最小的元素是6，它位于左子序列所有元素之后，而小于它的所有元素已经被排好序了。因此，在将右子序列中的元素插入到序列中的时候，可以跳过它，将它插入到接下来合适的位置即可。

左子序列排序后为：[1,2,3,4]

右子序列排序后为：[6,7,8]

Step 4： 合并左右两个子序列，得到有序序列：[1,2,3,4,5,6,7,8]

至此，数组arr已经排好序了。

代码实现

下面是Java语言实现快速排序的示例代码：

public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int i = left, j = right, pivot = arr[left];
        while (i < j) {
            while (i < j && arr[j] >= pivot) {
                j--;
            }
            arr[i] = arr[j];
            while (i < j && arr[i] <= pivot) {
                i++;
            }
            arr[j] = arr[i];
        }
        arr[i] = pivot;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    public static void main(String[] args) {
        int[] arr = {4, 5, 1, 8, 3, 7, 9, 6, 2};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

总结

快速排序算法是一种非常实用高效的排序算法，它的核心思想是分治策略，通过选取基准元素将序列分为两个子序列，然后递归排序各个子序列，最终将所有子序列合并成一个有序序列。快速排序算法的时间复杂度为O(nlogn)，但最差情况下时间复杂度为O(n^2)，因此在实际应用中要谨慎选择。