冒泡排序、选择排序、插入排序、希尔排序

冒泡排序

基本思想

代码实现

# 冒泡排序
def bubble_sort(arr):
    length = len(arr) - 1
    for i in range(length):
        flag = True
        for j in range(length - i):
            if arr[j] > arr[j + 1]:
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
                flag = False
 
        print(f'第{i + 1}趟的排序结果为：', arr)
 
        if flag:
            # 代码优化，如果某一趟排序中没有发生交换，表示序列已经有序，可以提前结束循环
            break
 
 
bubble_sort([3, 9, -1, 10, 20])
bubble_sort([3, 9, -1, 10, -2])

选择排序

基本思想

 

代码实现

# 选择排序
def select_sort(arr):
    for i in range(len(arr) - 1):  # 进行 n-1 趟排序
        min = arr[i]
        index = i
        for j in range(i + 1, len(arr)):
            if min > arr[j]:
                min = arr[j]
                index = j
 
        if index != i:
            arr[index] = arr[i]
            arr[i] = min
 
        print(f'第{i + 1}趟排序结果：', arr)
 
 
select_sort([3, 9, -1, 10, -2])
select_sort([3, 9, -1, 10, 20])

插入排序

基本思想

代码实现

# 插入排序
def insert_sort(arr):
    # for 循环遍历的是待排序的序列，即无序的序列
    for i in range(len(arr) - 1):
        insert_val = arr[i + 1]  # 待插入有序列表的值
        # 以 insert_index 位置为分割点，可以把 insert_index 及其之前的元素理解为已排序的序列
        # insert_index 以后的元素是无序序列
        insert_index = i  # 待插入值的前一个值的下标，即有序列表的最后一个元素的位置
 
        # while 循环遍历的是已有序的序列
        # insert_index >= 0 保证下标不越界
        # 从后往前访问有序列表
        # insert_val < arr[insert_index] 当待插入的值比有序列表中的值还小时，往前遍历有序列表，继续比较
        while insert_index >= 0 and insert_val < arr[insert_index]:
            # 将 arr[insert_index] 值后移，空出前面的位置存放待插入的值
            arr[insert_index + 1] = arr[insert_index]
            # 继续访问有序列表的前一个元素
            insert_index -= 1
 
        # 退出循环时，表示找到了插入的位置
        # 插入的位置为 insert_index + 1 ，因为 insert_index 位置要么为 -1 ，要么为比待插入值小的数
        arr[insert_index + 1] = insert_val
        print(f'第{i + 1}个待插入的值插入后的结果', arr)
 
 
insert_sort([3, 9, -1, 10, -2])
insert_sort([3, 9, -1, 10, 20])
 
 
# 同样的思想，稍微不同的写法
def insert_sort1(arr):
    # arr = [6, 5, 3, 1, 8, 7, 2, 4]
    for i in range(1, len(arr)):
        t = arr[i]
        while t < arr[i - 1] and i >= 1:
            arr[i] = arr[i - 1]
            i -= 1
        arr[i] = t
 
 
arr = [6, 5, 3, 1, 8, 7, 2, 4]
insert_sort1(arr)
print(arr)

希尔排序

基本思想

 

代码实现

# 希尔排序——交换法（效率低）
def shell_sort1(arr):
    """
    # 以 [8, 9, 1, 7, 2, 3, 5, 4, 6, 0] 为例进行分析
    # 希尔排序的第一轮
    # 第一轮将数组分为 10 // 2 = 5 组
    for i in range(5, len(arr)):
        # 遍历各组中所有的元素（共5组，每组2个元素），步长为5
        j = i - 5
        while j >= 0:
            # 如果当前元素大于加上步长后的哪个元素，说明需要交换
            if arr[j] > arr[j + 5]:
                temp = arr[j]
                arr[j] = arr[j + 5]
                arr[j + 5] = temp
            j -= 5
    print('希尔排序的第一轮结果：', arr)
    # 希尔排序的第二轮 [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
    # 第二轮将数组分为 5 // 2 = 2 组
    for i in range(2, len(arr)):
        # 遍历各组中所有的元素（共2组，每组5个元素），步长为5
        j = i - 2
        while j >= 0:
            # 如果当前元素大于加上步长后的哪个元素，说明需要交换
            if arr[j] > arr[j + 2]:
                temp = arr[j]
                arr[j] = arr[j + 2]
                arr[j + 2] = temp
            j -= 2
    print('希尔排序的第二轮结果：', arr)
    # 希尔排序的第三轮 [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
    # 第三轮将数组分为 2 // 2 = 1 组
    for i in range(1, len(arr)):
        # 遍历各组中所有的元素（共1组，每组10个元素），步长为5
        j = i - 1
        while j >= 0:
            # 如果当前元素大于加上步长后的哪个元素，说明需要交换
            if arr[j] > arr[j + 1]:
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            j -= 1
    print('希尔排序的第三轮结果：', arr)
    """
 
    # 交换法希尔排序
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            # 遍历各组中所有的元素，步长为gap
            j = i - gap
            while j >= 0:
                # 如果当前元素大于加上步长后的哪个元素，说明需要交换
                if arr[j] > arr[j + gap]:
                    temp = arr[j]
                    arr[j] = arr[j + gap]
                    arr[j + gap] = temp
                j -= gap
 
        print('本轮排序结果：', arr)
        gap //= 2
 
 
# 希尔排序——移位法（效率更高）
def shell_sort2(arr):
    # 移位法希尔排序，效率更高
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap, len(arr)):
            j = i
            temp = arr[j]
            if arr[j] < arr[j - gap]:
                while j - gap >= 0 and temp < arr[j - gap]:
                    arr[j] = arr[j - gap]
                    j -= gap
                arr[j] = temp
 
        print('本轮排序结果：', arr)
        gap //= 2
 
 
shell_sort1([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])
shell_sort2([8, 9, 1, 7, 2, 3, 5, 4, 6, 0])