本文主要是介绍数据结构与算法(python):插入排序和谢尔排序算法及分析,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
参考自 MOOC数据结构与算法Python版
目录
- 一、插入排序 Insertion Sort
- 1.1 算法思路
- 1.2 代码及算法分析
- 二、谢尔排序Shell Sort
- 2.1 算法思路
- 2.2 代码及算法分析
一、插入排序 Insertion Sort
1.1 算法思路
插入排序维持一个已排好序的子列表, 其位置始终在列表的前部, 然后逐步扩大这个子列表直到全表。
【步骤】
- 第1趟, 子列表仅包含第1个数据项, 将第2个数据项作为“新项”插入到子列表的合适位置中, 这样已排序的子列表就包含了2个数据项
- 第2趟, 再继续将第3个数据项跟前2个数据项比对, 并移动比自身大的数据项, 空出位置来, 以便加入到子列表中
- 经过n-1趟比对和插入, 子列表扩展到全表, 排序完成
1.2 代码及算法分析
【代码】
def insertionSort(alist):for index in range(1, len(alist)):currentvalue = alist[index] #取新项position = indexwhile position > 0 and alist[position-1] > currentvalue:alist[position] = alist[position-1]#比前一项小,往前移position = position - 1 #移动alist[position] = currentvalue
- 插入排序的比对主要用来寻找“新项”的插入位置,最差情况是每趟都与子列表中所有项进行比对, 总比对次数与冒泡排序相同,其时间复杂度仍然是 O ( n 2 ) O(n^2) O(n2)
- 最好情况, 列表已经排好序的时候, 每趟仅需1次比对, 总次数是 O ( n ) O(n) O(n),即, 列表越接近有序, 插入排序的比对次数就越少
- 由于移动操作仅包含1次赋值,是交换操作的1/3,所以插入排序性能会较好一些。
二、谢尔排序Shell Sort
2.1 算法思路
谢尔排序,又称希尔排序,以插入排序作为基础, 对无序表进行“间隔”划分子列表, 每个子列表都执行插入排序,随着子列表的数量越来越少, 无序表的整体越来越接近有序, 从而减少整体排序的比对次数
【步骤】
- 分组。将数据切分,通常是总长度的一半,奇偶数均可,将相同位置的数据项划分为一组,如第一部分的第二项和第二部分的第二项;
- 组内排序。插入排序,将其按大小交换位置;
- 再次分组。将数据再次切分,每个部分为上次的一半,再将其根据相对位置分好组,这是组内的成员数量为之前的一倍;
- 组内排序again;
- 直到最后所有的数据为一组,再进行插入排序
2.2 代码及算法分析
【代码】
def shellSort(alist):sublistcount = len(alist)//2while sublistcount >0:for startPos in range(sublistcount):gapInsertSort(alist, startPos, sublistcount)sublistcount = sublistcount // 2def gapInsertSort(alist, start, gap):for i in range(start+gap, len(alist), gap):currentvalue = alist[i]position = iwhile position>= gap and alist[position - gap] > currentvalue:alist[position] = alist[position - gap]position = position - gapalist[position] = currentvalue
- 由于每趟都使得列表更加接近有序, 这过程会减少很多原先需要的“无效”比对
- 对谢尔排序的详尽分析比较复杂,大致说是介于 O ( n ) O(n) O(n)和 O ( n 2 ) O(n^2) O(n2)之间
- 谢尔排序的时间复杂度约为 O ( n 3 2 ) O({{n}^{\frac{3}{2}}}) O(n23)
这篇关于数据结构与算法(python):插入排序和谢尔排序算法及分析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!