【算法作业记录】

插入排序 递归实现

直接插入

#将a[n]插入有序区间a[0,n-1]中 时间复杂度 O（n）
def Insert(a,n):
    i=n
    while(i>0 and a[i-1]>a[i]):
        tmp=a[i]
        a[i]=a[i-1]
        a[i-1]=tmp
        i-=1
    return
#直接插入排序
def Insertsort(a,n):
    for i in range(1,n):#【1，n-1】
        if(a[i-1]>a[i]):
            Insert(a,i)
    return      
#递归法实现直接插入：插入a[n]是建立在a[0,n-1]有序的基础之上
def RecursionInsertsort(a,n):
    if(n<=0):
        return
    RecursionInsertsort(a,n-1)#递归实现【0，n-1】有序
    if(a[n-1]>a[n]):
        Insert(a,n)#再把a[n]插入有序数组a[0,n-1]中
    return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

折半插入

#折半查找
 #在有序区[0,i-1]中二分查找元素a[i]应插入的位置 时间复杂度O（logN）
def BinInsert(a,i):
    low=0
    height=i-1
    insert=a[i]
    while(low<=height):
        mid=(low+height)//2
        if(insert<a[mid]):
            height=mid-1
        else:    
            low=mid+1    
        j=i-1
    #height+1为要插入的位置，将【height+1,i-1】元素往后平移一步，空出a[height+1]的位置   
    while(j>=height+1):
        a[j+1]=a[j]
        j=j-1
    a[height+1]=insert      

#折半插入排序
def BinInsertSort(a,n):
    for i in range(1,n):
        if(a[i-1]>a[i]):
            BinInsert(a,i)
        print(str(i)+":"+str(a))
#递归实现折半插入
def RecursionBinInsertSort(a,n):
    if(n<=0):
        return
    RecursionBinInsertSort(a,n-1)
    if(a[n-1]>a[n]):
        BinInsert(a,n)
    return    

list1 = [1,4,6,3,7,9,2,8,5,0]        
print("排序前："+str(list1))
#Insertsort(list1,len(list1))    
#RecursionInsertsort(list1,len(list1)-1)    
#BinInsertSort(list1,len(list1))
RecursionBinInsertSort(list1,len(list1)-1)
print("排序后："+str(list1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

归并排序的算法改进

还有一个链表自底向上的未实现，参考笔记点我 点我

#107552304105 吕雅轩
#由于本人能力有限 除了网上给的四个优化策略想不出其它的了，以下是实现过程
#策略1: 若两数组直接拼起来就是有序的，就无需merge 即当arr[mid]<=arr[mid+1]
#策略2：小区间使用性能更高的插入排序
#策略3：全程使用1个和待排数组大小一样的临时数组作为辅助空间，避免了每一次merge都要new的浪费
#策略4：自顶向下需要递归调用log(n)的函数栈空间，可用自底向上的思路优化
#策略5：归并算法的空间复杂度是O(n),若想使空间复杂度优化为O（1）,可以采用自底向上的链表法进行排序。
def merge_sort(a):
    #策略3：全局辅助空间
    global al
    al=list(range(len(a)))
    #_mergeSort(a,0,len(a)-1)
    #策略4：迭代法自底向上
    _mergeSortIterate(a)
    return

#插入排序
def _insertSort(a,l,r):
    for i in range(l,r+1):#【1，n-1】
        if(a[i-1]>a[i]):
            j=i
            while(j>0 and a[j-1]>a[j]):
                tmp=a[j]
                a[j]=a[j-1]
                a[j-1]=tmp
                j-=1
       
#用辅助空间把两个有序数组合并
def _merge_two_sorted_array(a,l,mid,r):
    for i in range(l,r+1):#[l,r]
        al[i]=a[i]
    i=l#左半有序数组的起始下标
    j=mid+1#右半有序数组的起始下标  
    #print(str(l)+":"+str(mid)+":"+str(r)+":"+str(a))  
    for k in range(l,r+1):#[l,r]
        if i==mid+1:
            a[k]=al[j]
            j+=1
        elif j>r:
            a[k]=al[i]
            i+=1
        elif al[i]<al[j]:
            a[k]=al[i]
            i+=1
        else:
            assert al[i]>=al[j]
            a[k]=al[j]
            j+=1 
    return
#递归实现归并排序
def _mergeSort(a,l,r):
    if l>=r:
        return
    #策略2：小区间使用性能更高的插入排序
    if (r-l)<=7:
        _insertSort(a,l,r)
        return
    mid=l+(r-l)//2#防止(l+r)溢出
    _mergeSort(a,l,mid)
    _mergeSort(a,mid+1,r)
    #策略1：若有序左区间的最大元素小于有序右区间的最小元素，可直接合并
    if a[mid]<=a[mid+1]:
        return
    _merge_two_sorted_array(a,l,mid,r)
    return

#策略4：迭代法自底向上
def _mergeSortIterate(a):
    n=len(a)
    size=1#每一次分段的长度
    i=0
    while(size<=n):
        i=0
        while(i+size<n):#确保后一段的存在，同时保证不越界
            _merge_two_sorted_array(a,i,i+size-1,min(i+size+size-1,n-1))
            i+=size+size
        size+=size
    return
        
list1 = [10,9,8,7,6,4,5,3,2,1]        
print("排序前："+str(list1))
merge_sort(list1)
#_mergeSortIterate(list1)
print("排序后："+str(list1))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84