Python之希尔排序

╰+哭是因爲堅強的太久メ 2022-02-20 08:49 181阅读 0赞

**希尔排序：**  
也称缩小增量排序，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。

**希尔排序的基本思想：**  
1、先将整个待排序列分割成若干个子序列(由相隔某个“增量”的元素组成)分别进行直接插入排序；  
2、然后依次缩减增量再进行排序；  
3、待整个序列中的元素基本有序(增量足够小)时，再对全体元素进行一次直接插入排序。  
4、因直接插入排序在元素基本有序的情况下（接近最好情况）效率很高，所以希尔排序在时间效率上比插入排序有较大提高。

希尔排序的时间复杂度大致介于O(n)和O(n²)之间。如果使用某些间隔时，它的时间复杂度为O(n²)。通过改变间隔的大小，比如以2k-1(1,3,5,7,15,31等等)为间隔，希尔排序的时间复杂度可以达到O(n\*\*1.5)。

**示例：**

# 希尔排序
    def shellSort(alist):
    	sublistcount = len(alist) // 2 					#初始子序列数，每2个元素为一个子序列
    	while sublistcount > 0:							#增量>0则循环
    		for startposition in range(sublistcount):	#将所有子序列进行循环插入排序
    			# 将子序列以子序列数作为增量进行插入排序
    			gapInsertionSort(alist, startposition, sublistcount)	
    		print("在间隔为", sublistcount, "的增量之后，列表为：", alist)
    		sublistcount = sublistcount // 2 			#缩减增量及子序列数继续循环
    
    # 增量插入排序，gap为增量
    def gapInsertionSort(alist, start, gap):
    	m = start + gap     							#循环开始位置
    	n = len(alist)									#循环结束后一个位置
    	for i in range(m, n, gap):						
    		currentvalue = alist[i]						#将当前值赋值给待插入元素
    		position = i 								#将当前索引赋值给position
    		# 当待插入元素的位置>=增量且子序列中前一个元素比待插入元素大，则循环
    		while position >= gap and alist[position - gap] > currentvalue:
    			alist[position] = alist[position - gap] #将子序列中前一个元素移到待插入元素位置
    			position -= gap 						#将待插入元素位置前移增量值个位置
    		alist[position] = currentvalue 				#将待插入元素赋值到正确位置
    
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    shellSort(alist)
    print(alist)

**结果为：**

在间隔为 4 的增量之后，列表为： [20, 26, 44, 17, 54, 31, 93, 55, 77]
    在间隔为 2 的增量之后，列表为： [20, 17, 44, 26, 54, 31, 77, 55, 93]
    在间隔为 1 的增量之后，列表为： [17, 20, 26, 31, 44, 54, 55, 77, 93]
    [17, 20, 26, 31, 44, 54, 55, 77, 93]