排序算法的稳定性：

假设有一串数据：（4，1）（3，1）（3，7）（5，6）；要求按照第一个数排序，结果如下：

第一种：（3，1）（3，7）（4，1）（5，6）（3相同，维持原来的次序）

第二种：（3，7）（3，1）（4，1）（5，6）（3相同，次序被改变）

第一种是稳定的。

冒泡排序(以从小到大排为例)：

每次走一遍把最大的元素冒泡，排到最后。

'''
冒泡排序：它也可以用于之前讲的链表什么的,只是交换部分稍微烦一点，思想一样。这里简单一点 ，以数字为例
'''
def bubble_sort(alist):
    '''冒泡排序，参数为列表'''
    n = len(alist)-1
    for j in range(n):
        for i in range(n-j):
            if alist[i]>alist[i+1]:
                # 前一个大于后一个，交换
                alist[i], alist[i+1] = alist[i+1], alist[i]    # 这样写在python这种动态语言中可以

if __name__ == '__main__':
    a = [2,0,5,1,10]
    bubble_sort(a)
    print(a)

冒泡排序的时间复杂度为：最坏可以认为是O（n^2）,稳定的

改进：假如传入的序列就是有序的，比如[1,2,3,4,5,6]。此时按照上面代码还是要一步步比较，复杂度是一样的。改进之后，最优时间复杂度为O(n)，最坏时间复杂度不变。

def bubble_sort(alist):
    '''冒泡排序，参数为列表'''
    n = len(alist)-1
    for j in range(n):
        count = 0
        for i in range(n-j):
            if alist[i]>alist[i+1]:
                # 前一个大于后一个，交换
                alist[i], alist[i+1] = alist[i+1], alist[i]    # 这样写在python这种动态语言中可以
                count += 1
        if count == 0:
            return 

选择排序：

思想解释：每次找到最小的值，与无序数中的一个数交换，比如：

a = [52，100，23，43，55，20，17，108]

找到最小值是17，将17与52交换，得：

a = [17，100，23，43，55，20，52，108]

看除了第一个数17外，其他最小的为20，与“第一个数”100交换：

a = [17，20，23，43，55，100，52，108]

此时，前面两个数已经有序，以此往下。

def select_sort(alist):
    """选择排序，既然是研究数据结构与算法，这里不用min()函数"""
    n = len(alist)
    for j in range(n-1):
        # 记录最小值的位置，这里首次默认是无序中的第一个
        min_index = j
        for i in range(j+1,n):
            if alist[i]<alist[min_index]:
                min_index = i
        alist[j], alist[min_index] = alist[min_index], alist[j]

选择排序的时间复杂度：O(n^2)，不稳定

插入算法：

思想理解，与上面选择排序有点雷士，其实还是将序列无形的分为两部分。比如序列[52，100，23，43，55，20，17，108]。

将序列分为[52，                      100，23，43，55，20，17，108]，第一部分是有序的。

然后将无序中的第一个100与有序中52比较，放在正确的位置[52，100，                      23，43，55，20，17，108]，

同理接着比较23与[52，100]，将其插入正确的位置[23，52，100，                            43，55，20，17，108]