技术分享之八大排序算法(均已以升序为例)

简介:

一、排序名称

内部排序:指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。其中快速排序的是目前排序方法中被认为是最好的方法。

1、插入排序:直接插入排序、(shell)希尔排序

2、交换排序:冒泡排序、快速排序

3、选择排序:简单选择排序、堆排序

4、归并排序

5、基数排序

 

外部排序:指的是大文件的排序,即待排序的记录存储在外存储器(硬盘…)上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

例如:将原文件分解成多个能够一次性装入内存的部分分别把每一部分调入内存完成排序。然后,对已经排序的子文件进行归并排序。内存才2G,外存有1000G待排序文件 = 500个 x 2G,然后每2G转入内存进行排序,排完序写入外存, 最后将500个排好序的文件进行归并排序。

 

二、性能元素

1、稳定性 

(1)通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。例如:{ 2 5 3 7 10 7 9} —>  { 2 3 5 7 7 9 10} ,一次排序后,红色的"7"还是在绿色的"7"前面。

(2)稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序在高位也相同时是不会改变的。

     

2、时间复杂度 T(n)=O(f(n))

(1)算法的时间复杂度O(n)是一个问题规模n函数,没有严格的定义,它定量描述了该算法的运行所需要的时间。衡量一个算法的效率,如果以每条代码的实际执行次数,虽然精确,但十分烦琐。因此人们设计了用数量级的方法来衡量算法效率,如甲程序的执行次数为2n(n为数据量个数),乙为 3n+2,则当 n 很大时,认为甲乙是等数量级的,是等效率的

(2)时间频度不同(一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)),但时间复杂度可能相同。如:T(n)=n^2+3n与T(n)=n^2+4n它们的频度不同,但时间复杂度相同,都为O(n^2)。

(3)时间复杂度比较简单的计算方法是:看看有几重for循环,没有循环时间复杂度为O(1),只有一重则时间复杂度为O(n),二重则为O(n^2),依此类推,如果有二分则为O(logn),二分例如快速幂、二分查找,如果一个for循环套一个二分,那么时间复杂度则为O(nlogn)。

 

3、空间复杂度 S(n)=O(f(n))

(1)它也是问题规模n的函数,S(n)定义为一个算法在运行过程中临时占用辅助存储空间大小的量度。

(2)算法的空间复杂度一般也以数量级的形式给出。

   当一个算法的空间复杂度为一个常量,即不随被处理数据量n的大小而改变时,可表示为O(1);

   当一个算法的空间复杂度与以2为底的n的对数成正比时,可表示为O(log2n);

   当一个算法的空间复杂度与n成线性比例关系时,可表示为O(n)。

 

三、性能总结

 

 

四、分别介绍

1、简单选择排序

思想:

   一句话概括就是依次按位置挑选出适合此位置的元素来填充。

过程:

(1)暂定第一个元素为最小元素,往后遍历,逐个与最小元素比较,若发现更小者,与先前的"最小元素"交换位置。达到更新最小元素的目的。

(2)一趟遍历完成后,能确保刚刚完成的这一趟遍历中,最的小元素已经放置在前方了。然后缩小排序范围,新一趟排序从数组的第二个元素开始。

(3)在新一轮排序中重复第1、2步骤,直到范围不能缩小为止,排序完成。

示例:

以下为选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

  第1趟:12与49索引交换:12 {27 65 97 76 49 38}

  第2趟:27不动 :            12 27 {65 97 76 49 38}

  第3趟:65与38索引交换:12 27 38  {97 76 49 65}

  第4趟:97与49索引交换:12 27 38 49   {76 97 65}

  第5趟:76与65索引交换:12 27 38 49 65   {97 76}

  第6趟:97与76索引交换:12 27 38 49 65 76 97 完成

核心代码:

 

2、冒泡排序

思想:

    一句话概括就是将待排序的元素看作是竖着排列的“气泡”,较小的元素比较轻,浮在上面,较大的元素往下沉。

过程:

(1)在一趟遍历中,不断地对相邻的两个元素进行排序,小的在前大的在后,这样会造成大值不断沉底的效果,当一趟遍历完成时,最大的元素会被排在后方正确的位置上。

(2)然后缩小排序范围,即去掉最后方位置正确的元素,对前方数组进行新一轮遍历,重复第1步骤。直到范围不能缩小为止,排序完成。

示例:

以下为选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

  第1趟:97沉底:{ 49 27 65 76 12 3897

  第2趟:76沉底:{ 49 27 65 12 38 } 76 97

  第3趟:65沉底:{ 49 27 12 38 } 65 76 97

  第4趟:49沉底27 12 38 } 49 65 76 97

  第5趟:38沉底:27 12 } 38 49 65 76 97

  第6趟:27沉底:{ 12 } 27 38 49 65 76 97

      第7趟:12沉底:12  27 38 49 65 76 97 完成 

