冒泡排序

思想

Donald E. Knuth（1974 年图灵奖获得者）：“冒泡排序法除了它迷人的名字和导致了某些有趣的理论问题这一事实外，似乎没有什么值得推荐的。”

def bubble_sort(nums):
    for i in range(len(nums)):
        for j in range(i,len(nums)):
            if nums[i] > nums[j]:
                flag = False
                nums[i], nums[j] = nums[j], nums[i]
    return nums

但优化后的冒泡排序,在数组有序时时间复杂度可以降为O(n)，可以用于判断一个数组是否有序。

优化方法如下述代码所示：

如果某轮的比较没有发生交换，说明数组已经有序，直接return。

def bubble_sort(nums):
    for i in range(len(nums)):
        flag = True
        for j in range(i,len(nums)):
            if nums[i] > nums[j]:
                flag = False
                nums[i], nums[j] = nums[j], nums[i]
        if flag:
            return nums
    return nums

分析

冒泡排序的时间复杂度可以视为 $O(n^2)$

空间复杂度因为只在原数组上进行比较与交换所以为 $O(1)$ 。

相对顺序并没有发生改变，是稳定排序算法。

选择排序

思想

选择排序的思想是：双重循环遍历数组，每经过一轮比较，找到最小(大)元素的下标，将其交换至首位。即每轮归位一个数。

def select_sort(nums):
    for i in range(len(nums)):
        min_idx = i
        for j in range(i, len(nums)):
            if nums[j]<nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    return nums

分析

选择排序与冒泡的不同之处在于：

冒泡排序在比较过程中就不断交换；而选择排序增加了一个变量保存最小值 / 最大值的下标，遍历完成后才交换，减少了交换次数。

选择排序的时间复杂度可以视为** $O(n^2)$ **

空间复杂度因为只一个元素的临时变量所以为** $O(1)$ **。

相对顺序会发生改变，是不稳定的排序算法。

例如数组：[2, 2, 1]，在选择排序中第一次进行交换时，原数列中的两个 2 的相对顺序就被改变了，因此，我们说选择排序是不稳定的。

插入排序

插入排序的思想非常简单，生活中有一个非常常见的场景：在打扑克牌时，我们一边抓牌一边给扑克牌排序，每次摸一张牌，就将它插入手上已有的牌中合适的位置，逐渐完成整个排序。

def insert_sort(nums):
    for i in range(1, len(nums)):
        temp = nums[i]
        #j从i-1 到 0倒序
        for j in range(i-1,-1,-1):
            if(nums[j]<=temp):
                break
            if(nums[j]>temp):
                nums[j],nums[j+1] = temp,nums[j]
    return nums