输入：n个数的数<a1,a2,a3,a4>

输出：输人序列的一个排列(a1,a2,…，an)，满足a1’≤a2’≤…≤an’

书中用了一个很好的例子来描述插入算法的原理，像许多人排序自己手中的扑克牌。

排序一手扑克牌，开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每人从子上拿走一张牌并将它插入左手中正确的位置，我们从右到左将它与在手中的每张牌进行比较，拿在左手上的牌总是排序好的，只需将该牌插入到正确的位置。

 

书中将伪代码命名为INSERTION-SORT(A), 其中A为一个数组。该算法是原址排

序：算法在数组A中重排这些数，在任何

片候，最多只有其中的常数个数字存储在数组外在过程 INSERTION-SORT结束时，输入数组包含已排序的数组

下面给出的关于c++语言的实现

 

#include <iostream>

void insertion_sort(int a[],int n) // n为该数组的长度
{
  for (int j = 1; j <n ; j++)
  {
    int key = a[j];
    int i = j - 1;
    while (i >= 0 && a[i] > key)
    {
      a[i + 1] = a[i];
      i -= 1;
    }
    a[i + 1] = key;
  }
}
int main()
{
  int a[] = { 3,6,7,1,3 };
  insertion_sort(a,sizeof(a)/sizeof(a[0]));
  
}

 

该算法的执行情况：

 

版权声明：本文为king0原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/king0/p/10440317.html