专栏首页数据魔术师基础算法| 常用排序算法小结

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

日常吹水

说到这个算法,

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

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

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

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

那还等什么,快进来看看

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

刺不刺激?高不高能?

内容提要:

*排序常用术语介绍

*冒泡排序

*选择排序

*插入排序

*希尔排序

*归并排序

*快速 排序

排序基础知识

⚫排序的定义

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

⚫ 排序的分类

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

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

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

⚫算法优劣的术语说明

⚫稳定:如果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),作者:优创突击队

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 如何优雅地写出大规模线性规划的对偶

    对偶理论Duality Theory在运筹学数学规划部分占据着举足轻重的地位,也属于比较高阶的理论。Duality Theory在精确算法设计中也经常用到,在...

    用户1621951
  • 十大经典排序算法(动图演示,收藏好文)

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也...

    用户1621951
  • 人工智能|爱犯错的智能体--视觉篇(一):视觉倒像

    机器会犯错,其错要么是因为数据集太少,无法涵盖数据形成的样本空间;要么是由于训练太过精细,导致没办法对新来的样本或数据形成有效预计,俗称为过拟合;要么是模型本身...

    用户1621951
  • 硬核!C语言八大排序算法,附动图和详细代码解释!

    排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

    诸葛青云
  • 小白学排序 | 十大经典排序算法(动图)

    比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排序。非比较类排序:不通过比较来决定元素间的相对...

    机器学习炼丹术
  • 视觉直观感受 7 种常用的排序算法

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

    后端技术探索
  • 视觉直观感受 7 种常用的排序算法

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。...

    慕白
  • 视觉直观感受 7 种常用排序算法

    大数据文摘
  • 算法基础:五大排序算法Python实战教程

    排序是每个软件工程师和开发人员都需要掌握的技能。不仅要通过编程面试,还要对程序本身有一个全面的理解。不同的排序算法很好地展示了算法设计上如何强烈的影响程序的复杂...

    AI研习社
  • 程序员必备排序算法(1)

    排序算法算是比较简单面试过程中遇到最多的算法,一般我们所说的排序算法往往指的是内部排序算法,即数据记录在内存中进行排序。

    PM小王

扫码关注云+社区

领取腾讯云代金券