| |
用Visual C++实现排序算法大全 |
|
时间: 2005-11-17 来自：天极网 |
 |
|
3.2交换排序
交换排序的基本思想是对待排序的对象序列进行n-1遍处理，第i遍处理的过程为：将对象i~对象n-1与对象i-1进行比较，若其较小，则与i-1对象交换位置；经过i遍处理之后，前i个对象就是顺序排列的了。
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++)
{
for(int j=i+1;j<SORT_OBJECT_NUM;j++)
{
if(sortObject[objectName[j]].iNumber
<sortObject[objectName[i]].iNumber)
{
//交换成员序号
int iTemp;
iTemp =
sortObject[objectName[j]].iSeq;
sortObject[objectName[j]].iSeq
=sortObject[objectName[i]].iSeq;
sortObject[objectName[i]].iSeq =
iTemp;
//交换成员位置
iTemp =
objectName[j];
objectName[j] = objectName[i];
objectName[i]
= iTemp;
//显示新位置
CString strName;
CString
strNum;
//显示j位置的成员
strName.Format("%d",sortObject[objectName[j]].iName);
dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x-5,
objectCoord[sortObject[objectName[j]].iSeq].y-8,strName);
if(sortObject[objectName[j]].iNumber<1000)
{
strNum.Format("
%d",sortObject[objectName[j]].iNumber);
}
else
{
strNum.Format("%d",sortObject[objectName[j]].iNumber);
}
dc.TextOut(objectCoord[sortObject[objectName[j]].iSeq].x-15,
objectCoord[sortObject[objectName[j]].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);
}
}
}
} |
下面是我们追踪所得的一次交换排序的轨迹：
7449 318 964 396 4973 1431 6541 2331 1489 3743
318 7449 964 396
4973 1431 6541 2331 1489 3743
318 964 7449 396 4973 1431 6541 2331
1489 3743
318 396 7449 964 4973 1431 6541 2331 1489 3743
318 396
964 7449 4973 1431 6541 2331 1489 3743
318 396 964 4973 7449 1431 6541
2331 1489 3743
318 396 964 1431 7449 4973 6541 2331 1489 3743
318
396 964 1431 4973 7449 6541 2331 1489 3743
318 396 964 1431 2331 7449
6541 4973 1489 3743
318 396 964 1431 1489 7449 6541 4973 2331 3743
318 396 964 1431 1489 6541 7449 4973 2331 3743
318 396 964 1431
1489 4973 7449 6541 2331 3743
318 396 964 1431 1489 2331 7449 6541
4973 3743
318 396 964 1431 1489 2331 6541 7449 4973 3743
318 396
964 1431 1489 2331 4973 7449 6541 3743
318 396 964 1431 1489 2331 3743
7449 6541 4973
318 396 964 1431 1489 2331 3743 6541 7449 4973
318
396 964 1431 1489 2331 3743 4973 7449 6541
318 396 964 1431 1489 2331
3743 4973 6541
7449 |
下面的动画（GIF格式）演示了交换排序的过程：
交换排序的时间复杂度为O(n2)，其比较次数与下文要介绍的选择排序相同，但是其交换次数比选择排序大，因此不推荐使用这种排序算法。
|
|
|
|
|
|
|
|
