位置: 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零基础小白到项目实战)

  • 纳税人办理退税流程
  • 应付税费重分类如何做会计分录?
  • 会计所得税公式怎么算
  • 汇算清缴银行手续费
  • 砂石行业一般纳税人税率多少?能简易征收吗?
  • 小规模纳税人季报还是月报?
  • 车辆停放服务属于交通运输服务吗
  • 个人取得什么收入不交税
  • 进销的单位不一样怎么办
  • 作废的支票银行怎么处理
  • 城市维护建设税怎么做分录
  • 应收账款融资的优缺点
  • 公司预存话费应该怎么做会计处理?
  • 上海市购销合同印花税计税金额怎么算?
  • 工程结算科目属于哪一类
  • 扣收手续费
  • 超市的商品进销表怎么做
  • 汽车折旧计算方法按照公里
  • vmware15虚拟机
  • 电脑上不了网怎么安装网卡驱动
  • 收到广告费收入怎么做分录
  • 收到发票怎么入库
  • window10设置wifi热点
  • 开源鸿蒙适配
  • 螃蟹不能和什么食物一起
  • 怀特岛郡国旗
  • mac怎么隐藏app
  • Mac SIP系统完整性保护开启及关闭的方法介绍
  • 单位未足额缴纳社保可以补交几年
  • 基于php技术
  • 山上覆盖着皑皑白雪
  • 发票点击了打印,然后怎么修改
  • 电子发票和纸质发票的法律效力
  • 山东省项目
  • 外管证预缴税费怎么算
  • gpt3 模型大小
  • display version命令
  • 支付职工差旅费发生的现金流出
  • 个人怎么开专票
  • 应付职工薪酬总账和明细账
  • 国税纳税申报表下载
  • 生产过程报废和返工产生的成本
  • php的框架
  • 收保险公司工伤怎么赔偿
  • 分公司可以单独上市吗
  • 加计抵减可以结转吗
  • 企业所得税多预缴了怎么办
  • 营业收入净额是销售收入净额吗
  • 增值税发票真假怎么查询
  • 小规模收入怎么算
  • 一般纳税人企业所得税税率多少
  • 售后服务维修收费制度
  • 母公司无偿给子公司房屋使用谁交房产税呢
  • 办公用品开普票几个点
  • 公司车辆购买保险申请
  • 固定资产清理增值税计税依据
  • 下乡扶贫可以报什么岗位
  • 科目汇总表账务处理程序登记总账的依据是
  • 完工结转的会计分录
  • win7 系统设置
  • linux进程管理实验总结
  • linux如何释放内存空间
  • mac怎么共享打印机设备
  • 苹果电脑Mac系统版本所对应的数字
  • centos chrony
  • win70x80073712解决方法
  • win8怎么修改电脑密码修改
  • perl入门
  • Cocos2d-x c++和java相互调用
  • nodejs writestream
  • nodejs rbac
  • 关于如何用好调查研究推动警务发展
  • android真机调试闪退
  • vue父子组件之间的通讯
  • ztree重新加载数据
  • node js模块
  • Python高手之路第3版PDF下载
  • js网页背景色
  • 安卓系统手机图片文件夹在哪里
  • 一个简单的javaweb项目
  • 免责声明:网站部分图片文字素材来源于网络,如有侵权,请及时告知,我们会第一时间删除,谢谢! 邮箱:opceo@qq.com

    鄂ICP备2023003026号

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

    友情链接: 武汉网站建设