位置: IT常识 - 正文

十大经典排序算法(下)(十大经典排序算法(动图演示C 实现))

编辑:rootadmin
十大经典排序算法(下)

推荐整理分享十大经典排序算法(下)(十大经典排序算法(动图演示C 实现)),希望有所帮助,仅作参考,欢迎阅读内容。

文章相关热门搜索词:十大经典排序算法,十大经典排序算法总结,十大经典排序算法菜鸟教程,十大经典排序算法菜鸟教程,十大经典排序算法java,十大经典排序算法总结,十大经典排序算法java,十大经典排序算法总结,内容如对您有帮助,希望把文章链接给更多的朋友!

🍓个人主页: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. 算法步骤

从数列中挑出一个元素,称为 "基准"(pivot);

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

递归地(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. 算法步骤

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

把堆首(最大值)和堆尾互换;

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

十大经典排序算法(下)(十大经典排序算法(动图演示C 实现))

重复步骤 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 桶排序

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

在额外空间充足的情况下,尽量增大桶的数量使用的映射函数能够将输入的 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; }}
本文链接地址:https://www.jiuchutong.com/zhishi/299399.html 转载请保留说明!

上一篇:2021年Windows下安装GPU版本的Tensorflow和Pytorch(windows2022下载)

下一篇:2022 uniapp基础掌握及面试题整理(uniapp零基础小白到项目实战)

  • 小米pay怎么支付(小米pay支付不用指纹)

    小米pay怎么支付(小米pay支付不用指纹)

  • qq音乐会员下载的歌曲是永久的吗(qq音乐会员下载歌曲怎么保存到本地)

    qq音乐会员下载的歌曲是永久的吗(qq音乐会员下载歌曲怎么保存到本地)

  • 淘宝揽件超时有惩罚吗(淘宝揽收超时会对卖家什么影响)

    淘宝揽件超时有惩罚吗(淘宝揽收超时会对卖家什么影响)

  • hp126a显示hp双闪同闪(惠普126双灯闪)

    hp126a显示hp双闪同闪(惠普126双灯闪)

  • 拍抖音怎么在屏幕上显示歌词(拍抖音怎么在屏幕上显示歌曲的字)

    拍抖音怎么在屏幕上显示歌词(拍抖音怎么在屏幕上显示歌曲的字)

  • 网线过长解决方法(网线太长怎么解决怎么收拾)

    网线过长解决方法(网线太长怎么解决怎么收拾)

  • 360路由器初始密码(360路由器初始密码自定义)

    360路由器初始密码(360路由器初始密码自定义)

  • 荣耀手机nfc功能怎么打开(荣耀手机nfc功能怎么使用公交卡)

    荣耀手机nfc功能怎么打开(荣耀手机nfc功能怎么使用公交卡)

  • 手机qq关闭黄钻标识(手机qq怎么关闭黄钻显示)

    手机qq关闭黄钻标识(手机qq怎么关闭黄钻显示)

  • applecare是什么(applecare是什么服务有用吗)

    applecare是什么(applecare是什么服务有用吗)

  • 腾讯王卡微博免流吗(腾讯王卡微博免流么)

    腾讯王卡微博免流吗(腾讯王卡微博免流么)

  • win10笔记本要不要装杀毒(笔记本window10要更新吗)

    win10笔记本要不要装杀毒(笔记本window10要更新吗)

  • 用户数据是什么意思(用户数据是啥意思)

    用户数据是什么意思(用户数据是啥意思)

  • i11蓝牙耳机是什么牌子(i11蓝牙耳机是杂牌吗)

    i11蓝牙耳机是什么牌子(i11蓝牙耳机是杂牌吗)

  • 快手下载人家作品知道吗(快手下载他人作品会通知他人吗)

    快手下载人家作品知道吗(快手下载他人作品会通知他人吗)

  • 电脑桌面横过来了怎么调回去(电脑桌面横过来了怎么调回去win7)

    电脑桌面横过来了怎么调回去(电脑桌面横过来了怎么调回去win7)

  • 如何手机远程控制电脑(如何手机远程控制平板)

    如何手机远程控制电脑(如何手机远程控制平板)

  • 金立gn5007手机忘记密码怎么办(金立忘记手机密码怎么办啊?)

    金立gn5007手机忘记密码怎么办(金立忘记手机密码怎么办啊?)

  • 小米6x手机放大镜在哪里(小米6手机放大器在哪里打开)

    小米6x手机放大镜在哪里(小米6手机放大器在哪里打开)

  • 拼多多里面的金猪老是在页面上怎么关了它(拼多多里面的金币是怎么来的)

    拼多多里面的金猪老是在页面上怎么关了它(拼多多里面的金币是怎么来的)

  • ppt全选快捷键(ppt全选按什么键)

    ppt全选快捷键(ppt全选按什么键)

  • 什么软件可以给视频加边框(什么软件可以给视频加字幕)

    什么软件可以给视频加边框(什么软件可以给视频加字幕)

  • 苹果14新功能有哪些详细介绍(苹果14.5新功能)

    苹果14新功能有哪些详细介绍(苹果14.5新功能)

  • 计提增值税比实际缴纳多
  • 两地发工资个税处理
  • 城市维护建设税是什么意思
  • 人员经费包括哪些方面?
  • 小规模纳税人冲红退税吗
  • 申报个人所得税是按应发工资还是实发工资
  • 减半征收的印花税缴纳所得税吗
  • 金税盘一年
  • 注册了公司没有经营会怎么样
  • 公司投资控股其他公司如何做账务处理
  • 个人所得税该如何缴纳
  • 转让土地使用权一般计税方法
  • 公司清算往来科目应该怎么处理?
  • 公司牌车还款从哪里扣款
  • 实际入库数量怎么算
  • 旅游费开票内容
  • 材料未验收入库属于哪个科目
  • 营改增后企业取得的不动产可以抵扣进项
  • 固定资产增值税怎么抵扣
  • 开具发票时,哪些备注事项需要被重视?
  • 科目余额表借方和贷方
  • 高新企业国家补助收入怎么入账
  • 哪些票据可以冲抵增值税
  • 税控盘额度
  • 发给职工的交通补贴
  • 购买国外技术需要缴纳什么税
  • boot mac os from
  • 旅游公司广告费支出扣除标准
  • win11安卓子系统教程
  • 栈定义代码
  • 个体户工商年报异常怎么解除
  • 银行承兑汇票开出后可以撤销吗?
  • windows11搜索
  • php的数组函数
  • 股东借款给公司会计分录
  • 我整理的邪恶铭刻所有卡牌及自制卡
  • thinkphp ide
  • 出口商品怎么做分录
  • 房产税缴纳标准是多少
  • 增值税一般纳税人认定标准
  • 普通增值税发票会计科目怎么写?
  • 债务重组收益会计处理
  • 施工企业成本费用有哪些方面构成
  • pytorch如何学
  • vue3.0配置代理
  • 论文导语如何写
  • vue.mixin是什么
  • 营改增后房地产开发税费一览表
  • 速达建账套期初数据
  • 正解之途
  • 处理交易性金融资产增值税买价含佣金吗
  • 成本法和权益法的相同点
  • 经营性流动资产减去经营性流动负债
  • 购入研发设备可以全额抵扣吗
  • 销售租赁服务税率
  • 企业承担个人所得税分录怎么做
  • 技术服务费发票怎么开
  • 附报资料是什么
  • 私营公司固定资产怎么查
  • mysql基本教程
  • win8无法运行exe
  • centos 命令大全
  • win10怎么安装运行库
  • linux日期与时间
  • hppusg.exe
  • win8系统电脑
  • linux病毒排查
  • unity总结
  • opengl编程实例
  • linux bash中too many arguments问题的解决方法
  • 执行批处理命令
  • 快速备份mysql数据库
  • jquery crud
  • scrollview不滚动
  • Python装饰器入门学习教程(九步学习)
  • javascript如何学
  • html折叠
  • 税务局24小时人工服务电话
  • 关于房地产企业所得税涉税处理表述正确的有
  • 湖南电子税务局网上办税大厅
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

    网站地图: 企业信息 工商信息 财税知识 网络常识 编程技术

    友情链接: 武汉网站建设