[数据结构与算法]排序算法（python实现）

排序算法(python实现)

初阶三人组

根据算法的时间复杂度将O(n2)和设计难度将冒泡排序、选择排序、插入排序划为初阶算法。

冒泡排序 bubble——sort()

将一个列表（n个对象）从左到右按下标递增的方式进行两两比较，如果左边的数值大于右边的数值则将左右值交换，直到最后一个。这样就筛选出了列表最大值且该值的下标在末尾，这个尾标就将数据划分为有序区和无序区，然后再进行n-1轮筛选更新尾标直到尾标等于1。
代码实现：

def bubble_sort(li):
    for i in range(len(li)-1):  #(交换次数，无序区第一个数不用排)
        exchange = False   #由于li[j]是相邻两两交换，所以当标志位不发生改变时则无序区本身就是有序的不用再冒泡。
        for j in range(len(li)-1-i):  #(争对具体的交换数,j为无序区有序区划分下标)
            if li[j] > li[j+1]:
                li[j],li[j+1] = li[j+1], li[j]
                exchange = True
        if not exchange:
            return li

选择排序 select_sort()

将列表（n个对象）的第一个值计为初始最小值，以此值的位置将列表分为左侧（有序区）和右侧（无序区）。通过坐标交换寻找无序区的最小值与有序区的初始最小值做比较，通过判断则交换值，循环实现排序。
代码块：

def select_sort(li):
    for i in range(len(li)-1): #最小值由左到右依次定义
        mid_lof = i  
        for j in range(i+1, len(li)):
            if li[mid_lof] > li[j]:
                mid_lof = j
        li[i], li[mid_lof] = li[mid_lof], li[i]
    return li

插值排序 index_sort()

思路：打扑克摸牌时的排序方法，从第一张牌开始摸将其作为最小的牌，然后摸第二张，判断与第一张的大小。如果大则不动，小的话就将第一张牌右移动一个单位直至让左边的牌小于等于现在的牌为止。最后摸完最后一张牌，排序结束。
代码实现：

def index_sort(li):
    for i in range(1, len(li)-1): #你摸到的牌的下标
            tmp = li[i]    #摸到的牌大小
            j = i-1            #手里面的牌
            while li[j] > tmp and j>= 0: #摸到的牌与手里面的牌进行比较，当手里面的牌比摸到的大时则循环
                li[j+1] = li[j]       #手里的牌进一位
                j -= 1               #跟下一张手里面的牌继续比较
            li[j+1] = tmp          #找到摸牌比手中牌大的位置且为 j+1，并将该位置的值更新
     return  li

进阶三人组

时间复杂度为nlog(n)的排序算法，为快速排序算法，堆排序算法，归并排序。

快速排序算法 quick_sort()

思路：先做规则函数: 将第一个元素作为初始值，将其与后面的元素进行比较交换下标，使得该元素的左边总是小于该元素的值，而右边的元素总大于该元素。这样就对第一个元素进行了定位。 后面定义调用函数，实现递归，使其以log(n)方式复杂度递减。
代码实现：

def partition(li, left, right):
    tmp = li[left]   #初始值取出保存，左边第一个变为空位
    while left < right :  #当left不与right碰头时继续进行
        while left < right and li[right] >= tmp :  #右边的right位与tmp比较，若小于则填入左边位置
            right -= 1        #右边空出，边界见一
        print(li)
        li[left] = li[right]   #值填入
        while left < right and li[left] <= tmp  :
            left += 1
        li[right] = li[left]

    li[left] = tmp #最后的空位left为tmp的位置，填入tmp
    return left  #返回tmp位置，将列表划为两个部分，并用于递归传值

def quick_sort(li,left,right):
    if left < right:  #判断列表长度大于2
        mid = partition(li, left, right) # 过第一遍，进行分区
        quick_sort(li, left,oid-1) #左边递归
        quick_sort(li, oid+1, right)# 右边递归
    return li

堆排序算法 heap_sort()

利用二叉树思想，将列表看成完全二叉树。列表元素下标(注意从0开始算)具有以下关系：父节点(i) —>子节点(2i+1或者2*i+2)。于是我们就可以利用这种关系建立堆排序，具体原理思路是建大堆(要求任意父节点大于子节点数，保证堆顶最大。这里需要先建立运算规则函数)，然后将堆顶数(也就是最大数)撸下放到列表的最后一位（原来的数进行保存取出）留出堆顶，在重复这样的操作，直至完成。大
代码实现：

def sift(li, low, high):
    i = low    #获得堆顶
    j = 2*i+1   #左边孩子
    tmp = li[i]  #取数保存
    while j <= high:  #保证孩子存在
        if j+1 < high and li[j] <li[j+1]:  #保证右孩子存在且右边大于左边时则j进位
            j += 1
        if tmp < li[j]:   #确定大堆的位置并交换,注意tmp不能用li[i]代替，否则第一个数无法写回
            li[i] = li[j]
            i = j
            j = 2*j+1
        else:
            li[i] = tmp #当tmp本来就大时则归还tmp
            break
    else:
        li[i] = tmp  #此处是为了heap_sort调用时将列表从末尾进行堆化
    print(li)
    return li

def heap_soft(li, low, high):
    n = high
    for i in range(n//2-1, -1, -1):
        sift(li, i , high)
        print(li,"duihua")    #堆化，即要求任意父节点大于子节点
    for j in range(n, -1, -1):  #j 分序
        li[0], li[j] = li[j], li[0]
        sift(li, 0 ,j -1) #j-1 之后的有序化数值不能参与运算
    return li

归并排序算法 merge_sort()

设置归并规则。假设列表被某一元素分为前后有序的序列，比较该元素前区的第一值与后区的第一值大小，依次进位、小值写入新列表直到筛选至该元素前的最后一值或后区列表最后一值结束。
后利用递归思想，将前去和后区再进行划分至分区列表数为2或11，最后得到一个假设列表，在调用规则完成归并排序。
代码块

def merge(li, low, mid, high):
    tmp1 = low
    tmp2 = mid+1
    c = mid
    list = []
    while tmp1 <= c and tmp2 <= high:
        if li[tmp2] <= li[tmp1]:
            list.append(li[tmp2])
            tmp2 +=1
        else:
            list.append(li[tmp1])
            tmp1 += 1
    while tmp2 <= high :
        list.append(li[tmp2])
        tmp2 +=1
    while tmp1 <= c :
        list.append(li[tmp1])
        tmp1 += 1
    li[low:high+1] = list


def merge_sort(li, low ,high):
    if low < high :
        mid = (low + high) // 2
        merge_sort(li,low, mid)  #前区递归
        merge_sort(li, mid+1, high) #后区递归
        merge(li, low, mid, high) #排序
    return li