Java快速排序算法实现(简洁易懂)

本文提供了一个简洁易懂的Java快速排序算法实现。快速排序是一种高效的排序算法，其平均时间复杂度为O(n log n)。

以下是Java代码示例:javapublic class QuickSort { public static void main(String[] args) { int[] array = {5, 9, 1, 3, 2, 6, 8, 7, 4}; quickSort(array, 0, array.length - 1); System.out.println('排序结果：'); for (int num : array) { System.out.print(num + ' '); } }

public static void quickSort(int[] array, int low, int high) {        if (low < high) {            int pivot = partition(array, low, high);            quickSort(array, low, pivot - 1);            quickSort(array, pivot + 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++;                swap(array, i, j);            }        }        swap(array, i + 1, high);        return i + 1;    }

public static void swap(int[] array, int i, int j) {        int temp = array[i];        array[i] = array[j];        array[j] = temp;    }}

代码解释:

quickSort(int[] array, int low, int high): - 递归函数，对数组 array 中从索引 low 到 high 的部分进行快速排序。 - 首先检查 low 是否小于 high，如果不是，则表示当前部分已经排序完毕，直接返回。 - 调用 partition() 函数获取分区点 pivot。 - 递归调用 quickSort() 对分区点左边的部分和右边的部分进行排序。
partition(int[] array, int low, int high): - 选择数组最后一个元素 array[high] 作为基准元素 pivot。 - 使用两个指针 i 和 j，i 指向小于 pivot 的元素区域的下一个位置，j 遍历数组。 - 遍历过程中，如果发现 array[j] 小于 pivot，则将 array[j] 和 array[i+1] 交换，并将 i 加一，扩大小于 pivot 的元素区域。 - 最后将 pivot 放到正确的位置，即将 pivot 与 array[i+1] 交换。 - 返回分区点 pivot 的索引。
swap(int[] array, int i, int j): 交换数组中索引 i 和 j 处的元素。

总结:

快速排序是一种高效的排序算法，其思想是分治法。该算法通过选择一个基准元素将数组分成两个子数组，并递归地对子数组进行排序，最终实现整个数组的有序排列。