八大排序之插入排序

算法核心思想

插入排序的核心思想是将数组中所有的元素分别和前面已经排序好的元素相比较， 如果后面选择的元素比已排序的元素小，则交换位置，直至比较完成。

具体实现逻辑

1. 取数组的第一个元素为已经排序好的元素，将第一个元素看作有序序列
2. 取数组的第二个元素和已经排序好的元素进行比较，如果第二个元素比第一个元 素小，则交换位置，排序完成后第一个元素和第二个元素必然有序，形成新的有 序数列
3. 取数组的第三个元素，依次和第一个第二个元素进行比较，排序完成后第一个， 第二个，第三个元素形成一个有序数列
4. 重复取第四个元素，第五个元素，第六个元素。。。
5. 最后一个元素重复上述步骤，最终实现整个数组有序

实现逻辑图示

代码实现-WHILE版本

def insertSort(arr): 
    i = 1
    while i<len(arr):
        j = i 
        while j>=1: 
            if arr[j]<arr[j-1]: 
                arr[j-1],arr[j] = arr[j],arr[j-1] 
                j-=1 
            else: 
                break 
        i+=1 
    return arr

代码实现-FOR版本

def insertSort(arr):
    #拆分数组为有序部分和无序部分
    #有序部分：arr[0]
    #无序部分：arr[1:]
    #取无序部分的元素
    for i in range(1,len(arr)):
        #arr[i]就是我们待插入的元素
        #arr[:i]是有序数组
        #arr[i:]是无序数组
        #将arr[i]插入到0到i-1的元素数组里面
        #具体排序过程
        for j in range(i,0,-1):
            if arr[j]<arr[j-1]:
                arr[j],arr[j-1] = arr[j-1],arr[j]
            else:
                break
    return arr
arr = [1,22,-1,9,23,5,9,9,2,23,1,2999,92,1]
print(insertSort(arr))

时间复杂度分析

1. 在最好的情况下，即序列已经是排好序的情况下，每次比较一次就退出while循环，则总比较次数 是n-1次，时间复杂度是O(n)
2. 在最坏的情况下，即每次while循环都要比较到第一个元素，则：
3. 第一次循环，比较了1次；
4. 第二次循环，比较了2次；
5. ...
6. 第n-1次循环，比较了n-1次；
7. 总的比较次数是1+2+3+...+(n-1) = n(n-1)/2
8. 我们上面所求得的n(n-1)/2，其时间复杂度，最大的影响因子是n²/2，故其时间复杂度是O(n²)。

优缺点分析

1. 在大多数元素已经有序的情况下，插入排序的工作量较小，这个结论很明显，如果 一个数组大部分元素都有序，那么数组中的元素自然不需要频繁地进行比较和交换。
2. 在元素数量较少的情况下，插入排序的工作量较小，这个结论更加显而易见，插入 排序的工作量和n的平方成正比，如果n比较小，那么排序的工作量自然要小得多。
3. 插入排序是一种稳定排序（稳定的定义：相同元素的位置没有发生变化）

执行解析

外层for遍历读取第n个元素，当读取第n个元素的时候前面n-1个元素是已经排序好 的序列，使用第n个元素和前面的n-1个元素进行依次比较，如果某一个元素比较的 时候比第n个元素大，则交换该元素和第n个元素的位置，这样比较轮下来从第0个 元素到第n个元素就是一个有序序列了。