【算法】插入排序算法

1. 算法简介

  插入排序是一种简单直观并且稳定的排序，虽然插入排序的时间复杂度为O(n^2)，但是在一个几乎有序的序列中插入一个数，要求插入后此数据序列仍然有序，这时候插入算法便具有很大的优势。

2. 算法思想

  插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

  插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

例如：

一个初始序列为：8、6、2、3、1、5、7、4

将第一个元素进行排序，由于 只有一个元素，所以不用排，第一个元素自身就是有序的

第一趟排序之后结果： 8、6、2、3、1、5、7、4

然后将第二个元素与第一个元素进行比较，8比6大，所以 8应该放在6后面，并依次类推。。

第二趟排序结果为： 6、8、2、3、1、5、7、4

第三趟排序结果为： 2、6、8、3、1、5、7、4

第四趟排序结果为： 2、3、6、8、1、5、7、4

第五趟排序结果为： 1、2、3、6、8、5、7、4

第六趟排序结果为： 1、2、3、5、6、8、7、4

第七趟排序结果为： 1、2、3、5、6、7、8、4

第八趟排序结果为： 1、2、3、4、5、6、7、8

代码实现

void swap(int* a,int* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

void insertionSort(int arr[],int n)
{
    for(int i=1;i<n;i++){
        
        for(int j=i;j>0 && arr[j]<arr[j-1];j--){
            swap(&arr[j],&arr[j-1];      
        }
    }
}

  以上便是插入排序的基本实现,代码非常简单，但是上面代码的运行效率却比较低，甚至比选择排序和冒泡排序还要差，为什么呢？ 就是因为不断进行swap交换，消耗了大量的时间一次swap就是三次赋值。下面进行了改进，用一个变量记录，要替换的数值和序列下表，用赋值来代替替换，改进后的代码如下：

void insertionSort(int arr[],int n)
{
    for(int i=1;i<n;i++){
        int temp = arr[i];
        int j;
        for(j=i;j>0 && arr[j-1]>temp;j--){
            arr[j] = arr[j-1];          
        }
        arr[j] = temp;
    }
}

  插入排序与选择排序、冒泡排序等相比，虽然时间复杂度都是O(n^2)，但是插入排序确实可以提前终止循环条件的，所以往往插入排序会更快一些，尤其在序列几乎有效的条件下，插入排序的优势更加明显。