python实现插入排序
程序员文章站
2022-04-09 16:21:14
插入排序插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按照其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。直接插入排序假设在排序过程中,待排序表L[1…n]在某一时刻的状态如下:有序序列L[1…i-1] || 待排序元素L[i] || 无序序列L[i+1…n]需要进行如下操作:1)查询待排序元素L[i]在有序序列L[1…i-1] 的插入位置index.2)将L[index…i-1]的所有元素往后挪一个位置。3)将L[i]插入到位置ind...
插入排序
插入排序是一种简单直观的排序方法,其基本思想在于每次将一个待排序的记录,按照其关键字大小插入到前面已经排好序的子序列中,直到全部记录插入完成。
直接插入排序
假设在排序过程中,待排序表L[1…n]在某一时刻的状态如下:
有序序列L[1…i-1] || 待排序元素L[i] || 无序序列L[i+1…n]
需要进行如下操作:
1)查询待排序元素L[i]在有序序列L[1…i-1] 的插入位置index.
2)将L[index…i-1]的所有元素往后挪一个位置。
3)将L[i]插入到位置index处。
def DirectInsert(A):
le=len(A) #获取列表的长度
for i in range(1,le):#从列表的第二个元素开始遍历,依次插入到有序序列
if A[i]<A[i-1]:#当前元素小于列表的最后一个元素代表需要插入,否则不需要移动
tmp=A[i]#临时记录一下当前元素
j=i-1#从i-1的位置开始比较
while(tmp<A[j]):#获取应该插入的位置
A[j+1]=A[j]#向后挪位
j -= 1 #比较下一个元素
A[j+1]=tmp
print(A)
A=[1,234,456,45,23,4,6,345,2354,234,345,2344,536,345]
DirectInsert(A)#[1, 4, 6, 23, 45, 234, 234, 345, 345, 345, 456, 536, 2344, 2354]
上面是数据结构中讲解的直接插入排序的一般用法,python熟悉的话一般这样处理:
def Insertsort(A):
for i in range(1, len(A)):
# 从第二个元素开始,每次取出一个元素,插入前面的序列使其有序
for j in range(i, 0, -1):
if A[j] < A[j - 1]:
A[j], A[j - 1] = A[j - 1], A[j]
print(A)
tes=[1,234,456,45,23,4,6,345,2354,234,345,2344,536,345]
Insertsort(tes)#[1, 4, 6, 23, 45, 234, 234, 345, 345, 345, 456, 536, 2344, 2354]
折半插入排序
直接插入排序在每一趟的插入过程中,都进行了两项工作:
1)从前面有序子表中查找出待插入元素应该被插入的位置
2)给插入位置腾出空间,然后将待插入元素放入指定位置
第一步的比较次数为O(n),因为是子表是有序表,可以使用二分法查找,比较次数将是O(logn)(底数为2)
#二分法查找元素应该插入的位置
def BinarySearch(array,ele):
low = 0
height = len(array)-1
while low <= height:
mid = (low+height)//2
#print("low:", low, "height:", height,"mid:",mid)
if array[mid] < ele:#查找右半字表
low = mid + 1
elif array[mid] > ele:#查找左半字表
height = mid - 1
else:#和表中元素相等则返回该位置索引
return mid
return (low+height)//2+1 #待查找元素和表中任何一个元素都不相等,则返回应插入的位置索引
def BinaryInsert(A):
le=len(A)
for i in range(1,le): #从第二个元素开始依次向后遍历
tmp=A[i] #临时记录该元素
inde=BinarySearch(A[:i],tmp)#应插入的位置
for j in range(i-1,inde-1,-1):#元素依次往后挪一位
A[j+1]=A[j]
A[inde]=tmp#插入元素
#print(i, inde, tmp, A)
print(A)
A=[278,3,450,5,34,56,78,90,45,456,6789,666]
BinaryInsert(A)#[3, 5, 34, 45, 56, 78, 90, 278, 450, 456, 666, 6789]
希尔排序
基本思想:先将待排序表分割成若干形如L[i,i+d,i+2d…i+kd]的特殊子表,分别进行直接插入排序,当整个表已呈现基本有序(d=1)时,再对全体记录进行一次直接插入排序。
def Shellsort(A):
le = len(A)
d = le // 2# 初始步长
while d > 0:#步长为1则排序完成
# 按步长进行插入排序
for i in range(d, le):
j = i
# 对每个子表进行插入排序
while j >= d and A[j - d] > A[j]:
A[j - d], A[j] = A[j], A[j - d]
j -= d
# print(d,A)
d = d // 2# 新的步长
ll=[2,4,6,8,10,12,14,16,1,3,5,7,9,11,13,15]
Shellsort(ll)
print(ll)#[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
本文地址:https://blog.csdn.net/liulanba/article/details/113945948