十大经典排序算法（下）

🍓个人主页：bit.. 

🍒系列专栏：Linux(Ubuntu)入门必看   C语言刷题      数据结构与算法  HTML和CSS3

目录

1.6 快速排序

1. 算法步骤

2. 动图演示

3.代码实现

 1.7 堆排序

1. 算法步骤

2. 动图演示

3. 代码实现

1.8 计数排序

1. 计数排序的特征

2. 动图演示

3.代码实现

 1.9 桶排序

1. 什么时候最快

2. 什么时候最慢

3. 示意图

3.代码实现

 1.10 基数排序

1. 基数排序 vs 计数排序 vs 桶排序

2. LSD 基数排序动图演示

3.代码实现

1.6 快速排序

快速排序，一种排序很快的方法，使用分治思想，就是说快速排序是通过把数据分成几部分来处理的一种算法。快排本身和其使用的分治思想都很重要，也是面试可能出现的一大难点。

1. 算法步骤

  1. 从数列中挑出一个元素，称为 "基准"（pivot）;

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

2. 动图演示

3.代码实现

public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

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

}

 1.7 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：

  1. 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
  2. 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

1. 算法步骤

  1. 创建一个堆 H[0……n-1]；

  2. 把堆首（最大值）和堆尾互换；

  3. 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

  4. 重复步骤 2，直到堆的尺寸为 1。

2. 动图演示

3. 代码实现

public class HeapSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int len = arr.length;

        buildMaxHeap(arr, len);

        for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    private void buildMaxHeap(int[] arr, int len) {
        for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    private void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, len);
        }
    }

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

}

1.8 计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

1. 计数排序的特征

当输入的元素是 n 个 0 到 k 之间的整数时，它的运行时间是 Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序中的算法来排序数据范围很大的数组。

通俗地理解，例如有 10 个年龄不同的人，统计出有 8 个人的年龄比 A 小，那 A 的年龄就排在第 9 位,用这个方法可以得到其他每个人的位置,也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去 1 的原因。

 算法的步骤如下：

  • （1）找出待排序的数组中最大和最小的元素
  • （2）统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  • （3）对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  • （4）反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1 

2. 动图演示

3.代码实现

public class CountingSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxValue = getMaxValue(arr);

        return countingSort(arr, maxValue);
    }

    private int[] countingSort(int[] arr, int maxValue) {
        int bucketLen = maxValue + 1;
        int[] bucket = new int[bucketLen];

        for (int value : arr) {
            bucket[value]++;
        }

        int sortedIndex = 0;
        for (int j = 0; j < bucketLen; j++) {
            while (bucket[j] > 0) {
                arr[sortedIndex++] = j;
                bucket[j]--;
            }
        }
        return arr;
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

}

 1.9 桶排序

桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

1. 什么时候最快

当输入的数据可以均匀的分配到每一个桶中。

2. 什么时候最慢

当输入的数据被分配到了同一个桶中。

3. 示意图

元素分布在桶中：

然后，元素在每个桶中排序：

3.代码实现

public class BucketSort implements IArraySort {

