【算法基础】选择排序与冒泡排序的思想与实现

1. 选择排序

1.1 思想

选择排序的思想很简单，如上图所示。在每一次遍历子数组的过程中，选择最小的和子数组的第一位交换。子数组的选择从一开始的整个数组，到后面范围逐渐向原数组最后一位缩减。复杂度$O(n^2)$

1.2 实现

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp


if __name__ == '__main__':
    arr = [6, 3, 1, 4, 2, 5]
    print("原数组：" + str(arr))

    for i in range(0, len(arr) - 1):
        min_idx = i
        for j in range(i + 1, len(arr)):
            min_idx = j if arr[j] < arr[min_idx] else min_idx
        swap(arr, i, min_idx)
    print("排序后的数组：" + str(arr))

main方法里是对选择排序的实现。选择排序就是，从剩下的数里面选择最小/最大的数，与当前子数组的第一位数进行交换。

2. 冒泡排序

2.1 思想

如上图所示，冒泡排序的思想是，在每一轮将最大的数换到子数组的最后一位上去。通过多地置换，最终实现数组的有序。复杂度$O(n^2)$

2.2 实现

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp


if __name__ == '__main__':
    arr = [6, 3, 1, 4, 2, 5]
    print("排序前的数组：" + str(arr))

    for i in range(len(arr) - 1, 0, -1):
        for j in range(0, i):
            if arr[j] > arr[j + 1]:
                swap(arr, j, j + 1)

    print("排序后的数组：" + str(arr))