从趣味游戏到排序算法(3)
本文共 2874 字，大约阅读时间需要 9 分钟。
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)，其比较次数与下文要介绍的选择排序相同，但是其交换次数比选择排序大，因此不推荐使用这种排序算法。
本文转自 21cnbao 51CTO博客，原文链接：http://blog.51cto.com/21cnbao/120744，如需转载请自行联系原作者
你可能感兴趣的文章
IIIDX[九省联考2018]
查看>>
Protobuf3 序列化
查看>>
C语言面试题大汇总
查看>>
JavaSE-List常用方法
查看>>
json 和 pickel 详解
查看>>
Linux基础命令之grep
查看>>
python自动化开发-7
查看>>
使用VS2010+SVN出現的問題
查看>>
谁说Javascript简单的？
查看>>
UVA 1374 Power Calculus
查看>>
表结构更改后或新增加数据后同步到表中
查看>>
软媒魔方u盘装系统
查看>>
python中的文件操作小结1
查看>>
ggplot2 geom设置—散点图
查看>>
inotify+rsync 实时同步目录文件
查看>>
eclipse中debug
查看>>
山寨百度之学习笔记
查看>>
maven入门与常用插件使用
查看>>
我是一只IT小小鸟
查看>>
【转载】Windows平台分布式架构实践 - 负载均衡
查看>>