算法----排序问题（python代码）

程序来源于：B站

课程：【Python】这可能是你见过的最简洁最没有废话的Python教程

网址：https://www.bilibili.com/video/av5236569/?p=15

1.插入排序

#插入排序，取数组中的某一个数，比较当前数与数组中的数值，如果找到了比他小的数，插入，循环至不可再循环

def insert_sort(origin_list):

        sorted_list=[]

        for i in range(0,len(origin_list)):

            if len(sorted_list)==0:

                sorted_list.append(origin_list[i])

                continue

                for j in range(len(sorted_list)-1,-1,-1):

                    if sorted_list[j]<=origin_list[i]:

                        sorted_list.insert(j+1,origin_list[i])

                        break

                    if j==0:

                        sorted_list.insert(0,origin_list[i])

            origin_list[:]=sorted_list[:]

origin_list=[5,3,1,7,9,8]

insert_sort(origin_list)

print(origin_list)

2.冒泡排序

#冒泡排序，将相邻两个数排序，不断迭代得到结果

def bubble_sort(origin_list):

    for iin range(len(origin_list),0,-1):

        for jin range(0,i-1):

            if origin_list[j]>origin_list[j+1]:

                origin_list[j],origin_list[j+1]=origin_list[j+1],origin_list[j]

origin_list=[5,3,1,7,9,8]

bubble_sort(origin_list)

print(origin_list)

3.快速排序

#快速排序，设定一个中位数，小于该数的数值放在前面，大于该数的数值放在后面，不断迭代，得到结果

def quick_sort(origin_list,start,end):

    if start>=end:

        return

    left=start

    right=end

    flag_index=left

    while left<right:

        while right>left:

            if origin_list[right]< origin_list[flag_index]:

                origin_list[right],origin_list[flag_index]=origin_list[flag_index],origin_list[right]

                flag_index=right

                break

            right-=1

        while right>left:

            if origin_list[left]>origin_list[flag_index]:

                origin_list[left],origin_list[flag_index]=origin_list[flag_index],origin_list[left]

                flag_index=left

                break

            left+=1

    quick_sort(origin_list,start,flag_index)

    quick_sort(origin_list,flag_index+1,end)

origin_list=[5,3,1,7,9,8]

quick_sort(origin_list,0,len(origin_list)-1)

print(origin_list)

4.归并排序

#归并排序，采用的是分治的理念，分而治之，也就是说先把序列均分，组内排序，再与另一组归并，得到结果

def merge_sort(origin_list,start,end):

    if end<=start:

        return

    mid=int((start+end)/2)

    merge_sort(origin_list,start,mid)

    merge_sort(origin_list,mid+1,end)

    left_head=start

    right_head=mid+1

    temp_list=[]

    while left_head<=midand right_head<=end:

        if origin_list[left_head]< origin_list[right_head]:

            temp_list.append(origin_list[left_head])

            left_head+=1

        if origin_list[left_head]>=origin_list[right_head]:

            temp_list.append(origin_list[right_head])

            right_head+=1

    if left_head<=mid:

        temp_list+=origin_list[left_head:mid+1]

    if right_head<=end:

        temp_list+=origin_list[right_head:end+1]

    for i in range(0,len(temp_list)):

        origin_list[i+start]=temp_list[i]

origin_list=[5,3,1,7,9,8]

merge_sort(origin_list,0,len(origin_list)-1)

print(origin_list)