输入：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])); }
该算法的执行情况：
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
