赞
踩
排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常见的排序算法进行归纳。
我不喜欢死记硬背,我更偏向于弄清来龙去脉,理解性地记忆。比如下面这张图,我们将围绕这张图来思考几个问题。
上面的这张图来自一个PPT。它概括了数据结构中的所有常见的排序算法。现在有以下几个问题:
1、每个算法的思想是什么?
2、每个算法的稳定性怎样?时间复杂度是多少?
3、在什么情况下,算法出现最好情况 or 最坏情况?
4、每种算法的具体实现又是怎样的?
这个是排序算法里面最基本,也是最常考的问题。下面是我的小结。
一、直接插入排序(插入排序)。
1、算法的伪代码(这样便于理解):
INSERTION-SORT (A, n) A[1 . . n]
for j ←2 to n
do key ← A[ j]
i ← j – 1
while i > 0 and A[i] > key
do A[i+1] ← A[i]
i ← i – 1
A[i+1] = key
2、思想:如下图所示,每次选择一个元素K插入到之前已排好序的部分A[1…i]中,插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]>=K,则将K插入到A[x]的后面,插入前需要移动元素。
3、算法时间复杂度。
最好的情况下:正序有序(从小到大),这样只需要比较n次,不需要移动。因此时间复杂度为O(n)
最坏的情况下:逆序有序,这样每一个元素就需要比较n次,共有n个元素,因此实际复杂度为O(n2)
平均情况下:O(n2)
4、稳定性。
理解性记忆比死记硬背要好。因此,我们来分析下。稳定性,就是有两个相同的元素,排序先后的相对位置是否变化,主要用在排序时有多个排序规则的情况下。在插入排序中,K1是已排序部分中的元素,当K2和K1比较时,直接插到K1的后面(没有必要插到K1的前面,这样做还需要移动!!),因此,插入排序是稳定的。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。