排序算法-1

1.冒泡排序
2.选择排序
3.插入排序（直接插入）
4.归并排序

##Bubble Sort
#i: 0---->n-1
#j: 0---->n-1-i
#前一个比后一个大就交换
#1, 5, 9, 2, 4
# ----                 ----                 ----                 ----   
#[1, 5, 9, 2, 4]-->[1, 5, 9, 2, 4]-->[1, 5, 2, 9, 4]-->[1, 5, 2, 4, 9]
# ----                 ----                 ----
#[1, 5, 2, 4, 9]-->[1, 2, 5, 4, 9]-->[1, 2, 4, 5, 9]
# ----                 ----
#[1, 2, 4, 5, 9]-->[1, 2, 4, 5, 9]
# ----
#[1, 2, 4, 5, 9]

def bubble_sort(n):
    for i in range(0, len(n)):
        for j in range(0, len(n) - 1 - i):
            if n[j] > n[j+1]:
                n[j], n[j+1] = n[j+1], n[j]
    print(n)

##Selecttion Sort
#选出0--->n-1个里面最小的一个放到[0]  [0]和[min]交换
#选出1--->n-1个里面最小的一个放到[1]
#1, 5, 9, 2, 4
#
#[1, 5, 9, 2, 4]    min = 1
#    -     -            
#[1, 2, 9, 5, 4]    min = 2
#       -     - 
#[1, 2, 4, 5, 9]    min = 4
#
#[1, 2, 4, 5, 9]    min = 5

def selection_sort(n):
    index_min = 0
    for i in range(0, len(n)):
        minimum = n[i]      
        for j in range(i, len(n)):
            if n[j] < minimum:
                index_min = j
                minimum = n[j]
        n[index_min], n[i] = n[i], n[index_min]
    print(n) 

##Insert Sort
##0--->i-1 为排好序的部分
##i--->n-1 为待插入的部分 
#1, 3, 4, 7, 2
#插入 1：[(1), 3, 4, 7, 2]
#插入 3：[(1, 3), 4, 7, 2]     
#插入 2：[(1, 3, 4), 7, 2]
#插入 5：[(1, 3, 4, 7), 2] 2与7比较 交换-->2与4比较 交换     
#插入 4：[(1, 2, 3, 4, 7)] 
def insert_sort(n):
    for i in range(1, len(n)):  
        j = i - 1
        cur = n[i]
        while j>=0 and cur < n[j] :
            n[j], n[j+1] = n[j+1], n[j]
            j -= 1
    print(n)

##Merge Sort
#--------------------------------------
#-----ONE----
#合并两个排好序的list
# i 0---->2  j 3------->6
#  [1, 4, 8]  [2, 3, 5, 9]
#  比较array[i]和array[j],谁大放谁到temp中，相应光标i或者j+1
#  把两个分list剩下的部分 追加到temp
#
def merge(array, left, mid, right):
    len = right - left +1
    temp = [0]*len
    index = 0
    i = left
    j = mid + 1
    while i <= mid and j <= right:
        if array[i] <= array[j]:            
            temp[index] = array[i]
            i += 1
        else:           
            temp[index] = array[j]
            j += 1
        index += 1          
    while i <= mid:
        temp[index] = array[i]
        index += 1
        i += 1
    while j <= right:
        temp[index] = array[j]
        j += 1
        index += 1
    for num in temp:
        array[left] = num
        left += 1

##---TWO---
##分
#将list分为两部分
def merge_sort_recursion(array, left, right):
    
    if left == right:
        return
    
    mid = int((right + left)/2)
    merge_sort_recursion(array, left, mid)
    merge_sort_recursion(array, mid+1, right)
    
    merge(array, left, mid, right)

##---THREE---
def merge_sort(n):
    temp = [0] * len(n)
    merge_sort_recursion(n, 0, int(len(n) - 1)) 
    print(n)
##---------------------------------------------

bubble_sort([5, 3, 1, 9, 4, 20, 21, 10, 2, 2, 7])
selection_sort([5, 3, 1, 9, 4, 20, 21, 10, 2, 2, 7])
insert_sort([5, 3, 1, 9, 4, 20, 21, 10, 2, 2, 7])
merge_sort([5, 3, 1, 9, 4, 20, 21, 10, 2, 2, 7])