第一步

#将原始列表中的最大值找出且放置在列表最右侧(将元素两两比较，将数值大的数逐步向后移动)
def sort(alist):
    for i in range(len(alist)-1):
        if alist[i] > alist[i+1]:
            alist[i],alist[i+1] = alist[i+1],alist[i]
    return alist

#判断 循环次数

def sort(alist):
    for j in range(len(alist)-1):
　　　　　#不断把最大的移动到最后
        for i in range(len(alist)-1-j):
            if alist[i]>alist[i+1]:
                alist[i] ,alist[i + 1]=alist[i + 1],alist[i]
    return alist
alist=[1,2,5,3,2,8,6,0]
print(sort(alist))

#将列表中的最大值的下标找到
def sort(alist):
    max_index = 0 #最大值的下标
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    print(max_index)

#将列表中的最大值一次找出，放置在列表最右侧
def sort(alist):
    max_index = 0 #最大值的下标
    for i in range(1,len(alist)):
        if alist[max_index] < alist[i]:
            max_index = i
    alist[max_index],alist[len(alist)-1] = alist[len(alist)-1],alist[max_index]
    
    return alist

def sort(alist):
　　#依次缩小列表范围
    for j in range(len(alist),1,-1):
        max_index = 0 #最大值的下标
        for i in range(1,j):  #len(alist)  == > j
            if alist[max_index] < alist[i]:
                max_index = i
        alist[max_index],alist[j-1] = alist[j-1],alist[max_index]
    
    return alist


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

#执行第一次插入操作
def sort(alist):
    i = 1
    # alist[i-1]:第一次插入时的有序列表
    # alist[i]:乱序列表中的第一个列表元素
    if alist[i] < alist[i-1]:
        alist[i],alist[i-1] = alist[i-1],alist[i]  

def sort(alist):
    i = 2
    # alist[i-1]:第一次插入时的有序列表
    # alist[i]:乱序列表中的第一个列表元素
    if alist[i] < alist[i-1]:
        alist[i],alist[i-1] = alist[i-1],alist[i]      

def sort(alist):
    i = 3
    # alist[i-1]:第一次插入时的有序列表
    # alist[i]:乱序列表中的第一个列表元素
    while i > 0:
        if alist[i] < alist[i-1]:
            alist[i],alist[i-1] = alist[i-1],alist[i] 
            i -= 1
        else:
            break

def sort(alist):
    for i in range(1,len(alist)):
        # alist[i-1]:第一次插入时的有序列表
        # alist[i]:乱序列表中的第一个列表元素
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i] 
                i -= 1
            else:
                break
    return alist

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

#增量为1的希尔排序（插入排序的核心）
def sort(alist):
    #增量
    gap = len(alist) // 2
    
    for i in range(1,len(alist)):
        # alist[i-1]:第一次插入时的有序列表
        # alist[i]:乱序列表中的第一个列表元素
        while i > 0:
            if alist[i] < alist[i-1]:
                alist[i],alist[i-1] = alist[i-1],alist[i] 
                i -= 1
            else:
                break
    return alist

#增量为gap的希尔排序
def sort(alist):
    #增量
    gap = len(alist) // 2
    for i in range(gap,len(alist)):
        # alist[i-1]:第一次插入时的有序列表
        # alist[i]:乱序列表中的第一个列表元素
        while i > 0:
            if alist[i] < alist[i-gap]:
                alist[i],alist[i-gap] = alist[i-gap],alist[i] 
                i -= gap
            else:
                break
    return alist

#继续缩小增量（gap）
def sort(alist):
    #增量
    gap = len(alist) // 2
    
    while gap >= 1 :
        for i in range(gap,len(alist)):
            # alist[i-1]:第一次插入时的有序列表
            # alist[i]:乱序列表中的第一个列表元素
            while i > 0:
                
                if alist[i] < alist[i-gap] and i-gap>0:
                    alist[i],alist[i-gap] = alist[i-gap],alist[i] 
                    i -= gap
                else:
                    break
        gap //= 2
    return alist

def sort(alist,start,end):
    low = start
    high = end
  
    #结束递归的条件
    if low > high:
        return
    mid = alist[low]
  
    
    while low < high:
        while low < high:
            if alist[high] > mid:
                high -= 1
            else:
                alist[low] = alist[high]
                break
        while low < high:
            if alist[low] < mid:
                low += 1
            else:
                alist[high] = alist[low]
                break      
    alist[low] = mid
    
    sort(alist,start,high-1)
    sort(alist,low+1,end) #将基准右侧的子列表进行递归操作

    
    return alist

alist = [2,4,5,1,3]
print(sort(alist,0,len(alist)-1))