核心代码:

 

3、直接插入排序

思想:

插入排序是从一个乱序的数组中依次取值,插入到一个已经排好序的数组中,比较的两个记录跨度为1。可以想象一下打扑克牌插牌时的情景。这看起来好像要两个数组才能完成,但如果只想在同一个数组内排序,也是可以的。此时需要想象出两个区域:前方有序区和后方乱序区。

某些情况下效率很高:1、记录本身基本有序   2、记录数比较少

过程:

(1)分区。开始时前方有序区只有一个元素,就是数组的第一个元素。然后把从第二个元素开始直到结尾的数组作为乱序区。

(2)从乱序区取第一个元素,把它正确插入到前方有序区中。把它与前方有序区的最后一个元素比较,亦即与它的前一个元素比较。

  • 如果比前一个元素要大,则不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。
  • 如果和前一个元素相等,则继续和前二元素比较、再和前三元素比较......如果往前遍历到头了,发现前方所有元素值都一样,那也可以不需要交换,这时有序区扩充一格,乱序区往后缩减一格,相当于直接拼在有序区末尾。
  • 如果比前一个元素小,则交换它们的位置。交换完后,继续比较取出元素和它此时的前一个元素,若更小就交换,若相等就比较前一个,直到遍历完成。
  • 至此,把乱序区第一个元素正确插入到前方有序区中。

(3)往后缩小乱序区范围,继续取缩小范围后的第一个元素,重复第2步骤。直到范围不能缩小为止,排序完成。

示例:

以下为选择排序的存储状态,其中大括号内为无序区,大括号外为有序序列:

初始序列:{49 27 65 97 76 12 38}

  第1趟:无序区的27添加到有序区49的前面 {27 49} { 65 97 76 12 38}

  第2趟:无序区的65添加到有序区49的后面 {27 49 65} { 97 76 12 38}

  第3趟:无序区的97添加到有序区65的后面 {27 49 65 97} { 76 12 38}

  第4趟:无序区的65添加到有序区97的前面,49的后面 {27 49 65 76 97} { 12 38}

  第5趟:无序区的76添加到有序区97的前面,65的后面 {12 27 49 65 76 97} { 38}

  第6趟:无序区的12添加到到有序区27的前面 {12 27 49 65 76 97} {38}

      第7趟:无序区的38添加到到有序区49的前面,27的后面  {12 27 38 49 65 76 97} 完成

核心代码:

 

4、快速排序

思想:

通过一趟排序将要排序的数据分割成独立的两部分:分割点左边都是比它小的数,右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

过程:

 

示例:

上图中,演示了快速排序的处理过程:

初始状态为一组无序的数组:2、4、5、1、3。

经过以上操作步骤后,完成了第一次的排序,得到新的数组:1、2、5、4、3。

新的数组中,以2为分割点,左边都是比2小的数,右边都是比2大的数。

因为2已经在数组中找到了合适的位置,所以不用再动。

2左边的数组只有一个元素1,所以显然不用再排序,位置也被确定。(注:这种情况时,left指针和right指针显然是重合的。因此在代码中,我们可以通过设置判定条件left必须小于right,如果不满足,则不用排序了)。

而对于2右边的数组5、4、3,设置left指向5,right指向3,开始继续重复图中的一、二、三、四步骤,对新的数组进行排序

核心代码:

 

5、堆排序

堆:堆是一棵顺序存储的完全二叉树。

其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。

其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。

举例来说,对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时,称之为堆:

(1) Ri <= R2i+1  Ri <= R2i+2 (小根堆)

(2) Ri >= R2i+1  Ri >= R2i+2 (大根堆)

其中i=1,2,…,n/2向下取整; 

 

思想(最大堆进行升序排序):

① 初始化堆:将数列a[1...n]构造成最大堆。

② 交换数据:将a[1]和a[n]交换,使a[n]是a[1...n]中的最大值;然后将a[1...n-1]重新调整为最大堆。 接着,将a[1]和a[n-1]交换,使a[n-1]是a[1...n-1]中的最大值;然后将a[1...n-2]重新调整为最大值。 依次类推,直到整个数列都是有序的。整个过程就是:创建堆—堆排序—创建堆—堆排序......堆排序(Heap Sort)只需要一个记录元素大小的辅助空间(供交换用),每个待排序的记录仅占有一个存储空间。

过程:

(1)根据初始数组去构造初始堆(构建一个完全二叉树,保证所有的父结点都比它的孩子结点数值大),按层倒着选择非叶节点去比较。

(2)每次交换第一个和最后一个元素,输出最后一个元素(最大值),然后把剩下元素重新调整为大根堆。 当输出完最后一个元素后,这个数组已经是按照从小到大的顺序排列了。

