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

【基础3】快速排序

核心思路

快速排序是Java中Arrays.sort()的实现原理,采用分治策略,通过选择基准元素,将数组分为两个子数组,使得左边元素 ≤ 基准元素 ≤ 右边元素,然后递归排序子数组。

举个简单的例子,图书管理员需要按照书本厚度对一箱书进行排序,使用快速排序就是先选择一本书作为中间基准,把厚的书放在它右边,薄的书放在它左边。(这里左右两边内部是无序的)

处理完后再对它左边的书分别快速排序(即选出新的基准元素,厚的放右边,薄的放左边),同理右边也是一样,最后就得到完整的序列。

复杂度
情况时间复杂度空间复杂度
最好情况O(n logn)O(logn)
最坏情况O(n²)O(n)
平均情况O(n logn)O(logn)
优缺点

优点

  1. 平均情况下最快的比较排序算法
  2. 原地排序(不需要额外内存)
  3. 高度可优化

缺点

  1. 最坏情况时间复杂度较高
  2. 不稳定排序
  3. 递归实现需要栈空间

适用场景

  • 大规模数据排序
  • 需要高效率的通用排序
  • 内存受限环境
代码实现(Java)
public class QuickSort {

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

    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;       

        //i+1实际上就是最后基准元素要被移到的位置
        for (int j = low; j < high; j++) {
            //把小于基准的元素不断向左靠拢(比基准大的元素也被动地向右边移动),
            //最后[low,i]的元素都比基准小,那么i+1的位置自然就留给基准元素了
            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;
    }
}
排序过程

初始数组:[5, 3, 8, 4, 2]

第1次分区(pivot=2)

移动元素:5>2,3>2,8>2,4>2 → 无交换  
最终交换基准 → [2, 3, 8, 4, 5]
返回位置0

递归左半部(空数组)和右半部[3,8,4,5]

第2次分区(pivot=5)

排序数组:[3,8,4,5]  
移动元素:3<5,8>5,4<5 → 交换8和4  
最终数组:[3,4,5,8]  
返回位置2

递归处理左右子数组

左半部[3,4] → 最终排序[3,4]  
右半部[8] → 保持原样

最终结果

[2, 3, 4, 5, 8]

http://www.kler.cn/a/576367.html

相关文章:

  • TDengine SQL手册—删除数据
  • 搭建BOA服务器
  • 【MySQL_03】数据库基本--核心概念
  • Springboot 循环依赖
  • 深入解析京东商品详情 API 接口 item_get
  • Linux(Centos 7.6)命令详解:vim
  • 运维Zabbix面试题及参考答案
  • HCIA-路由重分布
  • Python接口自动化之断言封装!
  • LLM论文笔记 19: On Limitations of the Transformer Architecture
  • 鸿蒙HarmonyOS评论功能小demo
  • 考研题库与考研真题分别应该如何使用?
  • 搭建一套东郊到家上门按摩app需要多少钱?
  • 恶劣天候三维目标检测论文列表整理
  • eclipse查看源码
  • 自学Java-JavaSE基础加强(Java网络编程)
  • 大白话CSS 中的box-sizing属性,它有哪些值以及各自的作用
  • 【笔记】记一次easyExcel中注解ExcelProperty映射字段赋值无效问题
  • G1,最大的特点是什么,标记位图,卡表卡页,SATB又分别是什么?
  • 统一数据返回格式