基础算法| 常用排序算法小结

日常吹水

说到这个算法,

可能瞬间大家就觉得那些灰机昏膏素什么的比这个生动活泼多了。

那么,正走在算法之路上的你,

是否还在苦苦寻求修仙之路?

是否被各种排序算法欺负得苦不堪言?

那还等什么,快进来看看

带你全程装逼加一路向西!

刺不刺激?高不高能?

内容提要:

*排序常用术语介绍

*冒泡排序

*选择排序

*插入排序

*希尔排序

*归并排序

*快速 排序

排序基础知识

⚫排序的定义

将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。说得再通俗点,比如将一个班的人(数据元素)按照身高(关键字)站位,高的站前面,矮的站后面咯。

⚫ 排序的分类

排序可分为内排序和外排序。

所谓内排序就是所有的数据和操作都在内存中完成。

而外排序就是说需要排序的数据太大,无法全部塞进内存,需要在内存和外存之间多次数据交换才能完成的排序。

⚫算法优劣的术语说明

⚫稳定:如果Ai=Aj,开始Ai在Aj前面,排完序之后Ai依然在Aj前面。

⚫不稳定:

如果Ai=Aj,开始Ai在Aj前面,而排完序以后Ai有可能跑到Aj后面去了。

⚫时间复杂度:一个算法执行完所消耗的时间。

⚫空间复杂度:执行一个算法需要消耗的内存空间大小。

⚫常见算法的复杂度及稳定性

好了看完上面一堆头(dan)疼的术语介绍,

接下来将为大家介绍几种常用的内部排序算法,

开始我们的表演。

1

冒泡排序(Bubble Sort)

⚫常规冒泡排序

冒泡排序算是比较好理解的了。想小编当年入门的时候,就是仰仗着冒泡大法,从此踏入红尘,一去不返……呃这个扯远了,为什么叫冒泡呢?这个后面再解释。为了更好的说明问题,还是用一个数组A[n],以升序(降序方法一样)为例,来给大家一一讲解。

⚫基本原理:

1)从序列的最左边开始,将两两相邻的两个元素(例如A[0]和A[1], A[1]和A[2], A[2]和A[3]等等)进行比较。将小的放左边,将大的放右边。例如A[i] > A[i+1],那么就交换A[i]和A[i+1]的位置。那么经过一轮比较交换以后,A[n]里的值必然是A[0]~A[n]中的最大值。

2) 对剩下的元素A[0]~A[n-1]也进行上述操作。完成后A[n-1]里面存的就是A[0]~A[n-1]中的最大值。

3) 不断对剩下的元素进行上述操作,直到剩下元素只有A[0]时,排序完成。

看不懂嘛?那来试试图片吧:

好了,讲完了基本原理,来看看具体代码是如何实现的吧。

可以看到,在冒泡后,相等元素的位置并不会改变。因此,冒泡算法是稳定的。

⚫ 冒泡排序改进版

此方法可称为定向冒泡排序,它和冒泡排序的不同之处在于,定向冒泡从左到右把最大数搬到最后面的时候,再反向从右往左把最小值搬到最左边。这种方法稍微比传统冒泡好上那么一丢丢。具体实施看代码。

不理解嘛?没关系,小编还为大家准备了动态图。

定向冒泡的优势,比如对序列{4, 5, 6, 7, 8, 2}排序,传统冒泡要访问5次序列,而定向冒泡排序只需要访问一次就OK了。

2

选择排序(Selection Sort)

说到选择排序,这个也是灰常易于理解的。相信大家看一眼基本原理就懂了。还是以数组A[n]与升序排列为例说明问题。

基本原理:

1)先从A[0]~A[n]中找最小的元素A[i],交换A[0]和A[i]的位置。

2)再从剩下的元素A[1]~A[n]中找最小的元素A[j],交换A[1]和A[j]的位置。

3)不断在剩下的元素中找最小的元素丢到开头,直到剩下最后一个元素。

还不懂?再来看看个图片:

代码哪能少?

选择排序每次将最小值丢到开头的时候,有可能会打乱相等元素的位置。因此,它是不稳定的。也注意区分其和冒泡排序的区别:冒泡排序通过依次交换相邻两个顺序不合法的元素位置,从而将当前最小(大)元素放到合适的位置;而选择排序每遍历一次都记住了当前最小(大)元素的位置,最后仅需一次交换操作即可将其放到合适的位置。

3

插入排序(Insertion Sort)

大家打过扑克牌嘛?我们在对手上的扑克牌进行排序的时候,是不是将右手上的牌插到左手上已经排序好的牌之间?这跟我们的插入排序是有点类似的。

还是以A[n]为例说明问题。

基本原理:

1)从A[0]开始,则A[0]可认为是已排序列。

2)取出下一个元素(比如A[1]),在已排序列中从右往左扫描,如果已排序列中的元素大于取出的元素,那么就将该元素(已排序列中的)往后挪一个位置。

3)直到在已排序列中找到一个小于等于取出元素的元素。将取出元素插入该元素(已排序列中的)后一个位置。

4)不断重复步骤2-3.直到所有元素都插入到已排序列。

还不明白?看看图片

请问代码在哪里???

亲,这么详细的注释,

别跟我说你看不懂

可以看出,关于相等元素,排序前后并不会改变他们的位置。因此,插入排序又是稳定的。

4

希尔排序(Shell Sort)

希尔排序,也叫递减增量排序,是插入排序的一种更高效的改进版本。其中希尔排序是基于以下几点做出改进的:

1)直接插入排序对于几乎排好的数据有着极高的效率。基本可以达到线性排序时的效率。

