永久的记忆——排序算法解析

[TOC]

冒泡排序

一队人按高矮排序,从第一个开始,和下一个比较,其中高的一个交换到后面。

然后第二个再和第三个比较,较高的交换到后面。

依次重复,第一次排完后,队伍中最高的将会被排到最后面。

然后剩下的n-1个人重复上面的动作,其中最高的又将排到n-1的最后,这样进行n-1次全部排完。

这样过程看起来就像每次排列中最高的那个人像气泡一样冒到最后。

所以比较次数为(n-1)+(n-2)+…+1=n(n-1)/2,即时间复杂度为O(n^2)

选择排序

一队人按高矮排序,第一个人依次与剩下的人进行比较,如果与他比较的人较矮,则交换位置。这样一个轮回下来,将得到队列里最矮的。

然后将最矮的排在第一个,剩下的重复刚才的动作,依次全部排完,得到最后的排列。

这样的比较次数为n-1+n-2+…+1=n(n-1)/2,即时间复杂度也为O(n^2)

插入排序

我们打扑克的时候,右手抓牌,插到左边的牌中,找到正确的位置插进去,左边的牌一直有序。这就是插入排序。

假设有一堆牌,从第二张开始,和第一张比较,如果第二张比第一张小,则交换。

然后第三张牌与已经排好的第二张比较,如果小于第二张,则依次交换,直到其大于其前面的牌为止。

后面重复之前的动作,直到最后一张牌插到前面正确的位置。

这样比较次数为1+2+…+n+1=n(n-1)/2,这样时间复杂度也是O(n^2),但是因为其排好的已经是有序的,只要不是原本已经有序的倒序排列,其效率是高于n^2的。而如果原本就是正向有序的,则时间复杂度变成n。如果是部分有序的,效率也很好。这也是希尔排序的基础。

希尔排序

希尔排序是对插入排序的改进,原理是将间隔h的元素变成有序的,这样的数组叫h有序数组。

实现时,第一次假设间隔为n/2,这样每个小组为两个元素。这时先对两个元素进行交换。

第二次间隔为n/4,这样每个小组为四个元素,这样之前排过的仍在同一组,不过合并了。这样效率也是不错的,对这样的小组进行插入排序。

然后间隔依次除以2,这样缩小增量,直到最后变成一组。然后再进行一次插入排序。这样效率很高。

归并排序

把大数据拆成若干个小问题的分治思想。把大数据拆到最后每个小数据只有一个数,然后开始两两合并,这就是归并(递归的合并)。

合并的时候方法如下,两组数,各自有序。两个指针,首先两个0位置的数比较,较小的放到新数组中,指针+1,剩下的两个位置最小的进行比较,小的放入新数组中,指针+1.最后一组剩下的数依次放入新数组。

快速排序

思路还是分治。首先选一个切分元素,把所有小于他的放左边,大于他的放右边。

然后左边,右边分别进行上面的子操作。无限切分下去直到最后每组两个,排好后所有数据就排好了。

排列方法,首先选一个切分元素,一般选第一个值下标0。

两个指针,分别从1,n-1开始向中间推进。

首先n-1向左推进,直到找到一个小于切分元素的值。然后1开始向右推进,直到找到第一个大于切分元素的值。交换这两个值。然后继续推进,直到全部交换完。然后把切分元素交换到中间合适的位置,排在第一个比他大的数前面。

然后对左边右边分别依次递归,最后完成排序。

堆排序

堆是一种树状结构,是一颗完全被填满的二叉树,底层的元素被从左到右填入,被称为完全二叉树。堆有堆序性,父亲总是大于或小于儿子。而每个节点和其兄弟节点没有顺序关系

完全二叉树有规律,可以使用一个数组表示而不需要指针。对于任意元素i,左儿子在2i,有儿子在2i+1,父亲在i/2.

所以用堆排序,只需要每次取最大元素,放到队列底部,就能完成排序。

堆一般包含插入操作和删除操作。插入时,先创建空穴,然后依次与父亲比较,依次上冒(交换),直到满足堆序性为止。与父亲比较使用i/2计算。

删除时,只能删除根节点,即最大值或最小值。

删除时,先删除根节点,然后把最后一个节点放到根节点,释放最后节点。

这时的根节点不是最大值或最小值。如果是最大堆,他要判断自己是否大于两儿子,如不是,找到两儿子中较大的交换。然后再依次与自己儿子进行比较,直到满足堆序性。

计数排序

高效的线性排序。原理是设置一个数组的索引值代表待排序元素的值,值来代表出现的次数。然后排列时,根据次数和值就知道该值应该排到什么地方。

这个方法有限制,首先是待排序的值只能是整形,还要知道最大的值,便于分配统计数组空间。

基数排序

也是一种线性排序。先把个位排序,然后对十位排序,然后最百位排序,依次排序最后得到有序。

桶排序

也是一种线性排序。方法如下,比如要排序的值在1~1000之间,每10个为一个桶,这样1~10在编号为1的桶,11~20在编号为2的桶,其中(i-1)*10+1,i*10存在i的桶里。

然后对每个桶进行排序,方法随便。

依次输出每个桶,即得到排序的数。

← 海量数据架构设计概念  TCP/IP详解读书笔记 →