常见排序算法总结

文章目录

  • 比较排序
    • 冒泡排序
    • 选择排序
    • 插入排序
    • 归并排序
    • 快速排序
    • 堆排序
    • 希尔排序
  • 非比较排序(桶排序)
    • 计数排序
    • 基数排序

比较排序

冒泡排序

嵌套循环,每次内层循环执行时,数组的每两个元素交换,将一个最大/小的数排到数组末尾

在这里插入图片描述

public void bubbleSort(int[] arr){for (int i = 0; i < arr.length; i++) {// 内层循环中,每轮都是让最后一个位置排好序,然后外层循环向前递进for (int j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j+1]){  // 把大的数挪到后面int tmp = arr[j];arr[j] = arr[j+1];arr[j+1] = tmp;}}}
}

选择排序

嵌套循环,每次内层循环执行时,子数组的后m-1个元素寻找最小值,再与子数组的首元素比较,如果更大/小就交换

在这里插入图片描述

public void selectSort(int[] arr){for (int i = 0; i < arr.length - 1; i++){    // len个元素只需比较n-1次int min_idx = i;for (int j = i + 1; j < arr.length; j++){if (arr[j] < arr[min_idx])     // 在i+1后面的数两两比较,找到最小下标min_idx = j;}// 内层遍历完之后,我们拿到后面的元素的最小值下标min_id,要和前面的下标i元素进行值的对比if (arr[min_idx] < arr[i]){        // 能篡位就篡位!arr[min_idx] = arr[min_idx] ^ arr[i];arr[i]       = arr[min_idx] ^ arr[i];arr[min_idx] = arr[min_idx] ^ arr[i];}}
}

插入排序

嵌套循环,默认第一个元素不处理,每插入/增加一个数,就依次跟前面的数两两对比,将前面的所有数进行排好序

在这里插入图片描述

public void insertSort(int[] arr){for (int i = 1; i < arr.length; i++) {  // 外层循环len-1次// 对应外层的len-1次,内层分别循环1到len-1次,且后一个数 < 前一个数才会进循环交换for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--){// 如果后一个元素更小,就交换到前面来arr[j]     = arr[j] ^ arr[j + 1];arr[j + 1] = arr[j] ^ arr[j + 1];arr[j]     = arr[j] ^ arr[j + 1];}}
}

归并排序

递归到最底层时会执行merge排序,回溯时排序保证了此时两个子数组都必然有序

在这里插入图片描述

// 不传参默认对整个数组进行归并排序
public void mergeSort(int[] arr) {if (arr == null || arr.length < 2) return;mergeSort(arr, 0, arr.length - 1);
}
// 传参则对[l, r]区间进行归并排序
public void mergeSort(int[] arr, int l, int r) {if (l == r) return;int mid = l + ((r - l) >> 1);mergeSort(arr, l, mid);mergeSort(arr, mid + 1, r);merge(arr, l, mid, r);  // 回溯位置归并,所以此时的子数组皆已排序完成
}
// 对 arr 的 [l, m]  [m+1, r] 两部分子数组进行归并排序
public void merge(int[] arr, int l, int m, int r) {int[] help = new int[r - l + 1];  // 辅助数组,暂时存放归并后的数组int i = 0;// 两个子数组的起始索引位置 p1 p2int p1 = l, p2 = m + 1;// 精髓:看数据哪边小,就先挪哪边的数据到help数组里while (p1 <= m && p2 <= r) help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];while (p1 <= m) help[i++] = arr[p1++];while (p2 <= r) help[i++] = arr[p2++];// 将暂存的归并后的数组,覆盖到 arr 上,使原数组排好序for (i = 0; i < help.length; i++) {arr[l + i] = help[i];}
}

快速排序

整体的quickSort函数swap后,再进行partition,划分三部分后,<区域 >区域 分别递归调用局部的quicksort

在这里插入图片描述

public void quickSort(int[] arr) {if (arr == null || arr.length < 2) return;quickSort(arr, 0, arr.length - 1);
}public void quickSort(int[] arr, int l, int r) {if (l < r) {// 左神的随机:让最右的r与[l,r-1]之间的随机一个数交换swap(arr, l + (int) (Math.random() * (r - l + 1)), r);// 先partition再进递归(与归并的回溯时merge区分)int[] p = partition(arr, l, r);quickSort(arr, l, p[0] - 1); // = 区域的左部分quickSort(arr, p[1] + 1, r); // = 区域的右部分}
}public int[] partition(int[] arr, int l, int r) {int less = l - 1;int more = r;while (l < more) {if (arr[l] < arr[r]) {swap(arr, ++less, l++);} else if (arr[l] > arr[r]) {swap(arr, --more, l);} else {l++;}}swap(arr, more, r);  // 最右那个 = 划分值挪回原位return new int[] { less + 1, more };  // = 区域:[ less+1, more ]
}public void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}

堆排序

堆是一种比较特殊的完全二叉树

分为:大根堆小根堆

由于完全二叉树的结构性质,可以使用数组或列表等线性数据结构来存储堆(此处用优先级队列)

大根堆:每个子树的最大节点是头结点

小根堆:每个子树的最小节点是头结点

在这里插入图片描述

public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) return;// 1. 先构建大根堆,完成后就已知arr最大值(根节点的value)// 传统 heapInsert1// for (int i = 0; i < arr.length; i++) {//    heapInsert1(arr, i);// }// 进化 heapInsert2heapInsert2(arr);// 2. 取出根节点这个最大值,与末尾节点做交换,然后最大值相当于到末尾排好序了,所以移除这个末尾(最大值)元素//    末尾节点到根节点位置后就heapify,再去重新进行大根堆的构建int size = arr.length;swap(arr, 0, --size);while (size > 0) {heapify(arr, 0, size);swap(arr, 0, --size);}
}
// 1. 构建大根堆   v1.0 传统版
public static void heapInsert1(int[] arr, int index) {while (arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) /2);index = (index - 1)/2 ;}
}
// 1. 构建大根堆   v2.0 进化版
public static void heapInsert2(int[] arr){for (int i = arr.length - 1; i >= 0; i--){heapify(arr, i, arr.length);}
}
// 2. 某个数在index位置,能否往下(数组下标越大的方向)移动
public static void heapify(int[] arr, int index, int size) {int left = index * 2 + 1;while (left < size) {int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;largest = arr[largest] > arr[index] ? largest : index;if (largest == index)break;swap(arr, largest, index);index = largest;left = index * 2 + 1;}
}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;
}

