[数据结构与算法]python实现四种简单的排序

#冒泡排序，冒泡排序实质上是指大的数据在后面，小的数据在前面
def Bubble_sort(num_list):
    for i in range(len(num_list)).__reversed__():#此行是为了可以使整个程序执行该数组长度的次数，而这里的倒序是为了得到比较到最后一位的下标
        # 这个循环是为了让相邻两个数据进行比较，从num[0]比较到num[i-1],因为下面我比较的是当前的下标对应的数据与它下一位的数据，所以只比较到倒数第二位就可以了
        # 所以第一次遍历比较时的i值为len（num_list)-1
        for j in range(i):
            if num_list[j] > num_list[j+1]: # 如果当前数组对应的数据比下一位大，则交换其位置
                num_list[j],num_list[j+1]=num_list[j+1],num_list[j] #交换两个数组的位置
    return num_list

#选择排序,选择排序的实质就是指将比较小的数字放在前面，需要用到一个标识位
def Select_sort(num_list):
    for i in range(len(num_list)-1): #老规矩，第一个遍历控制循环次数，第二个遍历控制比较的数组下标，将第一个数据当作比较位，则只比较长度-1次即可
        # 先标记一个标识位，让他等于最开始的数组下标，如果有其他的数据比他小，那么交换他们的数值，这样比较到最后一位的时候，该标识位对应的下标就是最小的
        minindex = i
        #选择排序是找最小的值，让他从前到后依次有序，因此让i的下标值从第i+1位开始比较到最后一位即可
        for j in range(i+1,len(num_list)):
            #如果找到比min下标对应的数据还小的，交换他们的数据
            if num_list[minindex] > num_list[j]:
                num_list[minindex],num_list[j]=num_list[j],num_list[minindex]
    return num_list

#插入排序，插入排序是指通过比较当前位置与此位置之前的数据的大小，若比之前数据小，则当前位置等于前一个位置的数据，直到找到比前一个大的位置，则当前下标即是目标下标
def Insert_sort(num_list):
    #假定第一个是有序的，从第二个位置开始遍历
    for i in range(1,len(num_list)):
        #j是当前下标
        j = i
        #用target储存当前位置的数据，也是待插入的数据
        target = num_list[i]
        #当下标大于0，并且target小于前一位数据时才执行whil循环里的内容，
        while(j>0 and target < num_list[j-1]):
        #当target小于前一位的时候，对应的当前数组的位置应当等于前一位
            num_list[j] = num_list[j-1]
            j -= 1            #这里的自减是因为当前位置已经比较完毕，应当比较之前一位的数据
        # 当退出while循环时的当前位置就是应当插入数据的位置
        num_list[j]=target
    return num_list

#快速排序1
def swap(arr, i, j):
    arr[i], arr[j] = arr[j], arr[i]

def partition(arr, left, right):
    pivot = left
    index = pivot+1
    i = index
    while  i <= right:
        if arr[i] < arr[pivot]:
            swap(arr, i, index)
            index+=1
        i+=1
    swap(arr,pivot,index-1)
    return index-1
def quickSort(arr, left=None, right=None):
    left = 0 if not isinstance(left,(int, float)) else left
    right = len(arr)-1 if not isinstance(right,(int, float)) else right
    if left < right:
        partitionIndex = partition(arr, left, right)
        quickSort(arr, left, partitionIndex-1)
        quickSort(arr, partitionIndex+1, right)
    return arr


#快速排序2
def Quick_sort(num_list,start,end):
    left=start
    right=end
    mid = num_list[start]
    while left < right :
        while left < right and num_list[right] >= mid:
            right -=1
        num_list[left]=num_list[right]
        while left < right and num_list[left] < mid:
            left +=1
        num_list[right]=num_list[left]
    num_list[left]=mid
    quickSort(num_list,start,right-1)
    quickSort(num_list,left+1,end)

if __name__ == "__main__":
    a = [1, 2, 5, 7, 8, 9, 4, 5, 28, 42, 5235, 5235,32, 63, 98, 2, 632, 623626, 6, 653]
    #res1=Bubble_sort(a)
    #res2=Select_sort(a)
    #print(res1)
    #print(res2)
    #res3=Insert_sort(a)
    #print(res3)
    res4=Quick_sort(a,0,len(a)-1)
    print(a)
    #res5=quickSort(a)
    #print(res5)