3.3
选择排序
由前文可知，交换排序的特点是每次用当前的对象一一与其后对象比较并交换。选择排序与交换排序类似，但是它并不是用当前对象与其后对象一一比较，而是直接以当前对象以后的最小对象与当前对象比较并交换，因而可以提高算法的时间性能。
void CSortDlg::OnSelectionSort()
{
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=0;i<SORT_OBJECT_NUM;i++)
{
int iPos;
iPos = i;
for(int j=i+1;j<SORT_OBJECT_NUM;j++)
{
if(sortObject[objectName[j]].iNumber <
sortObject[objectName[iPos]].iNumber)
{
iPos = j;
}
}
if(iPos!=i)
{
//
交换序号
int iTemp;
iTemp = sortObject[objectName[iPos]].iSeq;
sortObject[objectName[iPos]].iSeq =
sortObject[objectName[i]].iSeq;
sortObject[objectName[i]].iSeq = iTemp;
//
交换成员名
iTemp = objectName[iPos];
objectName[iPos] = objectName[i];
objectName[i] = iTemp;
//
显示变化
CString strName;
CString strNum;
//
对象
iPos
strName.Format("%d",sortObject[objectName[iPos]].iName);
dc.TextOut(objectCoord[sortObject[objectName[iPos]].iSeq].x-5,
objectCoord[sortObject[objectName[iPos]].iSeq].y-8,
strName);
if(sortObject[objectName[iPos]].iNumber<1000)
{
strNum.Format(" %d",
sortObject[objectName[iPos]].iNumber);
}
else
{
strNum.Format("%d",sortObject[objectName[iPos]].iNumber);
}
dc.TextOut(objectCoord[sortObject[objectName[iPos]].iSeq].x-15,
objectCoord[sortObject[objectName[iPos]].iSeq].y-30,
strNum);
//
对象
i
strName.Format("%d",sortObject[objectName[i]].iName);
dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-5,
objectCoord[sortObject[objectName[i]].iSeq].y-8,
strName);
if(sortObject[objectName[i]].iNumber<1000)
{
strNum.Format(" %d",sortObject[objectName[i]].iNumber);
}
else
{
strNum.Format("%d",sortObject[objectName[i]].iNumber);
}
dc.TextOut(objectCoord[sortObject[objectName[i]].iSeq].x-15,
objectCoord[sortObject[objectName[i]].iSeq].y-30,
strNum);
//
延迟
1
秒进行下一次排序以便将排序过程显示为动画
Sleep(1000);
}
}
}
下面是我们追踪所得的一次选择排序的轨迹：
5919 280 1617 4375 332 1467 158 9599 342 496
158 280 1617 4375 332 1467 5919 9599 342 496
158 280 332 4375 1617 1467 5919 9599 342 496
158 280 332 342 1617 1467 5919 9599 4375 496
158 280 332 342 496 1467 5919 9599 4375 1617
158 280 332 342 496 1467 1617 9599 4375 5919
158 280 332 342 496 1467 1617 4375 9599 5919
158 280 332 342 496 1467 1617 4375 5919 9599
下面的动画（
GIF
格式）演示了选择排序的过程：
选择排序法总的比较次数是n(n-1)/2次，但其交换次数有所减少。最坏情况下的交换次数接近于比较次数，为〔n2/ 4+3(n-1)〕；平均情况下交换次数为〔n*ln(n+u)〕，其中u 是尤拉常数，约为0. 577216。
本文转自 21cnbao 51CTO博客，原文链接：http://blog.51cto.com/21cnbao/120742，如需转载请自行联系原作者