希尔排序

间隔分组,且分组间隔依次减半,每次分组后,每个组内排序都是插入排序

相比于一开始就用插入排序,希尔排序的比较次数更少,效率更高

为什么呢?大概是因为插入排序没预处理,极端情况可能让一个很小很右的数一直比比比比比,比到最开头,浪费比较次数

而希尔排序会让每次分组比较后,基本上左侧大区间 < 右侧大区间 类似 log(n) 但实际复杂度为 O ( n 1.3 − 2 ) O(n^{1.3-2}) O(n1.32) -表示范围,不是减号

所以其实最坏情况和插入排序一样,只不过可能性较小,正常都比插入排序好些

public void shellSort(Comparable[] arr) {// 不断减半分组排序for (int gap = arr.length / 2; gap > 0; gap /= 2) {// 对每个步长的整个数组进行插入排序for (int i = gap; i < arr.length; i++) {// 内层就是插入排序,但交换的间隔单位为gap,不会影响其他分组for (int j = i; j >= gap && arr[j].compareTo(arr[j - gap]) < 0; j -= gap) {// 交换元素Comparable temp = arr[j];arr[j] = arr[j - gap];arr[j - gap] = temp;}}}
}

非比较排序(桶排序)

计数排序

省流:词频表

// only for 0~200 value,可以更大,但太占内存空间了,还不如换别的
// 仅适用于数组数据较为集中密集的情况,太稀疏的话,中间一堆内存空间浪费
public void countSort(int[] arr) {if (arr == null || arr.length < 2) return;int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}// 一个词频表int[] bucket = new int[max + 1];for (int i = 0; i < arr.length; i++) {bucket[arr[i]]++;}// 词频表中的数据依次取出放到arr,保证有序int i = 0;for (int j = 0; j < bucket.length; j++) {while (bucket[j]-- > 0) {arr[i++] = j;}}
}

基数排序

数字按最多多少位,先补齐

从个位开始排,开始进桶再出桶,完成个位上的优先级排序

从十位开始排,还是进桶出桶,完成十位上的优先级排序

依次百位,千位… 越往后,越晚排,优先级越高

同时之前的优先级也会保留下来

所有都排完,数组就有序了(升序/降序)

某种情况比计数排序好,因为数字,如果按照普通十进制理解,则只需准备10个不同数字的桶就好了!

局限:得根据多少进制准备多个桶,需要有进制这个前提规则!

前提得知道空间范围,比如人的年龄,正数[0-200],否则内存爆炸!

所以这种不基于比较的算法应用范围很局限,大部分情况下,不如之前的所有比较算法!

图解如下:
在这里插入图片描述

前缀和处理,倒序入桶,以及词频——比较难理解,可以看下面左神讲解

左神桶排序 2:15:00

