03月21, 2019

【数据结构】排序

排序不仅仅在计算机科学中经常使用,在现实生活中,我们也经常会遇到排序,例如学生的成绩、GPA,哪怕我们打牌的时候也会按照花色、大小排序(如果你打牌不排序,当我没说。。。)。在计算机科学中,排序更是随处可见。Dota2天梯榜、淘宝找最贵的娃娃,都用到了排序。排序算法有很多,这节课介绍几个最常见的。

##插入排序 这个其实就是打牌在起牌阶段整理手牌的过程,一般都是按照从小到大或者从大到小的顺序先拿着手牌,每次起一张新牌,会把牌“插入”到现有的手牌中,使得它比前面的牌大,比后面的牌小。 举个例子:

冒泡排序

在上第一节体育课的时候应该会先给大家排位置,冒泡排序的过程是这样的:第一个同学和第二个同学比一下身高,咦2比1低,高个往后排去,1和2交换位置,然后站在第二的同学再和站在第三的同学比个子,以此类推,一直到队尾,那么经过这一轮的交换,个子最高的同学肯定站在队尾了,接着在重头开始交换,直到排完队。

举个例子:

快速排序

可以说是最最经典的排序算法,没有之一。还是拿体育课排队来讲吧。体育老师随便抽了其中一个同学,然后对大家说:“比这个同学高的站在他右边,比他低的站在他左边”,经过这么一轮,可以肯定的是,左边的同学肯定比右边的同学都低。现在问题就变成了分别给左边和右边的同学排序。我们对左右两边的同学再用相同的方法,即从子队列中找一个同学,然后比他低的站左边,比他高的站右边。经过N多次这样的分组排序后,直到每个分组都排好序,那么整体的队列就排好序了。 举个例子:

归并排序

打牌都洗过牌吧,花式洗牌的一种,就是把一副牌分成两份,然后交叉洗进去,归并排序和这种洗牌方式很相近,原理都是把两部分牌洗在一起(归并在一起)只不过我们平常洗牌都是想把牌序打乱。假如让你把一副牌按照大小顺序洗好呢?我们可以每次把牌均分成两份,所谓一生二、二生四、四生八,把每份洗好,然后归并在一起,整副牌就洗好了。 举个例子:

本文链接:http://www.yuqiaochuang.com/post/【数据结构】排序.html

-- EOF --

Comments

""