排序算法系列:插入排序算法(InsertionSort)

标签: 排序

插入排序原理很简单,讲一组数据分成两组,我分别将其称为有序组与待插入组。每次从待插入组中取出一个元素,与有序组的元素进行比较,并找到合适的位置,将该元素插到有序组当中。就这样,每次插入一个元素,有序组增加,待插入组减少。直到待插入组元素个数为0。当然,插入过程中涉及到了元素的移动。

 

为了排序方便,我们一般将数据第一个元素视为有序组,其他均为待插入组。

 

下面以升序为例进行一次图解:

 

 

 

代码为:

#include <bits/stdc++.h>
using namespace std;

void InsertionSort(int *num,int n)
{
    int tem;
    for(int i=1;i<n;i++){
        int j=i;
        tem=num[j];
        //注意判断条件为两个,j>0对其进行边界限制。第二个为插入判断条件
        while(j>0&&tem<num[j-1]){
            //若不是合适位置,有序组元素向后移动
            num[j]=num[j-1];
            j--;
        }
        //找到合适位置,将元素插入
        num[j]=tem;
    }
}
int main()
{
    int num[8]={9,3,4,2,6,7,5,1};
    InsertionSort(num,8);
    for(int i=0;i<8;i++){
        if(i) cout<<' '<<num[i];
        else cout<<num[i];
    }
    cout<<endl;
    return 0;
}

 

复杂度分析

排序方法 时间复杂度 空间复杂度 稳定性 复杂性
平均情况 最坏情况 最好情况
插入排序 O(n2) O(n2) O(n) O(n) 稳定 简单

这里的最坏的情况和平均情况从代码中就可以看出来,因为有两嵌套的for循环嘛。那么其最好的情况呢?这个就是对于一个有序的序列来说,不需要进行交换,只是比较了n次,所以这里最好的时间复杂度就是O(n)。

原文链接:加载失败,请重新获取