首页 > 编程语言 >详解十大经典排序算法(六):快速排序(QuickSort)

详解十大经典排序算法(六):快速排序(QuickSort)

时间:2023-12-23 23:36:43浏览次数:48  
标签:arr int 基准 QuickSort high 详解 low 排序


算法原理

  1. 分区(Partition): 选择一个基准元素,将数组分为两个子数组,小于基准的放在左边,大于基2准的放在右边。
  2. 递归排序: 对左右两个子数组分别进行快速排序。
  3. 合并: 不需要实际的合并操作,因为在分解和递归排序阶段已经完成了排序。

算法描述

快速排序是一种基于分治思想的高效排序算法,由英国计算机科学家 Tony Hoare 于1960年提出。它的核心思想是选择一个基准元素,将数组分成两个子数组,小于基准的在左边,大于基准的在右边,然后对子数组进行递归排序。这一过程持续进行,直到整个数组有序。

算法原理可以简要概括为以下步骤:

  1. 选择基准元素: 从待排序的数组中选择一个元素作为基准(pivot)。选择基准的方法有多种,常见的包括选择第一个元素、最后一个元素、中间元素,或者随机选择一个元素。
  2. 分区过程: 将数组中的其他元素按照与基准的大小关系划分到基准的两侧,使得基准左边的元素都小于基准,右边的元素都大于基准。这个过程称为分区(partition)。具体的分区算法有多种,其中一种常见的是Lomuto分区方案和Hoare分区方案。
  • Lomuto分区方案
    a. 从左到右遍历数组,将比基准小的元素放到基准的左侧。
    b. 使用一个索引i来记录当前小于基准的元素的位置,初始时i指向数组的起始位置。
    c. 遇到小于基准的元素时,将它与索引i指向的元素交换,并将i递增。
    d. 最后,将基准元素与索引i指向的元素交换,这样基准元素就放置在了其最终的位置。
  • Hoare分区方案
    a. 使用两个指针,一个从数组的左端移动到右端,另一个从右端移动到左端,分别找到大于和小于基准的元素。
    b. 交换这两个元素的位置。
    c. 重复这个过程,直到两个指针相遇。最后,基准元素的位置就是两指针相遇的位置。
  1. 递归排序: 对基准左右两侧的子数组分别递归地应用快速排序算法。即,对左侧的子数组和右侧的子数组分别进行步骤1和步骤2,直到每个子数组只有一个元素,此时整个数组就是有序的。
  2. 合并结果:不需要实际的合并操作,因为在分区和递归排序阶段已经完成了排序。

动画演示

详解十大经典排序算法(六):快速排序(QuickSort)_算法


能看懂动画你就理解了快速排序 好吧,可能这个图不好理解,看个视频讲解把>>>B站小姐姐讲解快速排序

代码实现

public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 获取分区索引
            int partitionIndex = partition(arr, low, high);

            // 递归排序左右子数组
            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 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;
    }

算法复杂度

时间复杂度(最坏)

时间复杂度(最好)

时间复杂度(平均)

空间复杂度

稳定性

O(n^2)

O(n log n)

O(n log n)

O(log n)

不稳定

  • 最好情况:在最优情况下,快速排序的时间复杂度是O(n log n)。这通常发生在每次分区都能将数组均匀地分成两半的情况下。
  • 平均情况:在平均情况下,快速排序的时间复杂度是O(n log n)。这是因为每次分区都将数组分成两部分,每一部分都需要O(log n)次分区操作。
  • 最坏情况:最坏情况下的时间复杂度是O(n^2),当每次分区都选择最大或最小的元素作为基准时,会导致分区不均衡。
  • 空间复杂度:快速排序是一种原地排序算法,它不需要额外的存储空间来存储临时数据。因此,其空间复杂度是O(1)。这是因为所有的操作都是在输入数组上进行的,只需要常数级别的辅助空间用于存储一些变量,如循环索引、基准元素等。

快速排序的优化方式

快速排序是一种高效的排序算法,但在某些情况下可能面临最坏情况,即分区不均衡,导致性能下降。

  1. 随机选择基准元素
    在每次排序开始时,随机选择数组中的一个元素作为基准元素,而不是固定选择第一个或最后一个元素。这可以避免在某些情况下导致最坏情况发生。
public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // 随机选择基准元素
            int randomIndex = getRandomIndex(low, high);
            swap(arr, randomIndex, high);

            int partitionIndex = partition(arr, low, high);

            quickSort(arr, low, partitionIndex - 1);
            quickSort(arr, partitionIndex + 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;
    }

    private static int getRandomIndex(int low, int high) {
        Random random = new Random();
        return random.nextInt(high - low + 1) + low;
    }
  1. 三数取中法
    选择基准元素时,不是简单地选择第一个或最后一个元素,而是选择第一个、中间和最后一个元素中的中间值作为基准元素。
