线性排序算法（1）

排序

选择排序（适用于线性排序）

思路，2层遍历

1. 第一步：选择最小的元素，与第一个元素交换。
2. 第二步：从第二个元素到最后一个元素，选择最小元素，与第二元素交换
3. 完成前两步，第1第2元素已经排好序。继续遍历。

算法复杂度 O(n^2)

def SelectionSort(a):
    for i in range(len(a)):
        tmp_min = a[i]
        index = i
        for j in range(i,len(a)):
            if a[j]<tmp_min:
                index = j
                tmp_min = a[j]
        tmp = a[i]
        a[i] = a[index]
        a[index] = tmp
           

插入排序（适用于线性排序）

1. 第一步：第二元素向前遍历，如果第一个元素比自己大，与第一个元素交换位置
2. 第二步：从第三个元素到最后一个元素，向前遍历，如果前一个元素比自己大，就交换位置；
3. 遍历过程中，如果发现前一个元素比自己小，结束遍历。

由于在遍历过程中，当出现前一个元素小于当前元素，提前结束比对，比选择排序算法的比对次数少。

def swap(a,i,j):
    tmp  = a[i]
    a[i] = a[j]
    a[j] = tmp
def InsertionSort(a):
    for i in range(1,len(a)):
        for j in range(i,0,-1):
            if(a[j-1]>a[j]):
                swap(a,j-1,j)
            else:
                break
           

用赋值替换swap，对InsertionSort优化

def InsertionSortCopy(a):
    for i in range(1,len(a)):
        for j in range(i,0,-1):
            tmp = a[j]
            if(a[j-1]>tmp):
                a[j] = a[j-1]
            else:
                a[j] = tmp