欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

相关标签: python 数据结构