public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // 三数取中法选择基准元素
        int mid = low + (high - low) / 2;
        int pivotIndex = getMedianIndex(arr, low, mid, high);
        swap(arr, pivotIndex, high);

        int partitionIndex = partition(arr, low, high);

        quickSort(arr, low, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, high);
    }
}

private static int getMedianIndex(int[] arr, int i, int j, int k) {
    if ((arr[i] - arr[j]) * (arr[k] - arr[i]) >= 0) {
        return i;
    } else if ((arr[j] - arr[i]) * (arr[k] - arr[j]) >= 0) {
        return j;
    } else {
        return k;
    }
}

这两种优化方式可以在某些情况下提高快速排序的性能,特别是在面对特定输入数据的时候。随机选择基准和三数取中法都有助于减少最坏情况的发生概率,提高算法的鲁棒性。


相关概念

稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面。
不稳定:如果a原本在b的前面,而a=b,排序之后 a 可能会出现在 b 的后面。
时间复杂度:对排序数据的总的操作次数。反映当n变化时,操作次数呈现什么规律。
空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模n的函数。


标签:arr,int,基准,QuickSort,high,详解,low,排序
From: https://blog.51cto.com/xaye/8947865

相关文章

  • 算法学习笔记五一快速排序
    目录什么是快速排序算法思想示例代码什么是快速排序快速排序(Quicksort)是一种常用的排序算法,它的基本思想是通过分治的策略将一个大问题划分为多个小问题来解决。它的平均时间复杂度为O(nlogn),最坏情况(有序情况)为O(n^2)。是一种高效的排序算法。算法思想选择一个基准元素(pivot......
  • 将 n 个整数由小到大排序
    #define_CRT_SECURE_NO_WARNINGS1#include<stdio.h>intmain(){ intarr[10]; printf("请输入一串数字:\n"); for(inti=0;i<10;i++) { scanf("%d",&arr[i]); } for(inti=0;i<10;i++)//循环次数等于元素 { for(intj=......
  • C语言实现面向对象的方法详解
    结构体替代类使用结构体来封装变量和函数,即可实现类似对象的功能。其中,结构体包含变量和函数指针,变量用于存储成员变量的值,函数指针用于实现成员函数的功能。而每个对象的变量是独立的,因此可以使用这种方法实现类似对象的功能。下面是一个例子,以封装一个“人”的结构体为例:typ......
  • Java数组常见的几种排序。
    publicclasscode2{publicstaticvoidmain(String[]args){int[]x={37,89,23};for(intz=0;z<x.length-1;z++){intminIndex=z;for(inti=z+1;i<x.length;i++){if(......
  • 排序
    本来我们最开始是想把序列的操作转化为单点操作的想一下我们遇到过的序列转单点的方法:差分、前驱后继所以这题本来想用差分的,但是排了序之后差分数组是无法确定的(可以手动模拟样例就知道为啥无法确定了)然而这题目还给了我们一个提示:只需要知道最后时刻第\(q\)个位置上的数所以......
  • C++ Qt开发:Charts折线图绘制详解
    Qt是一个跨平台C++图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍QCharts折线图的常用方法及灵活运用。折线图(LineChart)是一种常用的数据可视化图表,用于展示随着......
  • Jackson Annotations(注解)详解
    转载自:https://blog.csdn.net/wjw465150/article/details/1273268491.概述在本教程中,我们将深入研究JacksonAnnotations。我们将了解如何使用现有的注解,如何创建自定义注解,最后,如何禁用它们。2.Jackson序列化注解首先,我们将看一下序列化注解。2.1.@JsonAnyGetter@J......
  • Spring的BeanDefinitionRegistryPostProcessor接口详解
    BeanDefinitionRegistryPostProcessor介绍BeanDefinitionRegistryPostProcessor它是Spring框架的一个扩展点,用于对Bean定义的注册过程进行干预和定制,例如添加,修改或删除Bean定义等。BeanDefinitionRegistryPostProcessor它继承BeanFactoryPostProcessor接口,并在其基础上扩展了......
  • 软件测试/测试开发|Linux sed命令详解
    sed命令介绍sed是streameditor(流编辑器)的简写,sed可依照脚本的指令来处理、编辑文本文件。Sed主要用来自动编辑一个或多个文件、简化对文件的反复操作、编写转换程序等。sed命令语法基本语法:sed[选项]'动作'文件名常用参数-n,--quiet,--silent取消自动打印模式空间-e......
  • FLV格式详解
    本文是什么FLV(FlashVideo)是由Adobe公司开发的一种非常流行的视频格式,其简单的内容格式非常适合用于流媒体。虽然现如今这种格式已经开始被弃用,但因为各种原因,一部分企业仍然继续使用这种格式来进行流媒体传输。学习FLV格式也有利于学习同样是Adobe公司开发的实时传输协议RTM......