python实现插入排序

插入排序

插入排序是一种简单直观的排序方法，其基本思想在于每次将一个待排序的记录，按照其关键字大小插入到前面已经排好序的子序列中，直到全部记录插入完成。
直接插入排序
假设在排序过程中，待排序表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