数据的排序方法_数据排序

1. 冒泡排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定

思路：（1）列表每两个相邻的数，如果前面比后面的大，则交换两个数的位置
           （2）一趟排序完成后，别找出当前列表中的最大数，并放在当前列表的末尾

def bubble_sort(list_num):
    n = len(list_num)
    for i in range(n-1):      # i 代表第几趟，每排完一趟后，列表后面的有序数组便增加一个数
        flag_change = False     # 如果某一趟执行完后没有出现元素交换的现象，说明列表已经有序，可直接跳出循环
        for j in range(n-1-i):        # j代表列表前面还有几个无序数
            if list_num[j] > list_num[j+1]:
                list_num[j],list_num[j+1] = list_num[j+1],list_num[j]
                flag_change = True
        if not flag_change:
            break
    return list_num

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

思路：（1）一趟排序记录最小的数，放到第一个位置
           （2）再一趟排序记录最小的数，放到第二个位置
           （3）。。。。。。

def select_sort(list_num):
    n = len(list_num)
    for i in range(n-1):      # i代表第几趟
        min_index = i
        for j in range(i+1,n):      # j代表从列表后面的无序数组中选择一个最小数
            if list_num[j] < list_num[min_index]:
                min_index = j
        list_num[i],list_num[min_index] = list_num[min_index],list_num[i]
    return list_num

3. 插入排序：时间复杂度O(n^2)，空间复杂度O(1)，稳定

思路：（1）初始时手里（有序区）只有一张牌（列表的第一个元素）
           （2）每次从无序区摸一张牌（剩余列表的第一个元素）插入手里（有序区）的正确位置

d