示例:

(1)构建堆

   无序序列{ 1 , 3, 4, 5, 2, 6, 9,  7,  8,  0}

 

  (2)堆排序

 

核心代码:

 

6、希尔排序

思想:

又称为缩小增量排序,它也是一种插入排序。不过它是直接插入排序算法的一种威力加强版。把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。 

过程:

初始时,有一个大小为 10 的无序序列。

在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。

接下来,按照直接插入排序的方法对每个组进行排序。

在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。

按照直接插入排序的方法对每个组进行排序。

在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。

按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。

需要注意一下的是,图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到,在排序过程中,两个元素位置交换了。

示例:

核心代码:

 

7、归并排序

理解:

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。

将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

思想:

将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的有序表成对归并,得到n/2个长度为2的有序表;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

归并排序其实要做两件事:

(1)“分解”——将序列每次折半划分。

(2)“合并”——将划分后的序列段两两合并后排序。

过程:

1、先考虑第二步,如何合并?

在每次合并过程中,都是对两个有序的序列段进行合并,然后排序。

这两个有序序列段分别为 R[low, mid] 和 R[mid+1, high]。

先将他们合并到一个局部的暂存数组R2中,待合并完成后再将R2复制回R中。

为了方便描述,我们称 R[low, mid] 第一段,R[mid+1, high] 为第二段。

每次从两个段中取出一个记录进行关键字的比较,将较小者放入R2中。最后将各段中余下的部分直接复制到R2中。

经过这样的过程,R2已经是一个有序的序列,再将其复制回R中,一次合并排序就完成了。

2、其次,掌握了合并的方法,接下来,让我们来了解如何分解?其实就是折半划分,直到每一个有序序列长度为1结束。

示例:

 

核心代码:

8、基数排序

思想:

基数排序与本系列前面讲解的七种排序方法都不同,它不需要比较关键字的大小。它是根据关键字中各位的值,通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。

过程:

通过一个具体的实例来展示一下,基数排序是如何进行的。 

设有一个初始序列为: R {50, 123, 543, 187, 49, 30, 0, 2, 11, 100}。

我们知道,任何一个阿拉伯数,它的各个位数上的基数都是以0~9来表示的。

所以我们不妨把0~9视为10个桶。 

我们先根据序列的个位数的数字来进行分类,将其分到指定的桶中。例如:R[0] = 50,个位数上是0,将这个数存入编号为0的桶中。

分类后,我们在从各个桶中,将这些数按照从编号0到编号9的顺序依次将所有数取出来。

这时,得到的序列就是个位数上呈递增趋势的序列。 

按照个位数排序: {50, 30, 0, 100, 11, 2, 123, 543, 187, 49}。

接下来,可以对十位数、百位数也按照这种方法进行排序,最后就能得到排序完成的序列。位数不够的,在数字前面补充0后,再填桶。 

示例:

{50, 123, 543, 187, 49, 30, 0, 2, 11, 100}

50 30 0 100 11 2 123 543 187 49  个位

0 100 2 11 123 30 543 49 50 187  十位

0 2 11 30 49 50 100 123 187 543  百位

核心代码:

 

 

五、参考地址

稳定性:http://www.cnblogs.com/codingmylife/archive/2012/10/21/2732980.html

iOS演示:http://www.jianshu.com/p/70619984fbc6?utm_campaign=hugo&utm_medium=reader_share&utm_content=note&utm_source=weixin-friends

Java排序总结:http://www.jianshu.com/p/7d037c332a9d?utm_campaign=hugo&utm_medium=reader_share&utm_content=note&utm_source=weixin-friends

堆排序:http://www.cnblogs.com/skywang12345/p/3602162.html

