算法学习笔记（1）

排序问题

直接开门见山，过多的废话不多说，当我们拿到一堆扑克牌的时候，如何将它从小到大依次排好，这就是我们要解决的问题。我们有两种方法，下文我们挨个阐述。

插入算法

第一种算法，插入算法，直接上图解释，简单明了。

在图a中，我们拿到一个乱序数组，所谓的插入算法，就是从数组的第二个数开始，将数挨个与左边的数进行比较，如果比左边的数小，就将其与左边的数进行交换位置。所以在此数组中，我们先将第二个数也就是（3）与其左边的数（2）作比较，发现3比2大，所以不进行换位。再看第三个数（1），比左边的数（3）小，所以将3与1的位置交换，将大的放在右边，然后再将换位后的1（此时在第二个位置）与其左边的数（2）作比较，发现比2小，再进行一次换位，这样我们就得到了图b。以此类推进行第四个数（5）的排序，发现它大于左边的数（3），所以不进行换位。再往下第五个数（4），与其左边的数（5）进行比较，小于5，所以进行换位操作，换位后再与其左边的数（3）进行比较，发现比3大，所以不进行换位操作。于是就得到了图c。再将第六个数（6）与其左边的数（5）进行比较，发现6大于5，所以不进行换位操作，于是得到图d。至此，图中的数组排序完成。

代码部分

def insertion_sort(Arrary):#①
    for i in range(1,len(Arrary)):#②
        key = Arrary[i]#③
        j = i-1#④
        while j>=0 and Arrary[j]>key:#⑤
            Arrary[j+1] = Arrary[j]#⑥
            j -= 1#⑦
            Arrary[j+1] = key#⑧
    return Arrary#⑨

在第①行中我们为这个排序方法定义一个函数，并将需要排序的数组直接传入该函数中。第②行就是将数组中的从第二个元素开始挨个拿出，并在第③行中将其储存到key中，在第④行中我们拿到当前元素左边的元素的下标值也就是j，在第⑤行中开始将我们所选的元素挨个与左边的数进行大小比较，直到到数组的最左端，如果左边的数大于右边的数的话，我们就进行⑥~⑧行的操作，将大的数放在右边，同时将j-1拿到换位后的左边元素的下标值，再将key中保存的元素也就是较小的数放在左边。最后在第⑨行将排列好的数组返回。

Input：Array1=[2,5,3,1,4,8,6,7,9,0]
Output: Array1=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

分治法

接下来我们来学习下一个排序算法，分治法，直接上图。

如图，将一个数组进行二分法到数组中只有一个元素，再左右进行大小判断排序逐渐合并回去，最后得到排好序的数组。核心思想是递归，接下来我们直接看代码实现。

代码部分

def merge(Array):
    X = Array[0:int(len(Array)/2)]
    Y = Array[int(len(Array)/2):len(Array)]
    i = 0
    j = 0
    for x in range(0,len(Array)):
        if i == int(len(X)):
            Array[j+i:] = Y[j:]
            break
        elif j == int(len(Y)):
            Array[j+i:] = X[i:]
            break
        if X[i] > Y[j]:
            Array[x] = Y[j]
            j+=1
        else:
            Array[x] = X[i]
            i+=1
    return Array

def merge_sort(Array):
    if len(Array) >= 2:
        Array[0:int(len(Array)/2)] = merge_sort(Array[0:int(len(Array)/2)])
        Array[int(len(Array)/2):len(Array)] = merge_sort(Array[int(len(Array)/2):len(Array)])
        merge(Array)
    return Array

由于不可抗拒因素，所以接下来给靠你的聪明才智去进行一些逻辑补充了，但具体逻辑还是如上图所示。