了解快速排序算法（附Java示例）

wufei123 2025-01-26 阅读:1 评论:0

快速排序：高效的分治排序算法快速排序是一种基于分治策略的高效排序算法。它将问题分解成更小的子问题，分别解决后再合并结果，最终得到排序后的数组。核心在于选择一个“枢轴”（pivot）元素，将数组划分成两部分：小于枢轴的元素和大于枢轴的元素。...

快速排序：高效的分治排序算法

快速排序是一种基于分治策略的高效排序算法。它将问题分解成更小的子问题，分别解决后再合并结果，最终得到排序后的数组。核心在于选择一个“枢轴”（pivot）元素，将数组划分成两部分：小于枢轴的元素和大于枢轴的元素。然后递归地对这两部分进行排序。

快速排序工作原理详解

假设我们需要对一个数组进行升序排序：

了解快速排序算法（附Java示例）

步骤1：选择枢轴

我们选择数组的最后一个元素作为枢轴：

了解快速排序算法（附Java示例）

步骤2：数组划分

遍历数组，将小于枢轴的元素移动到枢轴左侧，大于枢轴的元素移动到枢轴右侧。为此，我们使用两个指针：一个指向当前遍历元素，另一个指向小于枢轴元素区域的末尾。

了解快速排序算法（附Java示例）

最后，将枢轴与小于枢轴元素区域的末尾元素交换：

了解快速排序算法（附Java示例）

步骤3：递归排序

根据枢轴的位置，将数组划分成两个子数组，并递归地对这两个子数组应用快速排序算法，直到子数组只有一个元素（此时已排序）。

了解快速排序算法（附Java示例）

快速排序代码实现

public class QuicksortTest {
    public static void main(String[] args) {
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("Unsorted array: " + java.util.Arrays.toString(arr));
        quicksort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: " + java.util.Arrays.toString(arr));
    }

    public static void quicksort(int[] arr, int start, int end) {
        if (start < end) {
            int partitionIndex = partition(arr, start, end);
            quicksort(arr, start, partitionIndex - 1);
            quicksort(arr, partitionIndex + 1, end);
        }
    }

    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[end];
        int secondPointer = start - 1;
        for (int i = start; i < end; i++) {
            if (arr[i] < pivot) {
                secondPointer++;
                swap(arr, i, secondPointer);
            }
        }
        swap(arr, end, secondPointer + 1);
        return secondPointer + 1;
    }

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

代码解读：