各类排序算法

常见的排序算法原理及其python实现

常用的排序算法包括内排序以及外排序，内排序是指无需用到外存，所有操作全在内存中进行的排序方式，一般分类为：

在简单的总结之后，接下来我们会将各类算法进行一一详述，对其原理进行深入剖析，然后使用Python编程语言将其一一实现。

一、插入排序

1直接插入排序

直接插入排序是一种十分简单的排序算法，其基本思想和具体实现过程都不难，同时，我们会给出一幅排序过程图用以辅助理解。

基本思想：直接插入排序即在每步操作中，将一个待排序的记录，按其关键字的大小插入到已经排好序的有序数据中，直到所有的待排序记录都插完为止。

辅助理解过程图：（为节省时间，暂时不借助画图工具，直接手画，请勿见怪！）

图1：直接插入排序过程图

从图中我们可以清楚地理解整个直接插入排序是怎样一步步进行下去的。

Python代码实现

#_*_ coding: utf-8 _*_

#直接插入排序（升序排列）

"""

@:param:l:一个待排序的序列

@:return:l：一个排好序的序列

author: xc

time：2018-07-20

"""

definsertSort(l):

a =len(l)

iflis None:

return

ifa

returnl

foriinrange(a):#记录需要多少趟排序

p = i#标记每次待排序记录的索引位置

temp = l[i]#标记待排序记录值

while(p >andl[p-1] > temp):#当排好序中的有序数据中的值比待排序记录值大时，则将该值向后一移一位，直至找到适合待排序记录大小的索引入，将temp值放入

l[p] = l[p-1]

p -=1

l[p] = temp

returnl

print(insertSort([1,3,5,2,4]))

算法分析：

空间复杂度：O（1）；最好时间复杂度：O（n），最坏时间复杂度：O（n^2）；最好情况下，序列为排序好的序列，只需比较n-1次即可，需移动次；最坏情况下，需要比较O（n^2）次，移动次数O（n^2）。

2二分插入排序

二分插入排序是在直接插入排序的基础上提出来的一种排序算法，其基本思想也较为类似，唯一不同的点在于在进行待排序序列值与已经排好序序列中各值的比较时，采用二分法的方式进行比较，这样可以减少比较次数，但移动次数不会减少。

Python代码实现

#_*_ coding: utf-8 _*_

#二分插入排序（升序排列）

"""

@:param:l:一个待排序的序列

@:return:l：一个排好序的序列

author: xc

time：2018-07-20

"""

defbinInsertSort(l):

a =len(l)

iflis None:

return

ifa

returnl

foriinrange(a):

p = i

start =

end = i

temp = l[i]

while(end - start >):#通过二分法查找出待排序记录适合插入的位置

mid =int((end - start)/2) + start

if(l[mid] > temp):#根据中值的大小来改变二分查找时的首尾两端位置，直至找到位置

end = mid

else:

start = mid +1

while(p > end):#找到插入位置后，只需将位置前面直到排好序序列末尾的值一一向后移即可，将位置腾出给到待排序记录

l[p] = l[p-1]

p -=1

l[p] = temp

returnl

print(binInsertSort([1,3,5,2,4]))

3希尔排序

希尔排序稍稍有别于直接插入排序，因为它会将需要排列的序列进行分组，且每次会根据增量的不同，分组的组数由少变多（即增量越来越小，组内距离越来越小）。每次对分组内的数据进行一次直接插入排序，这样就可以将数组进行初步排序，而随着分组的不断细化，则可以实现整个序列的排序工作。

这样子进行排序的好处是，元素X从初始化位置移动到最终位置所需要的移动次数要少。

辅助理解过程图：

图2：希尔排序过程图

Python代码实现：

#_*_ coding: utf-8 _*_

#希尔排序（升序排列）

"""

@:param:l:一个待排序的序列

@:return:l：一个排好序的序列

author: xc

time：2018-07-20

"""

defshellSort(l):

a =len(l)

iflis None:

return

ifa

returnl

gap =int(a/2)

while(gap >):#等于0时则表示对所有数据排序完成

foriinrange(a):

temp = l[i]

p = i

while(p >= gapandl[p-gap] > temp):#对每个分组内的数据进行直接插入排序

l[p] = l[p - gap]

p -= gap

l[p] = temp

gap =int(gap/2)#减小gap值，使分组变多，直至将所有数据分为一组

returnl

print(shellSort([1,3,5,2,4]))

特征分析：

容易实现，且是一种基于插入排序的算法，提升了算法效率。其时间复杂度与增量序列的选取有关，时间复杂度下界为：n*log2n。在中等大小规模数据中表现较好，在规模特别大的数据集中表现略有欠缺。

可以首先使用希尔排序，再改用更高级的排序算法。