首页 > 算法 > 算法系列之二 插入排序

算法系列之二 插入排序

插入排序是通过不断扩大排序序列的长度来实现的,对于每一个待排序的元素,按其关键字大小插入到前面已经排好序的子序列中的适当位置,形成更长的有序子序列。
当每一个待排序的元素都这样子被循环迭代处理后,排序完成。

假设数组为a[0...n-1]
1、初始时,a[0]自成一个有序的子序列,无序区为a[1...n-1],令i=1
2、对于每一个a[i...n-1],将其并入到当前有序的子序列a[0...i-1]中形成更长的有序序列a[0,i],直到处理完i==n-1,也即i==n的时候排序完成
3、当i == n的时候,a[0,n-1]的每一个元素都插入到正确的位置
上述1到3,采用了算法导论的循环不定式证明了这样的算法是正确的

以下以升序为例

方法一:并入a[i]到有序子序列a[0...i-1]的时候,可以通过交换相邻数据的方法来实现
设j = i – 1;若a[j] > a[j+1],则交换a[j]和a[j+1],再j–继续这样循环处理,直到不满足这个条件或者j==-1。

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

方法二:并入a[i]到有序子序列a[0...i-1]的时候,可以通过搜索跟数据后移的方法来实现
1、先搜索到应该插入的位置pos
2、然后将a[pos...i-1]向后移动到a[pos+1...i],腾出a[pos]的位置,然后将a[i]插入到a[pos]

void InsertSort2(int a[], int n)
{
     int i, j, k,pos;
     //循环从第二个数组元素开始,因为arr[0]作为最初已排序部分
     for (i = 1; i < n; i++)
     {
          //为a[i]在前面的有序子序列中找一个合适的位置
          for (j = i - 1; j >= 0; j--)
               if (a[j] < a[i])
                    break;
          //合适的位置是在j之后,也即j+1
          pos = j+1;
          //这个位置不是i自己(如是自己,不需要处理)
          if (pos != i)
          {
               //先将a[pos...i-1]向后移动到a[pos+1...i],腾出a[pos]的位置,然后将a[i]插入到a[pos]
               int temp = a[i];
               for (k = i - 1; k >=pos ; k--)
                    a[k + 1] = a[k];
               a[pos] = temp;
          }
     }
}

方法三:并入a[i]到有序子序列a[0...i-1]的时候,可以通过搜索跟数据后移同时进行的方法来实现
设j = i-1;若a[j] > a[i],则将a[j]后移到a[j+1],然后再j–继续这样循环处理,直到不满足这个条件或者j==-1

void InsertSort3(int a[], int n)
{
     int i, j;
     for (i = 1; i < n; i++)
     {
          if (a[i] >= a[i-1]) 
          {
               break;
          }
          int temp = a[i];
          for (j = i-1; j >= 0 && a[j] > temp; j--)
          {
               a[j + 1] = a[j];
          }
          a[j+1] = temp;
     }
}

总结上述三种方法:
方法一,因为采用了swap,每个swap需要做三次赋值的操作,平均时间复杂度可以认为是3n*n
方法二,搜索后,再数据后移,分成两步,平均时间复杂度是2*n*n
方法三,搜索跟数据后移同时处理,平均时间复杂度是n*n
方法三是这三种插入排序方法中最优的算法

插入排序的时间复杂度分析:
最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可
最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次,插入排序的赋值操作是比较操作的次数减去(n-1)次。
平均来说插入排序算法复杂度为O(n2)

插入排序的稳定性分析:
若前面的元素跟当前元素一样,则不会做移位的操作,因此是稳定

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.