当前位置：首页 > article >正文

Java中的快速排序算法详解

article 2024/11/15 8:36:15

快速排序是一种广泛使用的排序算法，以其高效的性能和简单的实现而闻名。它基于分治法的原理，通过一个基准值（pivot）将数组分为两个子数组，分别对子数组进行排序，最终达到整体排序的目的。本文将详细介绍快速排序算法的思想、Java实现及其性能分析。

一、快速排序的基本思想

快速排序的核心思想是选择一个基准值，将数组分为左右两部分，使得左边的元素都小于基准值，右边的元素都大于基准值。这个过程称为分区（partition）。之后，递归地对左右两个子数组进行排序。

二、Java实现

在Java中实现快速排序主要包括两个步骤：分区和递归排序。以下是一个简单的快速排序实现示例：

public class QuickSort {
    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);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // 选择第一个元素作为基准值
        int pivot = arr[low];
        int i = low + 1;
        int j = high;
        while (i <= j) {
            // 从左向右找到第一个大于基准值的元素
            while (i <= j && arr[i] <= pivot) {
                i++;
            }
            // 从右向左找到第一个小于基准值的元素
            while (i <= j && arr[j] > pivot) {
                j--;
            }
            // 交换两个元素
            if (i < j) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        // 将基准值移到正确的位置
        arr[low] = arr[j];
        arr[j] = pivot;
        return j;
    }

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