Leetcode刷题-马士兵课程笔记

排序算法

1.选择排序

思路：依次遍历，找到当前未被排序的序列中的最小值，放在最前边，直到所有数都按照顺序排列

    def SelectionSort(arr):
        for i in range(len(arr)):
            minPos = i
            for j in range(i + 1, len(arr)):
                # minPos在一次循环中不断更新，要找到在未被排序的数中的最小值所在的位置（只要arr[j] < arr[minPos]，则minPos就会更新为j）
                # 利用minPos指针找到最小值对应的j后，与i位置交换顺序
                # 注意：每一轮minPos都会更新为新的i
                if arr[j] < arr[minPos]:
                    minPos = j
            arr[i], arr[minPos] = arr[minPos], arr[i]

改进：每一次内层循环，找到最大值和最小值，最小值放前边，最大值放后边

# 选择排序改进：最小值放左边，最大值放右边
    def SelectionSort2(arr):
        for i in range(len(arr) // 2):
            minPos = i
            maxPos = len(arr) - i - 1
            for j in range(minPos, maxPos + 1):
                if arr[j] > arr[maxPos]:
                    maxPos = j
                if arr[j] < arr[minPos]:
                    minPos = j

            # 最大值在最前边 and 最小值在最后边
            if (maxPos == i) and (minPos == len(arr) - i - 1):
                arr[maxPos], arr[minPos] = arr[minPos], arr[maxPos]

            # 最大值在最前边
            elif maxPos == i:
                arr[maxPos], arr[len(arr) - i - 1] = arr[len(arr) - i - 1], arr[maxPos]
                arr[i], arr[minPos] = arr[minPos], arr[i]

            # 最小值在最后边
            elif minPos == len(arr) - i - 1:
                arr[i], arr[minPos] = arr[minPos], arr[i]
                arr[len(arr) - i - 1], arr[maxPos] = arr[maxPos], arr[len(arr) - i - 1]

            # 其他情况
            else:
                arr[i], arr[minPos] = arr[minPos], arr[i]
                arr[len(arr) - i - 1], arr[maxPos] = arr[maxPos], arr[len(arr) - i - 1]

2.冒泡排序

思路：每一次从未被排序的数组的第一个数字开始，依次比较前后两个数的大小，将较大的留在后边，直到所有数字都到了正确的位置。

    def BubbleSort(arr):
        # 需要循环len次，保证每一个数都会经历一次比较大小--交换位置的过程
        for i in range(len(arr) - 1, 0, - 1):
            # 经过一次内层循环，一个数会被移动到应该在的位置
            for j in range(0, i, 1):
                if arr[j] > arr[j + 1]:
                    arr[j], arr[j + 1] = arr[j + 1], arr[j]

3.插入排序

思路：从第二个位置开始，和前边的数比较，若该数小于前边的值，插入到前边的位置；依次到第3个位置、第4个位置

插入排序比冒泡排序快一倍多：插入排序不用每次都交换次序，而冒泡排序是要依次和后边的数比较大小并交换顺序