排序算法——直接插入排序

一、插入排序

1.1.插入排序介绍

每次将一个待排序的数据按照大小插入到前面已经排好序的适当位置，直到全部数据插入完成为止。

1.2.插入排序思路

💡💡思路·：

1. 从第一个元素开始，该元素可以认为是已经排好的
2. 第二个元素与第一个元素进行比较，如果大于第一个元素，则交换位置，此时左侧的两个元素排序完毕
3. 第三个元素依次与后面的元素进行比较，重复上面操作。直接插入到响应的排序位置，此时左侧的三个元素排列完毕
4. 依次类推，进行n - 1轮比较和交换后，列表中的所有元素均按递增顺序排好。

1.3.时间复杂度

💡💡：
插入排序的元素比较次数和元素移动次数与元素的初始排列有关。

1. 最坏情况下每一行代码都被执行，即全部反向有序，内层每次遍历已排序部分，内循环指令的执行次数为1+2+......+n-1 = n(n-1)/2最坏时间复杂度为O(n^2)
2. 最好的情况下，列表元素已按关键字从小到大有序排列，每次只需要与前面有序元素的最后一个元素比较1次，移动2次元素，总的比较次数为n-1，元素移动次数为2(n-1)，算法复杂度为O(n)
3. 综合以上，直接插入排序的平均时间复杂度为O(n^2)

1.4.空间复杂度

直接插入排序中与问题规模无关，空间复杂度为O(1)

1.5.代码实现

C++代码：

#include<bits/stdc++.h>

using namespace std;

void InsertSort(int a[],int l)
{
    int temp;
    int j;
    // 外循环
    for(int i=1;i<l;i++)
    {
        // 判断2个元素大小
        if(a[i]<a[i-1])
        {
            temp=a[i];
            // 内循环
            for(j=i-1;j>=0&&temp<a[j];j--)
            {
                a[j+1]=a[j];
            }
            a[j+1]=temp;

        }
        for(int k=0;k<l;k++)
            cout<<a[k]<<" ";
        cout<<endl;

    }
}


int main()
{
    int a[10]={3,2,5,4,9,6,8,12,1};
    int len=9;
    InsertSort(a,len);
    return 0;
}

python代码：

# 定义插入排序函数
    def insertSort(nums):
    # 外循环控制排序轮数(元素个数)                                          
        for i in range(nums):
            # 插入元素指针key赋值                                      
            key = i   
            # 内循环负责2个元素的比较                                          
            while key > 0:   
                # 判断2个元素大小                                    
                if nums[key-1]>nums[key]:  
                     # 交换2个元素的位置                      
                     nums[key-1],nums[key] = nums[key],nums[key-1]  
                # 移动指针key位置，key=key-1
                key -= 1  
            # 输出每一轮插入排序的结果                                      
            print(nums) 
        # 函数返回                                        
        return nums    
    # 定义初始元素列表                                         
    nums = [7,2,5,3,1]      
    # 调用插入排序函数，输出排序结果                                         
    print(insertSort(nums))     

# 输出                                   
>>>[7,2,5,3,1][2,7,5,3,1][2,5,7,3,1][2,3,5,7,1][1,2,3,5,7][1,2,3,5,7]           

1.6.优缺点

优点：

每一次的扫描过程：一边比较，一边挪位置。 挪位置是赋值操作，相比冒泡排序的交换操作，要高效。而且相同元素的相对位置不变，如果两个元素相同，插入元素放在相同元素后面。是一种稳定排序。

缺点：

比较轮数较多，且每一轮都是不可或缺的，无法进一步进行优化。如果数据量大的时候，会更低效。时间复杂度O(n^2)