- 浏览: 40715 次
- 性别:
文章分类
最新评论
选择排序
假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么选择排序的排序流程为:
- 在这个数组中找出最小值与第一个元素交换,现在数组为[0,1,3,2,8,4,2]
- 在这个数组中除了第一个位置的元素外找出最小值与第二个元素交换,因为第二个元素就是最小的所以此次没有发生变化。现在数组为[0,1,3,2,8,4,2]
- 在这个数组中除了第一个、第二个位置的元素外找出最小值与第三个元素交换,现在数组为[0,1,2,3,8,4,2]
- 在这个数组中除了第一个、第二个、第三个位置的元素外找出最小值与第四个元素交换,现在数组为[0,1,2,2,8,4,3]
- 在这个数组中除了第一个、第二个、第三个、第四个位置的元素外找出最小值与第五个元素交换,现在数组为[0,1,2,2,3,4,8]
- 在这个数组中除了第一个、第二个、第三个、第四个、第五个位置的元素外找出最小值与第六个个元素交换,因为第六个元素就是最小的所以此次没有发生变化。现在数组为[0,1,2,2,3,4,8]
现在整个数组是不是已经变得有序了呢。接下来我们看图解版本
接下来上代码
插入排序
相信大家都有打扑克的经历,那么我们今天的插入排序就以拿牌为例开始讲(注意只是举例,不是按打牌的规则哦)
- 我们拿到了一张牌3,我们把它放手里,现在手里有牌[3]
- 我们拿到了一张牌1,拿它与手里最后一张牌也就是3比较,发现1比3小,所以我们把它插入到3的前面,现在手里有牌[1,3]
- 我们拿到了一张牌0,拿它与手里最后一张牌也就是3比较,发现0比3小,所以我们把它插入到3的前面,接着与3的上一张比较发现0比1还小,那么就把0在插入到1的前面,现在手里有牌[0,1,3]
- 我们拿到了一张牌2,拿它与手里最后一张牌也就是3比较,发现2比3小,所以我们把它插入到3的前面,接着与3的上一张比较发现2比1大,那么就不需要动了,现在手里有牌[0,1,2,3]
- 我们拿到了一张牌8,拿它与手里最后一张牌也就是3比较,8比3大,那么就不需要动了,现在手里有牌[0,1,2,3,8]
- 。。。
现在你明白什么叫做插入排序了么?如果你不明白的话也没关系,我还专门画了一张图:
接下来上代码
<figure class="highlight dart"><table><tr> <td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td> <td class="code"><pre><span class="line"></span><br><span class="line"><span class="built_in">int</span> []<span class="built_in">num</span>=<span class="keyword">new</span> <span class="built_in">int</span>[]{<span class="number">3</span>,<span class="number">1</span>,<span class="number">0</span>,<span class="number">2</span>,<span class="number">8</span>,<span class="number">4</span>,<span class="number">2</span>};</span><br><span class="line"><span class="keyword">for</span> (<span class="built_in">int</span> i=<span class="number">1</span>,n=<span class="built_in">num</span>.length;i<n;i++){</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">num</span>[i]<<span class="built_in">num</span>[i<span class="number">-1</span>]){</span><br><span class="line"> <span class="keyword">for</span> (<span class="built_in">int</span> j=i;j><span class="number">0</span>;j--){</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">num</span>[j]<<span class="built_in">num</span>[j<span class="number">-1</span>]){</span><br><span class="line"> <span class="built_in">int</span> temp=<span class="built_in">num</span>[j];</span><br><span class="line"> <span class="built_in">num</span>[j]=<span class="built_in">num</span>[j<span class="number">-1</span>];</span><br><span class="line"> <span class="built_in">num</span>[j<span class="number">-1</span>]=temp;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="keyword">for</span> (<span class="built_in">int</span> i:<span class="built_in">num</span>){</span><br><span class="line"> System.out.<span class="built_in">print</span>(i+<span class="string">","</span>);</span><br><span class="line">}</span><br></pre></td> </tr></table></figure>快速排序
快速排序是一个运用了分治法和递归算法的排序方式。假如我们现在要排序的数组为[3,1,0,2,8,4,2]。那么在进行快速排序的时候我们先要进行一些准备:
- n作为一个数组中的标杆,一趟排序过后我们要把数组中所有大于n的数放在它的右边,所有小于n的放在它的左边。一般情况下我们会取数组第一个元素作为n,在此数组中就是n=3
- i我们使用i来找数组中大于标杆的值,i初始指向数组第一个位置
- j我们使用j来找数组中小于标杆的值,j初始指向数组最后一个位置
下面开始排序:
- 先从数组右边开始,我们发现j指向的元素2比标杆n小,那么我们将j指向的元素赋值给i指向的元素,停止操作。此时数组为[2,1,0,2,8,4,2],i指向第一个位置,j仍指向最后一个。
- 从数组左边开始,i指向的元素2比标杆小,所以不做操作,使i++,i指向的元素1比标杆小,所以不做操作,使i++,一直到i指向8的时候比标杆大(注意此处如果等于的话也要操作),那么就把i指向的元素赋值给j指向的元素,此时数组为[2,1,0,2,8,4,8],i指向第五个位置。也就是元素8,j仍然指向最后一个位置。
- 继续从右边操作,j指向的8不比n小,所以不做操作,j–,4不比3小,不做操作,j–。现在i和j的位置重合了,把n放到这个位置上。我们此轮的操作也就结束了
- 接下来我们把3所在的位置左边分为一个数组,右边位置分为一个数组再次进行刚才的操作。(此处就是一个递归调用了)
接下来就来看一个图片描述的过程
希尔排序
希尔排序呢,其实可以理解为插入算法排序的一个升级版了.
回忆一下当使用插入排序在进行排序数据量非常大的数据时,有一个很小的数据出现在了数组的最后,那么我们就要移动了这个数据前面所有的元素给它放置到合适的元素。例如:我们要排序的数组为[1,2,3,4,5,6,7,。。。此处省略一百万。。.,0]
相信大家肯定不喜欢这个0往前移动一百万此吧,希尔排序的出现其实就是为了解决这个问题的
希尔排序使用了分治算法,先把整个大的数组根据某个增量分为若干个组,先对这若干个组进行一个调整,保证大部分小的数据会被调整到前面来。到最后再次进行插入排序,这样就大大加快了效率了。
来一个例子,如图所示,我们要排序的数组为[3, 1, 0, 2, 8, 4, 2,6,9,1,3,-2,8],
- 上方图片所说的增量就是我们进行分组的依据了。我们在这里初始值取得是数组得2分之一(此值没有标准的定义,只需保证大于1且小于数组长度即可),而红线所指向得就是我们根据这个增量所分的组了,我们分别针对每组进行排序。
- 可以在增量为3的结果种看到,第一组3,2,8 变为了2,3,8、第二组第三组没变、第四组变为了1,2、第五组变为了3,8、第六组变为了-2,4.
- 接下来增量减半,我们的数组分为3组,分别进行排序。
- 现在增量值经过再次减半后已经变为1了,我们可以通过观察数组发现,在数组的后面基本不可能出现最小的数据了,现在对数组进行插入排序的效率已经非常高了
不知道现在的你明白希尔排序了么?来看一看代码吧
<figure class="highlight cpp"><table><tr> <td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td> <td class="code"><pre><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">shellSort</span><span class="params">(<span class="keyword">int</span> <span class="built_in">list</span>[], <span class="keyword">int</span> length)</span></span>{</span><br><span class="line"> <span class="keyword">int</span> gap,i,j,temp;</span><br><span class="line"> <span class="keyword">for</span> (gap = length/<span class="number">2</span>; gap > <span class="number">0</span>; gap /= <span class="number">2</span>){</span><br><span class="line"> <span class="keyword">for</span>(i = gap; i < length; i++){</span><br><span class="line"> <span class="keyword">for</span>(j = i-gap; j>=<span class="number">0</span> && <span class="built_in">list</span>[j]><span class="built_in">list</span>[j+gap]; j -= gap){</span><br><span class="line"> temp = <span class="built_in">list</span>[j];</span><br><span class="line"> <span class="built_in">list</span>[j] = <span class="built_in">list</span>[j+gap];</span><br><span class="line"> <span class="built_in">list</span>[j+gap] = temp;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td> </tr></table></figure>冒泡排序
冒泡排序在排序算法中效率算最慢的一类了,但是因为它简单的缘故仍然是工作1-3年的程序员面试经常会碰到的算法问题。
假如我们现在要排序的数组为[3,1,0,2,8,4,2]
- 第一轮排序为比较3和1,发现3比1大,那么我们就交换3和1,数组变成了[1,3,0,2,8,4,2]
- 比较3和0,发现3比0大,那么我们就交换3和0,数组变成了[1,0,3,2,8,4,2]
- 比较3和2,发现3比2大,那么我们就交换3和2,数组变成了[1,0,2,3,8,4,2]
- 比较3和8,发现3没有8大,那么不操作,数组还是[1,0,2,3,8,4,2]
- 比较8和4,发现8比4大,那么我们就交换8和4,数组变成了[1,0,2,3,4,8,2]
- 比较8和2,发现8比2大,那么我们就交换8和2,数组变成了[1,0,2,3,4,2,8]
- 现在第一轮的排序已经完成了,我们就筛选出来了最大值8,此时数字8已经在数组最后的位置了,下一轮排序我们就可以排除它了。第二轮排序为:比较1和0,发现1比0大,那么我们就交换1和0,数组变成了[0,1,2,3,4,2,8]
- 比较1和2,发现1没有2大,那么不操作,数组还是[0,1,2,3,4,2,8]
- 比较2和3,发现2没有3大,那么不操作,数组还是[0,1,2,3,4,2,8]
- 比较3和4,发现3没有4大,那么不操作,数组还是[0,1,2,3,4,2,8]
- 比较4和2,发现4比2大,那么我们就交换4和2,数组变成了[0,1,2,3,2,4,8]
- 现在第二轮排序完成了,数组最后的4和8是不是已经有序了呢
聪明的你是不是已经发现了冒泡排序的规律了呢,代码实现:
本文源码可见https://github.com/shiyujun/syj-study-demo
推荐阅读
- SpringCloud学习系列汇总
- 为什么一线大厂面试必问redis,有啥好问的?
- 多线程面试必备基础知识汇总
- Java集合源码分析汇总-JDK1.8
- Linux常用命令速查-汇总篇
- JVM系列文章汇总
- MySQL系列文章汇总
- RabbitMQ系列文章汇总
相关推荐
python五大排序-五大排序算法(Python),算法数据结构 五大常用算法
五大基本排序算法,算法数据结构(01) 五大常用算法
五大基本排序算法,算法数据结构(02) 五大常用算法
基础五大排序算法(冒泡+排序+插入+希尔+快速)简述,算法数据结构 五大常用算法
使用Python实现五大排序算法,算法数据结构 五大常用算法
插入排序 归并排序 堆排序 快速排序 基数排序
c++的几种常见的大小排序的算法的模板,包括冒泡排序、选择排序、木桶排序、快速排序等,这些不同的算法的复杂度和效率也不同,里面有说明
冒泡,选择,插入,Shell,快速排序的算法与实例
数字排序法:通常来说有五大类方法:插入排序(直接插入排序、希尔排序等)、交换排序(冒泡排序、快速排序)、选择排序(简单选择排序、树形选择排序、堆排序)、归并排序、基数排序
Matlab实现五大排序算法(冒泡、插入、选择、合并、快速) Test文件为测试文件,打开测试文件,要测试某个算法就把它的函数名前的"%"注释符去掉。
提供五种排序算法的C++实现方法,输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现...
算法课程实验一五种排序算法的分析比较实验目的掌握选择排序、插入排序、冒泡排序、快速排序、归并排序五种排序算法原理,并实现上述算法;
// 归并排序// 存放LEN个随机数// 排序后的数组// 归并用的数组// 产生1-100的随机数// 输出随机值// 冒泡// 选择排序// 插入排序,d
数据结构中经典的5种排序方法,简单排序 快速排序 冒泡排序 希尔排序 直接插入排序,共有5个CPP文件,每个文件包含一种算法,运行的时候可把其他的注释掉,直接运行其中一个既可。
排 序 算 法种类繁多,但就其排序时所遵循的原则分类,则大致可分为五大类:一厂插人排序.,交换 排序寒选择排序忿归并排序③基数排序,在这五大类方法中常用且重要的排序方法分为三大类:插入 排序、交换排序、选择...
基数排序:LSD法:先按最低关键字位k1对待排序数据中的n个值进行排序,按k1值把待排序文件中的n个记录分配到具有不同k1值的若干个堆,然后按k1值从小到大的次序收集在一起,下次再按高一位关键子位k2的值进行分配和...
五种全面的排序算法,除了你熟悉的冒泡法、选择法,你还有用过其它的吗?那就下载看看吧! 五子棋是一种受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性。这里设计和实现了一个人机对下的...
假设要排序的数组是A[1]……A[N],首先任意选取一个数据(通常选用第一个数据)作为关键数据,然后将所有比它的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一躺快速排序。一躺快速排序的算法是: ...
(1)数据结构与算法概念...(15)排序算法(五)——快速排序 (16)排序算法(六)——希尔排序 (17)排序算法(七)——堆排序 (18)排序算法(八)——基数排序 (19)排序算法(九)——八大排序算法总结