1、冒泡排序

• 冒泡排序只会操作相邻的两个数据。
• 每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。
• 一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

第一次冒泡操作的详细过程

经过一次冒泡操作之后，6 这个元素已经存储在正确的位置上。要想完成所有数据的排序，我们只要进行 6 次这样的冒泡操作就行了。

实际上，冒泡过程还可以优化。当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作。下图中的另外一个例子，这里面给 6 个元素排序，只需要 4 次冒泡操作就可以了。

优化后的冒泡排序代码如下：

            
              """
    优化的冒泡排序：
    当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作
"""
def bubble_sort(a):
    '''   
    :param a: List[int]
    '''
    length = len(a)
    if length <= 1:
        return 

    for i in range(length):
        made_swap = False
        # 下标j + 1 最大为 length - 1
        for j in range(length-1-i):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                made_swap = True
        # 优化：无数据交换，结束排序操作
        if not made_swap:
                break
    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(bubble_sort(a))
            
          

 

2、插入排序

首先，我们将数组中的数据分为两个区间， 已排序区间 和 未排序区间 。初始已排序区间只有一个元素，就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

如图所示，要排序的数据是 4，5，6，1，3，2，其中左侧为已排序区间，右侧是未排序区间。

插入排序也包含两种操作，一种是元素的 比较 ，一种是元素的 移动 。当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小 ，找到合适的插入位置。找到插入点之后，我们还需要 将插入点之后的元素顺序往后移动一位 ，这样才能腾出位置给元素 a 插入。

代码如下：

            
              """
    插入排序包含两种操作，一种是元素的比较，一种是元素的移动。
    当我们需要将一个数据 a 插入到已排序区间时，需要拿 a 与已排序区间的元素依次比较大小，找到合适的插入位置。
    找到插入点之后，我们还需要将插入点之后的元素顺序往后移动一位，这样才能腾出位置给元素 a 插入。
"""
def insertion_sort(a):
    '''
    :param a: List[int]
    '''
    length = len(a)
    if length <= 1:
        return

    for i in range(1, length):
        value = a[i]
        j = i - 1
        # 查找插入位置，在前面的已排序区间，拿value与已排序区间的元素依次比较大小
        while j >= 0 and a[j] > value:
            # 数据向后移动
            a[j+1] = a[j]
            j -= 1
        # 插入数据
        a[j+1] = value

    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(insertion_sort(a))
            
          

 

3、选择排序

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会 从未排序区间中找到最小的元素，将其放到已排序区间的末尾 。

选择排序是一种不稳定的排序算法。从图中可以看出，选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。  

比如 5，8，5，2，9 这样一组数据，使用选择排序算法来排序的话，第一次找到最小元素 2，与第一个 5 交换位置，那第一个 5 和中间的 5 顺序就变了，所以就不稳定了。

正是因此，相对于冒泡排序和插入排序，选择排序就稍微逊色了。

代码如下：

            
              def selection_sort(a):
    length = len(a)
    if length <= 1:
        return

    for i in range(length):
        # i是每次已排序区间的末尾
        min_index = i
        min_val = a[i]
        # 查找未排序区间中最小的元素
        for j in range(i, length):
            if a[j] < min_val:
                # 未排序区间最小的元素
                min_val = a[j]
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]

    return a

if __name__ == '__main__':
    a = [7,1,4,3,6,5]
    print(selection_sort(a))