十大排序算法模板

☆* o(≧▽≦)o *☆嗨~我是小奥🍹
📄📄📄个人博客:小奥的博客
📄📄📄CSDN:个人CSDN
📙📙📙Github:传送门
📅📅📅面经分享(牛客主页):传送门
🍹文章作者技术和水平有限,如果文中出现错误,希望大家多多指正!
📜 如果觉得内容还不错,欢迎点赞收藏关注哟! ❤️

文章目录

  • 排序算法
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 计数排序
    • 基数排序
    • 桶排序

排序算法

十大排序算法指的是在计算机科学中被广泛使用,效率较高且实现简单的十个排序算法。下面是这十种排序算法的简要介绍:

(1)冒泡排序(Bubble Sort):交换相邻元素,最大或最小的元素经过n-1次比较后,就会排在数组的最后一位。

(2)选择排序(Selection Sort):每次寻找未排序序列中的最小值,并将其放在已排序序列的末尾。

(3)插入排序(Insertion Sort):对于未排序序列中的每一个元素,将其插入到已排序序列中的合适位置。

(4)希尔排序(Shell Sort):采用分组策略,先将待排序序列拆分为n/2个子序列,进行插入排序,然后逐渐缩小子序列的长度,直到子序列长度为1,即完成排序。

(5)归并排序(Merge Sort):将待排序序列不断二分,再将两个有序的子序列合并为一个有序序列,重复上述步骤,直到整个序列有序。

(6)快速排序(Quick Sort):选择一个基准元素,将序列中小于它的元素放在它的左边,大于它的元素放在右边,然后递归地对左右子序列进行快速排序。

(7)堆排序(Heap Sort):将待排序序列构建成一个堆,然后不断从堆顶取出最大值,并调整堆,直到取完所有元素。

(8)计数排序(Counting Sort):统计序列中每个元素出现的次数,然后根据统计信息对序列进行重排。

(9)桶排序(Bucket Sort):将整个区间划分为若干个桶,然后将元素按照大小分配到相应的桶中,在桶内使用其他的排序算法(如插入排序)进行排序。

(10)基数排序(Radix Sort):将待排序序列拆分为多个关键字,按照每个关键字进行排序,最终得到有序序列。

以上十种排序算法都有其独特的优势和适用场景,选择合适的排序算法可以提高程序的效率。

冒泡排序

	// 冒泡排序
    public static void bubblingSort(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                if(nums[i] > nums[j]) {
                    int t = nums[i];
                    nums[i] = nums[j];
                    nums[j] = t;
                }
            }
        }
    }

	// 双向冒泡排序
    public static void twoWaySort(int[] nums) {
        int l = 0, r = nums.length - 1;
        while(l < r) {
            for(int i = l + 1; i <= r; i++) {
                if(nums[l] > nums[i]) {
                    nums[l] ^= nums[i];
                    nums[i] ^= nums[l];
                    nums[l] ^= nums[i];
                }
            }
            l++;
            for(int i = r - 1; i >= l; i--) {
                if(nums[r] < nums[i]) {
                    nums[r] ^= nums[i];
                    nums[i] ^= nums[r];
                    nums[r] ^= nums[i];
                }
            }
            r--;
        }
    }

选择排序

	// 选择排序
    public static void selectSort(int[] nums) {
        int n = nums.length;
        for(int i = 0; i < n - 1; i++) {
            int minVal = i;
            for(int j = i + 1; j < n; j++) {
                if(nums[minVal] > nums[j]) {
                    minVal = j;
                }
            }
            if(minVal != i) {
                int t = nums[i];
                nums[i] = nums[minVal];
                nums[minVal] = t;
            }
        }
    }

插入排序

	// 插入排序
    public static void insertSort(int[] nums) {
        int n = nums.length;
        for(int i = 1; i < n; i++) {
            int val = nums[i], j = i;
            while(j > 0 && val < nums[j - 1]) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = val;
        }
    }

