#冒泡排序完整代码
#上述代码操作需要作用n-1才可以将整个序列变成有序的
def sort(alist):
    length = len(alist)
    
    for j in range(0,length-1): #有几个数字就循环几次,确保每一个数字都移动到对应的位置
        #让两两元素进行比较（n-1）
        for i in range(0,length-1-j):#每相邻两个数字都做比较,大的就放到最后,依次下去,
　　　　　　　　　　　　　　　　　　　　　　直到对应的位置,这里减j是要省去每次循环都对比7个元素
　　　　　　　　　　　　　　　　　　　　　　(循环一次就有一个数字已经找到对应的位置,接下来再循环时相邻数字作比较就少一个就好了),
　　　　　　　　　　　　　　　　　　　　　　第一次对比7个数字,第二次减去一个上依次循环已经定位好的第7个数字,就只对6个数字最相邻数字比较
            if alist[i] > alist[i+1]:#第一个元素大于第二个元素
                #两个元素交换位置
                alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist

alist = [3,8,5,2,0,7,6]
print(sort(alist))

#选择排序完整代码
def sort(alist):
    for j in range(0,len(alist)-1):
        max_index = 0 #表示的是最大值的下标，一开始我们假设列表中的第0个元素为最大值
        for i in range(len(alist)-1-j):#控制比较的次数
            if alist[max_index] < alist[i+1]:
                max_index = i+1 
        #将最大值和最后一个元素交换位置，就可以将最大值放置到序列的最后位置
        alist[max_index],alist[len(alist)-1-j] = alist[len(alist)-1-j],alist[max_index]

    return alist
    
    
alist = [3,8,5,2,0,7,6]
print(sort(alist))

#插入排序完整代码
def sort(alist):
    #i的取值范围是1-（n-1）
    for i in range(1,len(alist)):#假设左起第一个数字已经是排序好了的,然后就要拿左起第二个数字和这个数字作比较,
　　　　　　　　　　　　　　　　　　　　比第一个大,位置就不动,如果比第一个数字小就要放到第一个数字的左边,然后继续循环
　　　　　　　　　　　　　　　　　　　　(注意这里的range是顾头不顾尾,会比len(alist)少1)
    #i = 2 #有序部分有两个元素
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i]#[6,5,8,    2,6,10,1]
                i -= 1 　　　　　　#i是不可以为负数,减一之后就是刚才的数字向左移了一位,这里你继续和他左边的数字作对比,
　　　　　　　　　　　　　　          对比大了就不动了,小了就继续移动有可能会直到移动到最左边.
            else:
                break
    return alist
alist = [3,8,5,2,0,7,6]
print(sort(alist))

#加入递归后完整的快速排序代码
def sort(alist,left,right):
    #low&hight表示的序列的起始位置的下标
    low = left
    high = right 
    
    #结束递归的条件
    #这里有点难理解,只要记住到了极点出现low小于high就是递归结束的时候,不加他就会无限循环
    if low > high:
        return
    
    mid = alist[low] #基数
    
    while low < high:
        #将原始序列中比基数小的值放置在基数的左侧，比基数大的值放置在基数的右侧
        #注意：一开始的时候先将high向左偏移
        #向左偏移
        while low < high:
            if alist[high] < mid: #high小于基数
                alist[low] = alist[high]
                break
            else:#基数如果小于了high，将high向左偏移
                high -= 1 #high想左偏移了以为
        #low向右偏移
        while low <high:
            if alist[low] < mid:#如果low小于mid则让low想右偏移
                low += 1#让low向右偏移一位
            else:
                alist[high] = alist[low]
                break
    if low == high:#low和high重复，将基数赋值到low或者high的位置,
        alist[low] = mid #alist[high] = mid,每循环一次(将mid值左半部分和右半部分已经区分开了,low索引左边的比mid小,low索引右边的比mid大,注意此时low和high相等,这时候就要把low索引对应的值写成mid最早的值,即是中间值)
    
    #指定操作作用到基数左侧的子序列中
    sort(alist,left,low-1)
    #指定操作作用到基数右侧的子序列中
    sort(alist,high+1,right)
    return alist


alist = [66,13,51,76,81,26,57,69,23]
print(sort(alist,0,len(alist)-1))

#希尔排序:插入排序是一种特殊的希尔排序
def sort(alist):
    gap = len(alist) // 2
    while gap >= 1:
        #将增量设置成gap
        for i in range(gap,len(alist)):
            while i > 0 :
                if alist[i] < alist[i-gap]:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i]
                    i -= gap
                else:
                    break
        gap //= 2
    return alist

alist = [4,3,6,1,9,2]
print(sort(alist))

def merge_sort(alist):
    n = len(alist)
    #结束递归的条件
    if n <= 1:
        return alist
    #中间索引
    mid = n//2

    left_li = merge_sort(alist[:mid])
    right_li = merge_sort(alist[mid:])

    #指向左右表中第一个元素的指针
    left_pointer,right_pointer = 0,0
    #合并数据对应的列表：该表中存储的为排序后的数据
    result = []
    while left_pointer < len(left_li) and right_pointer < len(right_li):
        #比较最小集合中的元素，将最小元素添加到result列表中
        if left_li[left_pointer] < right_li[right_pointer]:
            result.append(left_li[left_pointer])
            left_pointer += 1
        else:
            result.append(right_li[right_pointer])
            right_pointer += 1
    #当左右表的某一个表的指针偏移到末尾的时候，比较大小结束，将另一张表中的数据（有序）添加到result中
    result += left_li[left_pointer:]
    result += right_li[right_pointer:]

    return result

alist = [3,8,5,7,6]
print(merge_sort(alist))