    private static final InsertSort insertSort = new InsertSort();

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return bucketSort(arr, 5);
    }

    private int[] bucketSort(int[] arr, int bucketSize) throws Exception {
        if (arr.length == 0) {
            return arr;
        }

        int minValue = arr[0];
        int maxValue = arr[0];
        for (int value : arr) {
            if (value < minValue) {
                minValue = value;
            } else if (value > maxValue) {
                maxValue = value;
            }
        }

        int bucketCount = (int) Math.floor((maxValue - minValue) / bucketSize) + 1;
        int[][] buckets = new int[bucketCount][0];

        // 利用映射函数将数据分配到各个桶中
        for (int i = 0; i < arr.length; i++) {
            int index = (int) Math.floor((arr[i] - minValue) / bucketSize);
            buckets[index] = arrAppend(buckets[index], arr[i]);
        }

        int arrIndex = 0;
        for (int[] bucket : buckets) {
            if (bucket.length <= 0) {
                continue;
            }
            // 对每个桶进行排序，这里使用了插入排序
            bucket = insertSort.sort(bucket);
            for (int value : bucket) {
                arr[arrIndex++] = value;
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }

}

 1.10 基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

1. 基数排序 vs 计数排序 vs 桶排序

基数排序有两种方法：

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

  • 基数排序：根据键值的每位数字来分配桶；
  • 计数排序：每个桶只存储单一键值；
  • 桶排序：每个桶存储一定范围的数值；

2. LSD 基数排序动图演示

3.代码实现

/**
 * 基数排序
 * 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
 */
public class RadixSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容，并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/887.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2023-03-17：使用Go语言和FFmpeg库实现音频重采样解码，并将其保存为PCM格式的文件。

2023-03-17：使用Go语言和FFmpeg库实现音频重采样解码，并将其保存为PCM格式的文件。

2023-03-17&#xff1a;使用Go语言和FFmpeg库实现音频重采样解码&#xff0c;并将其保存为PCM格式的文件。 答案2023-03-17&#xff1a; 在音视频处理领域&#xff0c;常常需要对音频进行重采样和解码&#xff0c;以便于后续的处理和分析。本文将介绍如何使用Go语言及FFmpeg库…
阅读更多...
【C++学习】类和对象（中）一招带你彻底了解六大默认成员函数

【C++学习】类和对象（中）一招带你彻底了解六大默认成员函数

前言&#xff1a;在之前&#xff0c;我们对类和对象的上篇进行了讲解&#xff0c;今天我们我将给大家带来的是类和对象中篇的学习&#xff0c;继续深入探讨【C】中类和对象的相关知识&#xff01;&#xff01;&#xff01; 目录 1. 类的6个默认成员函数 2. 构造函数 2.1概念介…
阅读更多...
【黑马JVM(2)】垃圾回收

【黑马JVM(2)】垃圾回收

JVM垃圾回收如何判断对象可以回收引用计数法可达性分析算法四种引用垃圾回收算法标记-清除标记-整理标记-复制分代垃圾回收相关VM参数垃圾回收器串行吞吐量优先响应时间优先G1垃圾回收阶段Young CollectionYoung Collection跨代引用Young CollectionCMRemark-SATBMixed Collect…
阅读更多...
第三代api自动化测试框架使用教程（pytest+allure+sql+yaml）

第三代api自动化测试框架使用教程（pytest+allure+sql+yaml）

使用教程一、配置1、环境配置2、框架配置3、启动入口二、用例编写1、用例模板2、参数依赖写法2、函数&#xff08;方法插件&#xff09;写法3、接口上传文件和表单参数4、接口上传json参数5、接口无数据填写6、code断言7、body断言7、json断言8、sql断言9、完整断言写法&#x…
阅读更多...
TCP UDP详解

TCP UDP详解

文章目录TCP UDP协议1. 概述2. 端口号 复用 分用3. TCP3.1 TCP首部格式3.2 建立连接-三次握手3.3 释放连接-四次挥手3.4 TCP流量控制3.5 TCP拥塞控制3.6 TCP可靠传输的实现3.7 TCP超时重传4. UDP5.TCP与UDP的区别TCP UDP协议 1. 概述 TCP、UDP协议是TCP/IP体系结构传输层中的…
阅读更多...
手把手的教你安装PyCharm --Pycharm安装详细教程（一）（非常详细，非常实用）

手把手的教你安装PyCharm --Pycharm安装详细教程（一）（非常详细，非常实用）

简介 Jetbrains家族和Pycharm版本划分&#xff1a; pycharm是Jetbrains家族中的一个明星产品&#xff0c;Jetbrains开发了许多好用的编辑器&#xff0c;包括Java编辑器&#xff08;IntelliJ IDEA&#xff09;、JavaScript编辑器&#xff08;WebStorm&#xff09;、PHP编辑器&…
阅读更多...
C/C++考试必考题目（含答案*仅供参考）

C/C++考试必考题目（含答案*仅供参考）

今天继续来分享几个C经常考试的几道题目&#xff0c;大家快快拿去&#xff0c;赶紧做一下 目录 &#xff08;小事一桩&#xff09;约瑟夫问题 discreb input output 效果展示&#xff1a; 1、 猜价格游戏 2、 计算 N 以内的所有素数 3、 袋中取球 4、 乘法口诀表 …
阅读更多...
尚医通-（三十三）就诊人管理功能实现

尚医通-（三十三）就诊人管理功能实现

目录&#xff1a; &#xff08;1&#xff09;前台用户系统-就诊人管理-需求说明 &#xff08;2&#xff09;就诊人管理-接口开发-列表接口 &#xff08;3&#xff09;就诊人管理-接口开发-其他接口 &#xff08;4&#xff09;前台用户系统-就诊人管理-前端整合 &#xff0…
阅读更多...
react的基础使用

react的基础使用

react中为什么使用jsxReact 认为渲染逻辑本质上与其他 UI 逻辑内在耦合&#xff0c;比如&#xff0c;在 UI 中需要绑定处理事件、在某些时刻状态发生变化时需要通知到 UI&#xff0c;以及需要在 UI 中展示准备好的数据。react认为将业务代码和数据以及事件等等 需要和UI高度耦合…
阅读更多...
竞赛无人机搭积木式编程——以2022年TI电赛送货无人机一等奖复现为例学习(7月B题)

竞赛无人机搭积木式编程——以2022年TI电赛送货无人机一等奖复现为例学习(7月B题)

在学习本教程前&#xff0c;请确保已经学习了前4讲中无人机相关坐标系知识、基础飞行控制函数、激光雷达SLAM定位条件下的室内定点控制、自动飞行支持函数、导航控制函数等入门阶段的先导教程。 同时用户在做二次开发自定义的飞行任务时&#xff0c;可以参照第5讲中2021年国赛植…
阅读更多...
【uniapp小程序实战】—— 使用腾讯地图获取定位

【uniapp小程序实战】—— 使用腾讯地图获取定位

文章目录&#x1f34d;前言&#x1f34b;正文1、首先看官网uni.getLocation(OBJECT)#注意2、腾讯位置服务平台申请密钥和下载SDK2.1 申请开发者秘钥2.2 开通webserviceAPI服务2.3 下载微信小程序JavaScriptSDK2.4 安全域名设置3、配置manifest.json文件4、示例代码展示4.1 引用…
阅读更多...
面试重难点问题（C++）

面试重难点问题（C++）

持续更新&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 网络部分 1.问&#xff0c;四次挥手的过程&#xff0c;和双方状态变化&#xff1f; 挥手这前&#xff0c;两边都是established状态&#xff0c;客户端发起断开请求&#xff0c;向服务器发送fin请求&…
阅读更多...
Docker6种网络配置详解，网络模式应该这么选

Docker6种网络配置详解，网络模式应该这么选

文章目录一、Bridge网络模式二、Host网络模式三、Overlay网络模式四、None网络模式五、Macvlan网络模式六、Ipvlan网络模式七、网络模式选择在Docker中&#xff0c;网络配置是一个重要的主题&#xff0c;因为容器需要与其他容器或外部网络进行通信。Docker提供了多种网络模式和…
阅读更多...
注意下C语言整形提升

注意下C语言整形提升

C语言整形提升 C语言整形提升是指在表达式中使用多种类型的数据时&#xff0c;编译器会自动将较小的类型转换为较大的类型&#xff0c;以便进行运算。在C语言中&#xff0c;整型提升规则如下&#xff1a; 如果表达式中存在short类型&#xff0c;则将其自动转换为int类型。 如…
阅读更多...
【JavaEE】初识线程

【JavaEE】初识线程

一、简述进程认识线程之前我们应该去学习一下“进程" 的概念&#xff0c;我们可以把一个运行起来的程序称之为进程&#xff0c;进程的调度&#xff0c;进程的管理是由我们的操作系统来管理的&#xff0c;创建一个进程&#xff0c;操作系统会为每一个进程创建一个 PCB&…
阅读更多...
C++之深浅拷贝

C++之深浅拷贝

一、浅拷贝 我们看下以下代码 Test.h 文件 #pragma once #include<iostream> using namespace std; class Student { public:Student(){}~Student(){if (m_Id ! nullptr){delete m_Id;m_Id nullptr;}}Student(int id, string strName){m_Id new int[id];m_strName s…
阅读更多...
字符函数和字符串函数(上)-C语言详解

字符函数和字符串函数(上)-C语言详解

CSDN的各位友友们你们好,今天千泽为大家带来的是C语言中字符函数和字符串函数的详解,掌握了这些内容能够让我们更加灵活的运用字符串,接下来让我们一起走进今天的内容吧!写这篇文章需要在cplusplus.com上大量截图,十分不易!如果对您有帮助的话希望能够得到您的支持和帮助,我会持…
阅读更多...
信号处理-小波变换4-DWT离散小波变换概念及离散小波变换实现滤波

信号处理-小波变换4-DWT离散小波变换概念及离散小波变换实现滤波

连续小波变换的适用场景&#xff1a;能够获取某一段信号的瞬时信息、时频信息 缺点&#xff1a;计算量大&#xff0c;无法进行数据压缩- 针对连续小波存在的缺点提出离散小波变换 离散小波变换 离散小波变换 分解过程&#xff1a;&#xff08;离散2进正交&#xff09; cD1: …
阅读更多...
数据结构与算法——栈和队列＜也不过如此＞

数据结构与算法——栈和队列＜也不过如此＞

&#x1f3c6;作者主页&#xff1a;king&南星 &#x1f384;专栏链接&#xff1a;数据结构 &#x1f3c5;文章目录一、&#x1f947;栈1、&#x1f948;概念理解2、&#x1f948;链表头插头删实现栈1、&#x1f949;预备准备2、&#x1f949;创建结点函数3、&#x1f949;遍…
阅读更多...
SPI读写SD卡速度有多快？

SPI读写SD卡速度有多快？

SD卡是一个嵌入式中非常常用的外设&#xff0c;可以用于存储一些大容量的数据。但用单片机读写SD卡速度一般都有限&#xff08;对于高速SD卡&#xff0c;主要是受限于单片机本身的接口速度&#xff09;&#xff0c;在高速、实时数据存储时可能会有影响。但具体速度可以达到多少…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站