希尔排序

	// 希尔排序
    public static void shellSort(int[] nums) {
        int n = nums.length;
        for(int g = n >> 1; g > 0; g >>= 1) {
            for(int i = g; i < n; i++) {
                int x = nums[i];
                int j = 0;
                for(j = i; j >= g && nums[j - g] > x; j -= g) {
                    nums[j] = nums[j - g];
                }
                nums[j] = x;
            }
        }
    }

归并排序

借鉴博客链接:(9条消息) java实现归并排序(详解)_java 归并排序_星辰与晨曦的博客-CSDN博客

介绍

归并排序先将待排序的数组不断拆分,直到拆分到区间里只剩下一个元素的时候。不能再拆分的时候。这个时候我们再想办法合并两个有序的数组,得到长度更长的有序数组。当前合并好的有序数组为下一轮得到更长的有序数组做好了准备。一层一层的合并回去,直到整个数组有序。

实现

	public static void mergeSort(int[] nums, int l, int r, int[] temp) {
        if(l >= r) return;
        int mid = l + r >> 1;
        mergeSort(nums, l, mid, temp);
        mergeSort(nums, mid + 1, r, temp);
        int k = 0, i = l, j = mid + 1;
        while(i <= mid && j <= r) {
            if(nums[i] < nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while(i <= mid) temp[k++] = nums[i++];
        while(j <= r) temp[k++] = nums[j++];
        for(i = l, j = 0; i <= r; i++, j++) {
            nums[i] = temp[j];
        }
    }

快速排序

介绍

实现

 	// 快速排序 递归版
    public static void quickSort(int[] nums, int l, int r) {
        if(l >= r) {
            return;
        }
        int i = l - 1, j = r + 1, x = nums[(l + r) / 2];
        while(i < j) {
            do i++; while(nums[i] < x);
            do j--; while(nums[j] > x);
            if(i < j) {
                int t = nums[i]; 
                nums[i] = nums[j]; 
                nums[j] = t;
            }
        }
        quickSort(nums, l, j);
        quickSort(nums, j + 1, r);
    }

	// 快速排序,非递归版
    public static void quickSortByStack(int[] nums, int l, int r) {
        Stack<Integer> s = new Stack<>();
        s.push(r);
        s.push(l);
        while(!s.isEmpty()) {
            int low = s.pop(), high = s.pop();
            int i = low, j = high;
            if(i >= j) {
                continue;
            }
            int pivot = nums[i];
            while(i < j) {
                while(i < j && nums[j] >= pivot) j--;
                nums[i] = nums[j];
                while(i < j && nums[i] < pivot) i++;
                nums[j] = nums[i];
            }
            nums[i] = pivot;
            s.push(high);
            s.push(i + 1);
            s.push(i - 1);
            s.push(low);
        }
    }

堆排序

import java.util.Scanner;
public class Main{
    static int N = 100010;
    static int[] h = new int[N];
    static int size;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        size = n;
        for(int i = 1; i < n + 1; i++) {
            h[i] = sc.nextInt();
        }
        // 建堆
        for(int i = n / 2; i != 0; i--)  down(i);
        while(k-- > 0) {
            System.out.print(h[1] + " ");
            h[1] = h[size];
            size--;
            down(1);
        }
    }

    // 下移
    public static void down(int u) {
        int t = u;
        if(2 * u <= size && h[2 * u] < h[t]) t = 2 * u;
        if(2 * u + 1 <= size && h[2 * u + 1] < h[t]) t = 2 * u + 1;
        if(t != u) {
            h[u] ^= h[t];
            h[t] ^= h[u];
            h[u] ^= h[t];
            down(t);
        }
    }
}		

计数排序

 	// 计数排序
    public static void countSort(int[] nums) {
       int n = nums.length;
       int[] t = new int[n];
       int maxV = nums[0];
       for(int i = 1; i < n; i++) {
           if(maxV < nums[i]) {
               maxV = nums[i];
           }
       }
        int[] count = new int[maxV + 1];
        for(int i = 0; i < n; i++) count[nums[i]]++;
        for(int i = 1; i <= maxV; i++) count[i] += count[i - 1];
        for(int i = n - 1; i >= 0; i--) {
            t[count[nums[i]] - 1] = nums[i];
            count[nums[i]]--;
        }
        for(int i = 0; i < n; i++) nums[i] = t[i];
    } 

基数排序

借鉴博客链接:(8条消息) java实现基数排序_基数排序java_其实我不想摆烂的博客-CSDN博客

介绍

属于分配式排序,又称桶子法或者bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。

基数排序的思想是,将所有待比较数值统一为同样的数值长度,数位较短的数前面补0,然后,从最低位开始,依次进行一次排序,这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

实现

	// 基数排序
    public static void radixSort(int[] nums) {
        // 找出数组中的最大值
        int max = nums[0];
        for(int i : nums) max = max > i ? max : i;
        // 计算最大值的位数
        int len = (max + "").length();
        // 桶的表示。十个桶处理 0-9 十个数字
        // 防止数据溢出,所以定义len长度的一维数组来存放每次排序后的序列
        // 经典的空间换时间概念
        int[][] bucket = new int[10][len];
        // 记录每个桶中放置数字的个数
        int[] bucketCount = new int[10];
        // 循环处理
        for(int i = 0, n = 1; i < len; i++, n *= 10) {
            // 第i轮对对应的位排序,第一次为个位,第二次为十位
            for(int j = 0; j < nums.length; j++) {
                int digit = (nums[j] / n) % 10;
                bucket[digit][bucketCount[digit]] = nums[j];
                bucketCount[digit]++;
            }
        }
        int idx = 0;
        for(int i = 0; i < bucketCount.length; i++) {
            if(bucketCount[i] != 0) {
                for(int j = 0; j < bucketCount[i]; j++) {
                    nums[idx++] = bucket[i][j];
                }
            }
            bucketCount[i] = 0;
        }
    }

桶排序

借鉴博客链接:(8条消息) java实现桶排序(详细解析)桶排序java、信仰_的博客-CSDN博客

介绍

桶排序 (Bucketsort),是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(O(n))。

桶排序的思想是,若待排序的记录的关键字在一个明显有限范围内时,可设计有限个有序桶,每个桶只能装与之对应的值,顺序输出各桶的值,将得到有序的序列。简单来说,在我们可以确定需要排列的数组的范围时,可以生成该数值范围内有限个桶去对应数组中的数,然后我们将扫描的数值放入匹配的桶里的行为,可以看作是分类,在分类完成后,我们需要依次按照桶的顺序输出桶内存放的数值,这样就完成了桶排序。

实现

	public static void bucketSort(int[] nums) {
        int max = nums[0];
        for(int i : nums) max = max > i ? max : i;
        int[] bucket = new int[max + 1];
        for(int i : nums) bucket[i]++;
        int idx = 0;
        for(int i = 0; i < max + 1; i++ ) {
            for(int j = 0; j < bucket[i]; j++) {
                nums[idx++] = i;
            }
        }
    }

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

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

相关文章

近4w字吐血整理!只要你认真看完【C++编程核心知识】分分钟吊打面试官(包含:内存、函数、引用、类与对象、文件操作)

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;C从基础到进阶 &#x1f3c6;&#x1f3c6;关注博主&#xff0c;随时获取更多关于C的优质内容&#xff01;&#x1f3c6;&#x1f3c6; C核心编程&#x1f30f;1 内存分区模型&#x1f384…

在 Jenkins 中使用 SSH Servers 配置文件上传路径

引言 在使用 Jenkins 进行持续集成和持续部署&#xff08;CI/CD&#xff09;的过程中&#xff0c;有时我们需要将构建好的文件上传到远程服务器。本文将介绍如何在 Jenkins 的 SSH Servers 配置中设置文件的上传目录&#xff0c;以及这些设置是如何组合以形成最终的上传路径。…

LLVM的项目结构

所有LLVM项目都有统一的目录结构。让我们比较一下LLVM和GCC&#xff0c;即GNU编译器集合。几十年来&#xff0c;GCC几乎为您能想到的每一个系统都提供了成熟的编译器。但除了编译器&#xff0c;没有任何工具可以用这些代码&#xff0c;原因是它不为重用而设计&#xff0c;而LLV…

【问题记录】使用命令语句从kaggle中下载数据集

从Kaggle中下载Tusimple数据集 1.服务器环境中安装kaggle 使用命令&#xff1a;pip install kaggle 2.复制下载API 具体命令如下&#xff1a; kaggle datasets download -d manideep1108/tusimple3.配置kaggle.json文件 如果直接使用命令会报错&#xff1a; root:~# kagg…

FPGA——时序分析与约束(Quartus II)

FPGA时序分析与约束 FPGA结构基础数据传输模型Quartus II 时序报告Quartus II 中TimeQuest的操作实操 时序分析&#xff1a;通过分析FPGA内部各个存储器之间的数据和时钟传输路径&#xff0c;来分析数据延迟和时钟延迟的关系&#xff0c;保证所有寄存器都可以正确寄存数据。 数…

直流继电器 JT3-22/5 线圈电压DC220V电磁式 柜内固定安装 JOSEF约瑟

JT3系列直流继电器 系列型号 JT3-42/3电磁继电器;JT3A-40/3电磁继电器 JT3-11/3电磁继电器;JT3A-03/3电磁继电器 JT3-30/3电磁继电器;JT3A-20/3电磁继电器 JT3-02/3电磁继电器;JT3A-12/3电磁继电器 JT3-22/1电磁继电器;JT3A-24/1电磁继电器 JT3-42/1电磁继电器;JT3A-31/1电磁…

gin-vue-admin二开使用雪花算法生成唯一标识 id

场景介绍 需求场景&#xff1a; 总部采集分支的数据&#xff0c;由于分支的 id 是子增的主键 id&#xff0c;所以会出现重复的 id&#xff0c;但是这个 id 需要作为标识&#xff0c;没有实际作用&#xff0c;这里选择的是分布式 id 雪花算法生成 id 存储用来标识&#xff0c;这…

NAS入门(学习笔记)

文章目录 AutoMLNAS初期NAS当前NAS框架One-Shot NAS权重共享策略 Zero-Shot NASZen-NASNASWOTEPENAS 参考资料 AutoML 深度学习使特征学习自动化 AutoML 使深度学习自动化 自动化机器学习 (automated machine learning) 是一种自动化的数据驱动方法, 并做出一系列决策。 按…

数据分析-Pandas如何整合多张数据表

数据分析-Pandas如何整合多张数据表 数据表&#xff0c;时间序列数据在数据分析建模中很常见&#xff0c;例如天气预报&#xff0c;空气状态监测&#xff0c;股票交易等金融场景。数据分析过程中重新调整&#xff0c;重塑数据表是很重要的技巧&#xff0c;此处选择Titanic数据…

vue-cli解决跨域

在vue.config.js中 找到devServer 在devServer中创建proxy代理 proxy:{ path&#xff08;路径中包含这个path就会导航到target的目标接口&#xff09;&#xff1a;{ target:"目标接口" } } 例&#xff1a; 1 同源策略只针对于浏览器&#xff0c;代理服务器到后端接…

Linux中的定时任务(案例:定时备份和清空)

前言 Linux中的定时任务&#xff08;案例&#xff1a;定时备份和清空&#xff09; crontab 命令 Linux crontab 是用来定期执行程序的命令, 当安装完成操作系统之后&#xff0c;默认便会启动此任务调度命令。crond 命令每分钟会定期检查是否有要执行的工作&#xff0c;如果有…

CentOS Linux操作系统源码安装最新Redis版本,使用JSON数据类型踩入新坑

最近有空查阅了redis官网&#xff0c;发现redis数据类型不止Strings、Lists、Sets、Hashes、Sorted sets&#xff0c;还多了几种&#xff0c;决定先试用下JSON数据类型 1、安装Redis软件 JSON数据类型&#xff0c;对Redis版本有要求&#xff0c;需要大于4.0版本。下图是华为云…

基础+常用的数据结构

基础 java基础 JDK 和 JRE JDK&#xff0c;它是功能齐全的 Java SDK&#xff0c;是提供给开发者使用&#xff0c;能够创建和编译 Java 程序的开发套件。它包含了 JRE,同时还包含了编译 java 源码的编译器 javac 以及一些其他工具比如 javadoc&#xff08;文档注释工具&#…

前端下载文件流,设置返回值类型responseType:‘blob‘无效的问题

前言&#xff1a; 本是一个非常简单的请求&#xff0c;即是下载文件。通常的做法如下&#xff1a; 1.前端通过Vue Axios向后端请求&#xff0c;同时在请求中设置响应体为Blob格式。 2.后端相应前端的请求&#xff0c;同时返回Blob格式的文件给到前端&#xff08;如果没有步骤…

java农业信息化技术一体化服务农产品商城平台springboot+vue

农业信息化服务平台,能够推进农村农业信息化的发展,提升农业和农村信息化水平,促进先进农业技术在农业生产中的推广应用,推动农业向现代化、集约化发展。同时,进一步探索农村信息化建设的新模式,以技术规划来支撑农业未来信息化管理的发展。 开发软件有很多种可以用&#xff0c…

【深度学习】RTX2060 2080如何安装CUDA,如何使用onnx runtime

文章目录 如何在Python环境下配置RTX 2060与CUDA 101. 安装最新的NVIDIA显卡驱动2. 使用conda安装CUDA Toolkit3. 验证onnxruntime与CUDA版本4. 验证ONNX需求版本5. 安装ONNX与onnxruntime6. 编写ONNX推理代码 如何在Python环境下配置RTX 2060与CUDA 10 RTX 2060虽然是一款较早…

虚拟环境的搭建

优点 1、使不同应用开发环境相互独立 2、环境升级不影响其他应用&#xff0c;也不会影响全局的python环境 3、防止出现包管理混乱及包版本冲突# 什么是虚拟环境&#xff0c;为什么要有它&#xff1f;它解决了什么问题-操作系统装了python3.8-使用django 2.2.2开发了一个项目-使…

解密IP代理池:匿名访问与反爬虫的利器

当今互联网环境中&#xff0c;为了应对反爬虫、匿名访问或绕过某些地域限制等需求&#xff0c;IP代理池成为了一种常用的解决方案。IP代理池是一个包含多个可用代理IP地址的集合&#xff0c;可以通过该代理池随机选择可用IP地址来进行网络请求。 IP代理池是一组可用的代理IP地址…

【经典算法】有趣的算法之---粒子群算法梳理

every blog every motto: You can do more than you think. https://blog.csdn.net/weixin_39190382?typeblog 0. 前言 粒子群算法 粒子群算法&#xff08;Particle Swarm Optimization&#xff0c;PSO&#xff09;是一种用于解决优化问题的元启发式算法。它通过模拟鸟群或…

Kafka-消费者-KafkaConsumer分析-ConsumerNetworkClient

前面介绍过NetworkClient的实现&#xff0c;它依赖于KSelector、InFlightRequests、Metadata等组件&#xff0c;负责管理客户端与Kafka集群中各个Node节点之间的连接&#xff0c;通过KSelector法实现了发送请求的功能&#xff0c;并通过一系列handle*方法处理请求响应、超时请求…