3.4插入排序
插入排序的基本思想是，经过i-1遍处理后，对象0～i-1己排好序，第i遍处理的过程是将对象i插入对象0～i-1之间的适当位置，使得对象0～i又是排好序的序列。
void CSortDlg::OnInsertSort()
{
CClientDC dc(this);
dc.SetBkColor(RGB(180, 180, 180));
int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名
//初始化每个位置对应的成员
for (int i = 0; i < SORT_OBJECT_NUM; i++)
{
objectName[i] = i;
}
//插入排序
for (i = 1; i < SORT_OBJECT_NUM; i++)
{
int iPos = i - 1;
int iName = objectName[i];
CString strName, strNum;
while (iPos >= 0 && sortObject[iName].iNumber < sortObject[objectName[iPos]].iNumber)
{
objectName[iPos + 1] = objectName[iPos];
sortObject[objectName[iPos]].iSeq += 1;
//显示iPos+1位置的对象
strName.Format("%d", objectName[iPos + 1]);
dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
if (sortObject[objectName[iPos + 1]].iNumber < 1000)
{
strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
}
else
{
strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
}
dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);
iPos--;
Sleep(1000);
}
objectName[iPos + 1] = iName;
sortObject[objectName[iPos + 1]].iSeq = iPos + 1;
//显示iPos+1位置的对象
strName.Format("%d", objectName[iPos + 1]);
dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
if (sortObject[objectName[iPos + 1]].iNumber < 1000)
{
strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
}
else
{
strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
}
dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);
Sleep(1000);
}
}
下面是我们追踪所得的一次插入排序的轨迹：
{
CClientDC dc(this);
dc.SetBkColor(RGB(180, 180, 180));
int objectName[SORT_OBJECT_NUM]; //每个位置对应的成员名
//初始化每个位置对应的成员
for (int i = 0; i < SORT_OBJECT_NUM; i++)
{
objectName[i] = i;
}
//插入排序
for (i = 1; i < SORT_OBJECT_NUM; i++)
{
int iPos = i - 1;
int iName = objectName[i];
CString strName, strNum;
while (iPos >= 0 && sortObject[iName].iNumber < sortObject[objectName[iPos]].iNumber)
{
objectName[iPos + 1] = objectName[iPos];
sortObject[objectName[iPos]].iSeq += 1;
//显示iPos+1位置的对象
strName.Format("%d", objectName[iPos + 1]);
dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
if (sortObject[objectName[iPos + 1]].iNumber < 1000)
{
strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
}
else
{
strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
}
dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);
iPos--;
Sleep(1000);
}
objectName[iPos + 1] = iName;
sortObject[objectName[iPos + 1]].iSeq = iPos + 1;
//显示iPos+1位置的对象
strName.Format("%d", objectName[iPos + 1]);
dc.TextOut(objectCoord[iPos + 1].x - 5, objectCoord[iPos + 1].y - 8,strName);
if (sortObject[objectName[iPos + 1]].iNumber < 1000)
{
strNum.Format(" %d", sortObject[objectName[iPos + 1]].iNumber);
}
else
{
strNum.Format("%d", sortObject[objectName[iPos + 1]].iNumber);
}
dc.TextOut(objectCoord[iPos + 1].x - 15, objectCoord[iPos + 1].y - 30,strNum);
Sleep(1000);
}
}
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 270 738 1699 4875 228 706 102 1787 1565
228 262 270 738 1699 4875 706 102 1787 1565
228 262 270 706 738 1699 4875 102 1787 1565
102 228 262 270 706 738 1699 4875 1787 1565
102 228 262 270 706 738 1699 1787 4875 1565
102 228 262 270 706 738 1565 1699 1787 4875
下面的动画（GIF格式）演示了插入排序的过程：262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 738 1699 4875 270 228 706 102 1787 1565
262 270 738 1699 4875 228 706 102 1787 1565
228 262 270 738 1699 4875 706 102 1787 1565
228 262 270 706 738 1699 4875 102 1787 1565
102 228 262 270 706 738 1699 4875 1787 1565
102 228 262 270 706 738 1699 1787 4875 1565
102 228 262 270 706 738 1565 1699 1787 4875
插入排序法的比较次数和交换次数与被排序数组的初始顺序情况有关：在最好、最坏、平均三种情况下，总的比较次数分别是(n-1)、(n2+n-2)/4、(n2+n)/2-1，总的交换次数是总比较次数减去n-1，它在最佳情况下为0，在最差及平均情况下为O(n2)。由此看出，在最坏情况下，插入排序法的交换次数与冒泡法、选择法一样糟糕，其执行时间和n2成正比。
D. L. Shell 发明了希尔（Shell）排序算法，该算法的基本思路是插入排序。希尔排序又称为缩小增量法，它的做法是先取定一个正整数d1 < n，把全部记录分成d1 个组，所有距离为d1倍数的记录放在一个组中，在个组内进行插入排序；然后取d2 < d1 ，重复上述分组和排序工作，直至取di = 1，即所有记录放在一个组中排序为止。大量的实验证明：当n在某个特定范围内时，希尔排序的比较次数和交换次数均为约n1.3。