程序算法艺术与实践:经典排序算法之插入排序
最后更新于：2022-04-01 21:41:01
插入排序(Insertion Sort)的基本思想是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子文件中的适当位置，直到全部记录插入完成为止。
#### 基本思想与伪代码
经过j-1遍处理后,A[1..j-1]己排好序。第j遍处理仅将A[j]插入L[1..j-1]的适当位置，使得A[1..j]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较A[j]和A[j-1]，如果A[j-1]≤ A[j]，则A[1..j]已排好序，第i遍处理就结束了；否则交换A[j]与A[j-1]的位置，继续比较A[j-1]和A[j-2]，直到找到某一个位置i(1≤i≤j-1)，使得A[j] ≤A[j+1]时为止。用伪码描述如下：
~~~
算法: InsertSort(A,n)
输入：n个数组A
输出：按照递增顺序的数组A
1. for j ← 2 to n do
2. x←A[j]
3. i ← j-1 //行3到行7把A[j]插入A[1.....j-1]之中
4. while i >0 and x =0 && t_<:
~~~
void InsertionSort(int *ptritems, int count) {
int i, j, k;
for (i=1; i< count; ++i) {
k = ptritems[i];
for ( j=i-1; (j>=0) && (k
';