排序算法之插入排序

插入排序是一种简单直观的排序算法。它的工作原理非常类似于我们抓扑克牌。

对于未排序数据(右手抓到的牌)，在已排序序列(左手已经排好序的手牌)中从后向前扫描，找到相应位置并插入。

插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，比如量级小于千，那么插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序（通常为8个或以下）

具体算法描述如下：

从第一个元素开始，该元素可以认为已经被排序

取出下一个元素，在已经排序的元素序列中从后向前扫描

如果该元素（已排序）大于新元素，将该元素移到下一位置

重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

将新元素插入到该位置后

重复步骤2~5

// 分类 ------------- 内部比较排序

// 数据结构 ---------- 数组

// 最差时间复杂度 ---- 最坏情况为输入序列是降序排列的,此时时间复杂度O(n^2)

// 最优时间复杂度 ---- 最好情况为输入序列是升序排列的,此时时间复杂度O(n)

// 平均时间复杂度 ---- O(n^2)

// 所需辅助空间 ------ O(1)

// 稳定性 ------------ 稳定

#include

usingnamespacestd;

intmain()

{

intA[] = {6,5,3,1,8,7,2,4};//从小到大插入排序

intn =sizeof(A) /sizeof(int);

inti, j, get;

for(i =1; i < n; i++)//类似抓扑克牌排序

{

get = A[i];//右手抓到一张扑克牌

j = i -1;//拿在左手上的牌总是排序好的

while(j >=0&& A[j] > get)//将抓到的牌与手牌从右向左进行比较

{

A[j +1] = A[j];//如果该手牌比抓到的牌大,就将其右移

j--;

}

A[j +1] = get;//直到该手牌比抓到的牌小(或二者相等),将抓到的牌插入到该手牌右边(相等元素的相对次序未变,所以插入排序是稳定的)

}

printf("插入排序结果：");

for(i =0; i < n; i++)

{

printf("%d ", A[i]);

}

printf("\n");

return0;

}