几乎所有的排序都有两个基本的操作：

1. 关键字大小的比较。
2. 改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式 存储的记录则通过改变指向记录的指针实现重定位。

插入排序

插入排序类型算法有直接插入排序和希尔排序，它们的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。

直接插入排序

1.算法思想：设待排序数据存放在数组 A[1..n]中，则 A[1]可看作是一个有序序列，让 i 从 2 开始，依次将 A[i]插入到有序序列 A[1..i-1]中， A[n]插入完毕则整个过程结束， A[1..n]成为有序序列。

示例：[【2】,1,4,7,3,5,3]

[【1,2】,4,7,3,5,3]

[【1,2,4】,7,3,5,3]

[【1,2,4,7】,3,5,3]

[【1,2,3,4,7】,5,3]

[【1,2,3,4,5,7】,3]

[【1,2,3,3,4,5,7】]

2. 算法实现：

在数组中增加元素 A[0]作为关键值存储器和循环控制开关。第 i 趟排序，即 A[i]的插入过程为：

① 保存 A[i]→A[0]

② j = i -1

③ 如果 A[j]<=A[0]（即待排序的 A[i]），则 A[0]→A[j+1]，完成插入；否则，将 A[j]后移一个位置：A[j]→A[j+1]； j = j - 1；继续执行 ③。

算法具有稳定性，时间复杂度 O(n²)。

希尔排序

1.算法思想：任取一个小于 n 的整数 S1 作为增量，把所有元素分成 S1个组。所有间距为 S1 的元素放在同一个组中。

第一组： {A[1]， A[S1+1]， A[2S1+1]， ……}

第二组： {A[2]， A[S1+2]， A[2S1+2]， ……}

第三组： {A[3]， A[S1+3]， A[2S1+3]， ……}

……

第 s1组： {A[S1]， A[2S1]， A[3S1]， ……} 先在各组内进行直接插人排序；然后，取第二个增量 S2（<S1）重复上述的分组和排序，直至所取的增量 St=1 （St<St-1<St-2<…<S2<S1），即所有记录放在同一组中进行直接插入排序为止