2)但是对于一般的乱序数据来说,直接插入排序由于每次只能将数据往后搬一位,从这点上来说它效率又是及其低下的。

基本原理:

1)将无序数据分割为若干个子序列,子序列不是逐段分割的,而是相隔特定的增量的子序列,对各个子序列进行直接插入排序;

2)然后再选择一个更小的增量,再将数据分割为多个子序列进行直接插入排序......

3)不断重复步骤2,直到最后增量变为1,即对所有数据使用直接插入排序(此时所有数据几乎都排好了,直接插入效率较高),最终排序完成。

唉,小编就不指望你们能看懂,还是来看看图片吧。

关于不同增量的选取对于希尔排序性能的影响,有不同的观点。这里就不过多赘述。

代码!代码!代码在哪里!!!???

值得一提的是,由于数据划分为多个区域,在每个区域中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱。因此希尔排序是不稳定的排序。

5

归并排序(Merge Sort)

小伙子,你造归并吗?

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。效率为O(nlogn),1945年由冯·诺伊曼首次提出。归并排序的实现分为递归实现与非递归(迭代)实现。这里我们讨论递归实现。归并排序依赖于归并操作。归并操作(merge),也叫归并算法,指的是将两个顺序序列合并成一个顺序序列的方法。

基本原理:

1)申请内存空间A,大小为两个已排序列之和。

2)设定两个指针,分别指向两个已排序列的首元素。

3)比较两个指针指向的元素大小,将小的那个元素丢进内存空间A。同时指向该元素的指针向前移动一位。

4)不断重复步骤3),直到任何一个序列的元素全被丢进空间A。那么就把另外一个序列剩下的所有元素丢进空间A。

Understand?别说了,看图吧。

兄弟,来,干了这段代码。

归并排序是稳定的算法。

6

快速排序(Quick Sort)

1

1

终于说到这个大boss了。为什么叫快速排序呢?额,这个倒不是因为它很快。

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:开始选取一个基准数,通过一趟排序将基准数移到序列的合适位置,使得,左边的这部分都小于等于基准数,右边的部分都大于等于基准数,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

那么,对于一个序列,怎样才能使基准数移动到正确位置,以便能使左边的数都小于等于它,右边的数都大于等于它呢?还是以数组A[N]为例,为大家慢慢道来:

1)设置两个变量i、j,排序开始的时候:i=0,j=N;

2)以第一个数组元素作为关键数据,赋值给key,即key=A[0];

3)从j开始向前搜索,即由后开始向前搜索(j--),找到第一个小于key的值A[j],将A[j]和A[i]互换;

4)从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;

5)重复第3、4步,直到i=j;

6)3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束。

还是来看看图吧:

聪明的同学已经发现了,当序列中的每个元素都归位的时候,整个序列也就都变得有序了。

看完了图解是不是感觉贼得劲儿了呢??

看代码:

快速排序是不稳定的排序算法。

OK自此,常用的排序算法已经介绍完毕,今天的表演到此结束,谢谢大家。

最后再多说两句

这次内容量有点大啊

小伙伴们要耐下心来多看几遍

不懂就再多看几遍

最近天气变冷了,大家修仙学习的时候也多注意身体。

不要像小编一样……

最后谢谢大家的支持,共勉共进。

祝大家早日练就大佬的姿态

1

END

编辑:邓发珩(华中科技大学管理学院本科一年级,2638512393@qq.com,个人公众号:程序猿声)

代码: 邓发珩

指导老师:秦时明岳(professor.qin@qq.com)

原文发布于微信公众号 - 数据魔术师(gh_39567a079597)

原文发表时间:2017-11-20

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-551-Student Attendance Record I(判断是否出现连续几个相同字符)

14760
来自专栏武军超python专栏

2018年7月25日python中面向对象编程的练习

今天遇到的新单词: parameter  n参数 IndentationError  n缩进错误 formatting n格式化

43240
来自专栏云霄雨霁

子字符串查找----Rabin-Karp算法(基于散列)

26400
来自专栏chenjx85的技术专栏

leetcode-162-寻找峰值

给定一个输入数组 nums,其中 nums[i] ≠ nums[i+1],找到峰值元素并返回其索引。

22430
来自专栏青玉伏案

窥探Swift之基本数据类型

  在上一篇博客“窥探Swift编程之在Playground上尽情的玩耍”中介绍了如何使用Playground来学习Swift语言。本篇博客就使用Playgro...

21050
来自专栏醒者呆

面向程序员编程——精研排序算法

这篇文章很长,我花了好久的时间(中间公司出了bug,加班了好几天( ¯ ¨̯ ¯̥̥ ))进行整理,如有任何疑问,欢迎随时留言。 关键字:排序算法,时间...

39050
来自专栏云霄雨霁

排序----希尔排序

16500
来自专栏斑斓

函数式非凡的抽象能力

如果说面向对象思想是物质世界的哲学观,则函数式思想展现的就是纯粹的数学思维了。函数作为一等公民,它不代表任何物质(对象),而仅仅代表一种转换行为。是的,任何一个...

34650
来自专栏开发技术

排序之希尔排序(shell sort)

本篇博客是在伍迷兄的博客基础上进行的,其博客地址点击就可以进去,里面好博客很多,我的排序算法都来自于此;一些数据结构方面的概念我就不多阐述了,伍迷兄的博客中都...

14330
来自专栏牛客网

校招面试手撕算法汇总

所有题目都是从面经中提取而来,持续更新。 本人也是菜鸟一枚,帖子也会相应的发布自己对于题目的解法和看法,但是可能想得不够,也希望大家能够一起讨论,一起进步。 1...

422110

扫码关注云+社区

领取腾讯云代金券