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

重温经典算法——快速排序

ops 2025/7/14 1:04:54

版权声明

本文原创作者：谷哥的小弟
作者博客地址：http://blog.csdn.net/lfdfhl

在这里插入图片描述

基本原理

快速排序基于分治思想，通过选取基准元素将数组划分为两个子数组（小于基准和大于基准），递归排序子数组。平均时间复杂度 O(n log n)，最差 O(n²)（如已有序且基准选择不当），空间复杂度 O(log n)。

代码实现

import java.util.Arrays;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[high]; // 选择最后一个元素为基准（可优化为三数取中）int i = low - 1;       // 记录小于基准的子数组末尾位置for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;swap(arr, i, j); // 将小于基准的元素交换到左侧}}swap(arr, i + 1, high); // 将基准放到正确位置return i + 1;}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}public static void main(String[] args) {int[] arr = {10, 7, 8, 9, 1, 5};quickSort(arr, 0, arr.length - 1);System.out.println("Sorted array: " + Arrays.toString(arr));// 输出：Sorted array: [1, 5, 7, 8, 9, 10]}
}