Java实现快速排序及其动图演示

快速排序（Quicksort）是一种基于分治思想的排序算法。它通过选择一个基准元素，将数组分为两个子数组，其中一个子数组的所有元素都小于基准元素，另一个子数组的所有元素都大于基准元素，然后递归地对这两个子数组进行排序。

具体步骤如下：

选择一个基准元素，通常选择数组中的第一个元素。
将数组分为两个子数组，一个是小于基准元素的子数组，一个是大于基准元素的子数组。可以使用两个指针分别从数组的两端开始，然后向中间遍历，当两个指针相遇时停止，并交换相遇位置的元素。
递归地对两个子数组进行步骤1和步骤2的操作，直到子数组的长度为1或者为空。
合并排序好的子数组，此时整个数组已经有序。

快速排序的时间复杂度为O(nlogn)，其中n是数组的长度。最坏情况下的时间复杂度为O(n^2)，但是通过合理地选择基准元素，可以避免最坏情况的发生。快速排序是一种原地排序算法，不需要额外的空间。

Java实现快速排序及其动图演示-LMLPHP

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

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {5, 8, 2, 1, 6, 3, 9, 4, 7};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("排序结果：");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];
        while (low < high) {
            while (low < high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];
            while (low < high && arr[low] <= pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low] = pivot;
        return low;
    }
}

代码的思路是采用了分治法的思想。首先选择一个基准元素，通常是数组的第一个元素。然后将数组分为两部分，一部分是小于等于基准元素的元素，一部分是大于基准元素的元素。接着对这两部分分别进行快速排序，直到每个部分只剩下一个元素或者没有元素。

在quickSort方法中，首先判断low是否小于high，如果是的话，调用partition方法划分数组，并在基准元素的位置将数组分为两部分，然后再分别对这两部分进行快速排序。

partition方法使用两个指针low和high，分别从数组两端开始向中间移动。在移动过程中，如果遇到比基准元素小的元素，则将其放到左边，否则将其放到右边。最后将基准元素放到合适的位置，并返回该位置的索引。

以上代码可以按照快速排序的思想对给定的数组进行排序。

输出结果为：1 2 3 4 5 6 7 8 9。

小筱在线

Java实现快速排序及其动图演示