程序猿神奇的手,每时每刻,这双手都在改变着世界的交互方式!
本文转自当天真遇到现实博客园博客,原文链接:http://www.cnblogs.com/XYQ-208910/p/6917708.html ,如需转载请自行联系原作者
相关文章
|
Web App开发 存储 算法
微信技术分享:微信的海量IM聊天消息序列号生成实践(算法原理篇)
如何优雅地解决“消息序列号只要保证顺序性而不需要兼顾唯一性”的问题呢?这就是本文所要分享的内容,强烈建议深入理解和阅读。
2974 0
|
3天前
|
机器学习/深度学习 算法 数据可视化
m基于PSO-LSTM粒子群优化长短记忆网络的电力负荷数据预测算法matlab仿真
在MATLAB 2022a中,应用PSO优化的LSTM模型提升了电力负荷预测效果。优化前预测波动大,优化后预测更稳定。PSO借鉴群体智能,寻找LSTM超参数(如学习率、隐藏层大小)的最优组合,以最小化误差。LSTM通过门控机制处理序列数据。代码显示了模型训练、预测及误差可视化过程。经过优化,模型性能得到改善。
18 6
|
1天前
|
缓存 算法
基于机会网络编码(COPE)的卫星网络路由算法matlab仿真
**摘要:** 该程序实现了一个基于机会网络编码(COPE)的卫星网络路由算法,旨在提升无线网络的传输效率和吞吐量。在MATLAB2022a中测试,结果显示了不同数据流个数下的网络吞吐量。算法通过Dijkstra函数寻找路径,计算编码机会(Nab和Nx),并根据编码机会减少传输次数。当有编码机会时,中间节点执行编码和解码操作,优化传输路径。结果以图表形式展示,显示数据流与吞吐量的关系,并保存为`R0.mat`。COPE算法预测和利用编码机会,适应卫星网络的动态特性,提高数据传输的可靠性和效率。
|
3天前
|
算法 调度
基于变异混合蛙跳算法的车间调度最优化matlab仿真,可以任意调整工件数和机器数,输出甘特图
**摘要:** 实现变异混合蛙跳算法的MATLAB2022a版车间调度优化程序,支持动态调整工件和机器数,输出甘特图。核心算法结合SFLA与变异策略,解决Job-Shop Scheduling Problem,最小化总完成时间。SFLA模拟蛙群行为,分组进行局部搜索和全局信息交换。变异策略增强全局探索,避免局部最优。程序初始化随机解,按规则更新,经多次迭代和信息交换后终止。
|
14天前
|
算法
基于GA-PSO遗传粒子群混合优化算法的VRPTW问题求解matlab仿真
摘要: 本文介绍了考虑时间窗的车辆路径问题(VRPTW),在MATLAB2022a中进行测试。VRPTW涉及车辆从配送中心出发,服务客户并返回,需在指定时间窗内完成且满足车辆容量限制,目标是最小化总行驶成本。文章探讨了遗传算法(GA)和粒子群优化(PSO)的基本原理及其在VRPTW中的应用,包括编码、适应度函数、选择、交叉、变异等步骤。同时,提出了动态惯性权重、精英策略、邻域搜索、多种群和启发式信息等优化策略,以应对时间窗限制并提升算法性能。
|
8天前
|
算法 JavaScript 决策智能
基于禁忌搜索算法的TSP路径规划matlab仿真
**摘要:** 使用禁忌搜索算法解决旅行商问题(TSP),在MATLAB2022a中实现路径规划,显示优化曲线与路线图。TSP寻找最短城市访问路径,算法通过避免局部最优,利用禁忌列表不断调整顺序。关键步骤包括初始路径选择、邻域搜索、解评估、选择及禁忌列表更新。过程示意图展示搜索效果。
|
8天前
|
机器学习/深度学习 算法
基于BP神经网络和小波变换特征提取的烟草香型分类算法matlab仿真,分为浓香型,清香型和中间香型
```markdown 探索烟草香型分类:使用Matlab2022a中的BP神经网络结合小波变换。小波分析揭示香气成分的局部特征,降低维度,PCA等用于特征选择。BP网络随后处理这些特征,以区分浓香、清香和中间香型。 ```
|
11天前
|
算法 调度 决策智能
基于自适应遗传算法的车间调度matlab仿真,可以任意调整工件数和机器数,输出甘特图
这是一个使用MATLAB2022a实现的自适应遗传算法解决车间调度问题的程序,能调整工件数和机器数,输出甘特图和适应度收敛曲线。程序通过编码初始化、适应度函数、遗传操作(选择、交叉、变异)及自适应机制进行优化,目标如最小化完工时间。算法在迭代过程中动态调整参数,以提升搜索效率和全局优化。
|
13天前
|
传感器 算法 安全
基于WSN网络的定向步幻影路由算法matlab仿真
该文探讨了无线传感器网络中的位置隐私保护,对比了NDRW路由与定向步幻影路由在安全时间和能耗方面的性能。在MATLAB2022a中进行测试,结果显示NDRW路由提供最长的安全时间,尤其在长距离传输时,且在近距离下能耗低于幻影路由。幻影路由虽消耗更多能量,但通过随机步创造幻影源以增强安全性。NDRW路由利用非确定性随机游走策略,避免拥堵并提高效率,而幻影路由则引入方向性控制,通过启发式算法优化路径选择。
|
12天前
|
算法
基于ADM自适应增量调制算法的matlab性能仿真
该文主要探讨基于MATLAB的ADM自适应增量调制算法仿真,对比ADM与DM算法。通过图表展示调制与解调效果,核心程序包括输入输出比较及SNR分析。ADM算法根据信号斜率动态调整量化步长,以适应信号变化。在MATLAB中实现ADM涉及定义输入信号、初始化参数、执行算法逻辑及性能评估。