排序算法经过了很长时间的演变产生了很多种不同的方法。对于初学者来说对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合很难通用。因此我们很有必要对所有常见的排序算法进行归纳。我不喜欢死记硬背我更偏向于弄清来龙去脉理解性地记忆。比如下面这张时间复杂度图我们将围绕这张图来分析。上面的这张图来自一个PPT。它概括了数据结构中的所有常见的排序算法给大家总结如下。区分稳定与不稳定快速、希尔、堆、选择不稳定其他排序算法均稳定。平均时间复杂度冒泡选择插入是O(n2)其他均是O(n*log2n)最坏时间复杂度冒泡选择插入快排是O(n2)其他是O(n*log2n)平均和最坏时间复杂度只有O(n2)和O(n*log2n)两种冒泡选择插入是O(n2)最坏情况下加一个快排其他均是O(nlog2n)。一、直接插入排序(插入排序)。1、算法的伪代码(这样便于理解)12345678INSERTION-SORT (A, n) A[1 . . n]forj ←2 to ndokey ← A[ j]i ← j – 1whilei 0 and A[i] keydoA[i1] ← A[i]i ← i – 1A[i1] key2、思想如下图所示每次选择一个元素K插入到之前已排好序的部分A[1…i]中插入过程中K依次由后向前与A[1…i]中的元素进行比较。若发现发现A[x]K,则将K插入到A[x]的后面插入前需要移动元素。3、算法时间复杂度。最好的情况下正序有序(从小到大)这样只需要比较n次不需要移动。因此时间复杂度为O(n)最坏的情况下逆序有序,这样每一个元素就需要比较n次共有n个元素因此实际复杂度为O(n­2)平均情况下O(n­2)4、稳定性。理解性记忆比死记硬背要好。因此我们来分析下。稳定性就是有两个相同的元素排序先后的相对位置是否变化主要用在排序时有多个排序规则的情况下。在插入排序中K1是已排序部分中的元素当K2和K1比较时直接插到K1的后面(没有必要插到K1的前面这样做还需要移动)因此插入排序是稳定的。二、希尔排序(插入排序)1、思想希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序然后,取第二个增量d2(d1),重复上述的分组和排序,直至所取的增量dt1例如将 n 个记录分成 d 个子序列{ R[0] R[d] R[2d]… R[kd] }{ R[1] R[1d] R[12d]…R[1kd] }…{ R[d-1]R[2d-1]R[3d-1]…R[(k1)d-1] }说明d5 时先从A[d]开始向前插入判断A[d-d]然后A[d1]与A[(d1)-d]比较如此类推这一回合后将原序列分为d个组。由后向前2、时间复杂度。最好情况由于希尔排序的好坏和步长d的选择有很多关系因此目前还没有得出最好的步长如何选择(现在有些比较好的选择了但不确定是否是最好的)。所以不知道最好的情况下的算法时间复杂度。最坏情况下O(N*logN)最坏的情况下和平均情况下差不多。平均情况下O(N*logN)3、稳定性。由于多次插入排序我们知道一次插入排序是稳定的不会改变相同元素的相对顺序但在不同的插入排序过程中相同的元素可能在各自的插入排序中移动最后其稳定性就会被打乱所以shell排序是不稳定的。(有个猜测方便记忆一般来说若存在不相邻元素间交换则很可能是不稳定的排序。)三、冒泡排序(交换排序)1、基本思想通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。2、时间复杂度最好情况下正序有序则只需要比较n次。故为O(n)最坏情况下: 逆序有序则需要比较(n-1)(n-2)……1故为O(N*N)3、稳定性排序过程中只交换相邻两个元素的位置。因此当两个数相等时是没必要交换两个数的位置的。所以它们的相对位置并没有改变冒泡排序算法是稳定的四、快速排序(交换排序)1、思想它是由冒泡排序改进而来的。在待排序的n个记录中任取一个记录(通常取第一个记录),把该记录放入适当位置后,数据序列被此记录划分成两部分。所有关键字比该记录关键字小的记录放置在前一部分,所有比它大的记录放置在后一部分,并把该记录排在这两部分的中间(称为该记录归位),这个过程称作一趟快速排序。2、算法复杂度最好的情况下因为每次都将序列分为两个部分(一般二分都复杂度都和logN相关)故为 O(N*logN)最坏的情况下基本有序时退化为冒泡排序几乎要比较N*N次故为O(N*N)3、稳定性由于每次都需要和中轴元素交换因此原来的顺序就可能被打乱。如序列为 5 3 3 4 3 8 9 10 11会将3的顺序打乱。所以说快速排序是不稳定的五、直接选择排序(选择排序)1、思想首先在未排序序列中找到最小元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小元素然后放到排序序列末尾。以此类推直到所有元素均排序完毕。具体做法是选择最小的元素与未排序部分的首部交换使得序列的前面为有序。2、时间复杂度。最好情况下交换0次但是每次都要找到最小的元素因此大约必须遍历N*N次因此为O(N*N)。减少了交换次数