// 只适合非负数
public void radixSort(int[] arr) {if (arr == null || arr.length < 2) return;radixSort(arr, 0, arr.length - 1, maxbits(arr));
}
// 计算数组中最大元素的位数(比如324就是三位数)
public int maxbits(int[] arr) {int max = Integer.MIN_VALUE;for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}int res = 0;while (max != 0) {res++;max /= 10;}return res;
}public void radixSort(int[] arr, int begin, int end, int digit) {final int radix = 10;  // 默认十进制int i = 0, j = 0;// 有多少个数就准备多少个辅助空间int[] bucket = new int[end - begin + 1];// 有多少个“十进制位”,就出桶进桶多少次,所以循环digit次(从个位开始算)for (int d = 1; d <= digit; d++) {int[] count = new int[radix];// 1. 遍历每一个arr元素,根据外层循环次数,取出个/十/百...位上的数字(getDigit的作用)for (i = begin; i <= end; i++) {j = getDigit(arr[i], d);count[j]++;}// 2. 遍历好个/十/百...位上的所有数字后,count数组记录了对于数字出现的频数//    接下来,把词频数换成前缀数,记录<=当前索引的数字个数,处理成如下效果://                        "10个空间"//          count[0] 当前位(d位)是 0      的数字有多少个//          count[1] 当前位(d位)是 0和1   的数字有多少个//          count[2] 当前位(d位)是 0,1和2 的数字有多少个//          count[i] 当前位(d位)是 0-i    的数字有多少个for (i = 1; i < radix; i++) {count[i] = count[i] + count[i - 1];}// 3. 入桶操作:从右往左遍历,根据个/十/百...位上的数字大小进行相应入桶,排好序for (i = end; i >= begin; i--) {j = getDigit(arr[i], d);bucket[count[j] - 1] = arr[i];count[j]--;}// 4. 出桶操作:将bucket(help)辅助数组,覆盖赋值到原来的数组arr中for (i = begin, j = 0; i <= end; i++, j++) {arr[i] = bucket[j];}}
}
// 获取一个整数 x 在指定位数 d 上的数字
public int getDigit(int x, int d) {return ((x / ((int) Math.pow(10, d - 1))) % 10);
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

技术成神之路:设计模式(八)责任链模式

介绍 责任链模式&#xff08;Chain of Responsibility Pattern&#xff09;是一种行为设计模式&#xff0c;它允许多个对象依次处理请求&#xff0c;避免请求的发送者和接收者之间的显式耦合。该模式通过将多个可能处理请求的对象连接成一条链&#xff0c;并沿着这条链传递请求…

达梦数据库 DISQL连接数据库与执行SQL、脚本的方法

DISQL连接数据库与执行SQL、脚本的方法 1.DISQL介绍2.DISQL连接数据库的方法2.1 本地连接2.2 远程连接2.3 CONN连接 3.执行SQL、脚本的方法3.1 通过DISQL登录后在字符界面3.2 启动DISQL时运行脚本3.3 进入DISQL后&#xff0c;通过start命令运行脚本3.4 使用EDIT命令编辑脚本 1.…

ubuntu 24 PXE Server (bios+uefi) 批量部署系统

pxe server 前言 PXE&#xff08;Preboot eXecution Environment&#xff0c;预启动执行环境&#xff09;是一种网络启动协议&#xff0c;允许计算机通过网络启动而不是使用本地硬盘。PXE服务器是实现这一功能的服务器&#xff0c;它提供了启动镜像和引导加载程序&#xff0c;…

解决npm install(‘proxy‘ config is set properly. See: ‘npm help config‘)失败问题

摘要 重装电脑系统后&#xff0c;使用npm install初始化项目依赖失败了&#xff0c;错误提示&#xff1a;‘proxy’ config is set properly…&#xff0c;具体的错误提示如下图所示&#xff1a; 解决方案 经过报错信息查询解决办法&#xff0c;最终找到了两个比较好的方案&a…

git commit报错: pre-commit hook failed (add --no-verify to bypass)

原因&#xff1a; 在提交前做代码风格检查&#xff0c;若检查不通过&#xff0c;则提交失败 解决方案&#xff1a;进入项目的.git>hooks目录&#xff0c;找到pre-commit文件&#xff0c;删除即可

【银河麒麟服务器操作系统】java进程oom现象分析及处理建议

了解银河麒麟操作系统更多全新产品&#xff0c;请点击访问麒麟软件产品专区&#xff1a;https://product.kylinos.cn 现象描述 某服务器系统升级内核至4.19.90-25.22.v2101版本后仍会触发oom导致java进程被kill。 现象分析 oom现象分析 系统messages日志分析&#xff0c;故…

python--实验15 数据分析与可视化

目录 知识点 1 数据分析概述 1.1流程 1.2定义 1.3数据分析常用工具 2 科学计算 2.1numpy 2.1.1定义 2.1.2创建数组的方式 2.1.3np.random的随机数函数 3 数据可视化 3.1定义 3.2基本思想 3.3Matplotlib库 3.3.1模块 4 数据分析 4.1Pandas 4.2数据结构 4.3基…

html+canvas 实现签名功能-手机触摸

手机上的效果图 需要注意&#xff0c;手机触摸和鼠标不是一个事件&#xff0c;不能通用&#xff0c;上一篇是关于使用鼠标的样例 相关代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewpo…

Large Language Model系列之一:语言模型与表征学习(Language Models and Representation Learning)

语言模型与表征学习&#xff08;Language Models and Representation Learning&#xff09; 1 语言模型 N-Gram模型 from collections import defaultdictsentences [The swift fox jumps over the lazy dog.,The swift river flows under the ancient bridge.,The swift br…

Java关于JDBC的理解

JDBC Java Database Connectivity&#xff1a;意为Java数据库连接。是Java提供的一组独立于任何数据库管理系统的API。Java提供接口规范&#xff0c;由各个数据库厂商提供接口的实现&#xff0c;厂商提供的实现类封装成jar文件&#xff0c;也就是我们俗称的数据库驱动jar包。我…

PyTorch张量数值计算

文章目录 1、张量基本运算2、阿达玛积3、点积运算4、指定运算设备⭐5、解决在GPU运行PyTorch的问题 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;专注于Java领域学习&#xff0c;擅长web应用开发、数据结构和算法&am…

LDR6020:重塑iPad一体式有线键盘体验的创新力量

在移动办公与娱乐日益融合的时代&#xff0c;iPad凭借其强大的性能和便携性&#xff0c;成为了众多用户不可或缺的生产力工具。然而&#xff0c;为了进一步提升iPad的使用体验&#xff0c;一款高效、便捷的键盘成为了不可或缺的配件。今天&#xff0c;我们要介绍的&#xff0c;…

云计算复习--虚拟化技术

文章目录 虚拟化技术定义与原理虚拟机监视器&#xff08;VMM&#xff09;虚拟化技术服务器虚拟化存储虚拟化网络虚拟化应用虚拟化 关键技术新型虚拟化技术发展进展作业 虚拟化技术定义与原理 定义&#xff1a;虚拟化技术是一种将计算机物理实体&#xff08;如服务器、存储设备…

【BUG】已解决:OSError: [Errno 22] Invalid argument

已解决&#xff1a;OSError: [Errno 22] Invalid argument 目录 已解决&#xff1a;OSError: [Errno 22] Invalid argument 【常见模块错误】 错误原因&#xff1a; 解决方法如下&#xff1a; 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&…

利用AI辅助制作ppt封面

如何利用AI辅助制作一个炫酷的PPT封面 标题使用镂空字背景替换为动态视频 标题使用镂空字 1.首先&#xff0c;新建一个空白的ppt页面&#xff0c;插入一张你认为符合主题的图片&#xff0c;占满整个可视页面。 2.其次&#xff0c;插入一个矩形&#xff0c;右键选择设置形状格式…

贝锐蒲公英远程运维方案:即装即用、无需专线,断网也可远程维护

目前&#xff0c;公路、隧道、桥梁、航道&#xff0c;甚至是施工现场和工业生产环境等&#xff0c;都采用了实时监测方案。 通过部署各类传感器和摄像头等设备&#xff0c;现场视频画面和控制单元&#xff08;如PLC、工控机等&#xff09;数据可以实时回传&#xff0c;用于集中…

智能优化算法之灰狼优化算法(GWO)

智能优化算法是一类基于自然界中生物、物理或社会现象的优化技术。这些算法通过模拟自然界中的一些智能行为&#xff0c;如遗传学、蚁群觅食、粒子群体运动等&#xff0c;来解决复杂的优化问题。智能优化算法广泛应用于各种工程和科学领域&#xff0c;因其具有全局搜索能力、鲁…

蚂蚁集团推出EchoMimic:能通过音频和面部标志生成逼真的肖像动画视频

蚂蚁集团最近推出了一项名为EchoMimic的新技术。能通过音频和面部标志生成逼真的肖像动画视频&#xff0c;让你的声音和面部动作被完美复制到视频中&#xff0c;效果自然如照镜子。 EchoMimic不仅可以单独使用音频或面部标志点生成肖像视频&#xff0c;也可以将两者结合&#…

【C++】16. set 和 map

在之前的博客中&#xff0c;我们已经接触过STL中的部分容器&#xff0c;比如&#xff1a;vector、list、deque等&#xff0c;这些容器统称为序列式容器&#xff0c;因为其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 我们这篇博客的内容是关联式容器&#xff…

在 Windows 上开发.NET MAUI 应用_1.安装开发环境

开发跨平台的本机 .NET Multi-platform App UI (.NET MAUI) 应用需要 Visual Studio 2022 17.8 或更高版本&#xff0c;或者具有 .NET MAUI 扩展的最新 Visual Studio Code。要开始在 Windows 上开发本机跨平台 .NET MAUI 应用&#xff0c;请按照安装步骤安装 Visual Studio 20…