八大排序算法的python实现(二)希尔排序

python

代码:

#coding:utf-8

#author:徐卜灵

# 希尔排序的实质就是分组插入排序,该方法又称缩小增量排序,因DL.Shell于1959年提出而得名。

# 希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

# 希尔排序是基于插入排序的以下两点性质而提出改进方法的:

# 插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率

# 但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位

L = [1, 3, 2, 32, 5, 4]

def Shell_sort(L):

step = len(L)/2

while step > 0:

for i in range(step,len(L)): #在索引为step到len(L)上,比较L[i]和L[i-step]的大小

while(i >= step and L[i] < L[i-step]): #这里可以调整step从小到大或者从大到小排列

L[i],L[i-step] = L[i-step],L[i]

i -= step

step /= 2

print L

Shell_sort(L)

#别人的希尔排序代码

#引用网址:http://www.cnblogs.com/qlshine/p/6052223.html

# def shellSort(nums):

# # 设定步长

# step = len(nums)/2

# while step > 0:

# for i in range(step, len(nums)):

# # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置

# while i >= step and nums[i-step] > nums[i]:

# nums[i], nums[i-step] = nums[i-step], nums[i]

# i -= step

# step = step/2

# return nums

#

#

# if __name__ == '__main__':

# nums = [9,3,5,8,2,7,1]

# print shellSort(nums)

这个算法不难理解,但在写程序的时候还是遇到了小小的麻烦。主要体现在它的时间复杂读为O(n ** 1.3 )好奇怪的时间复杂度。

所以,在一次排序中,L[i]和L[i-step]的比较,一直循环到本组的第一个元素。

还需要注意一点是的索引是从step开始的。

时间复杂度最坏情况是O(n ** 2)

空间复杂度O(1)

并不是一个稳定的排序算法。

以上是 八大排序算法的python实现(二)希尔排序 的全部内容, 来源链接: utcz.com/z/387834.html

回到顶部