3.排序
3.1冒泡排序
冒泡排序的名字来源于其工作方式，在这种排序算法中，较小的数一个一个往水面上“冒”，最终所有数均变成了由小到大排列。在冒泡排序算法中我们要对待排序的对象序列进行若干遍处理，处理的过程是：自底向上检查序列，并比较相邻对象的大小。如果发现两个相邻对象的顺序不对（较小对象在后面），就交换它们的位置。经过一遍处理之后，最小的对象就“冒”到了最前面的位置；经过第二遍处理，次小的对象又“冒”到了次前位置，依此类推。
void CSortDlg::OnBubbleSort()
{
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++)
{
for (int j = SORT_OBJECT_NUM - 1; j >= i; j--)
{
if (sortObject[objectName[j]].iNumber < sortObject[objectName[j -1]].iNumber)
{
//交换成员序号
int iTemp;
iTemp = sortObject[objectName[j - 1]].iSeq;
sortObject[objectName[j - 1]].iSeq = sortObject[objectName[j]].iSeq;
sortObject[objectName[j]].iSeq = iTemp;
//交换成员位置
iTemp = objectName[j];
objectName[j] = objectName[j - 1];
objectName[j - 1] = iTemp;
//显示新位置
CString strName;
CString strNum;
//显示j-1位置的成员
strName.Format("%d", objectName[j - 1]);
dc.TextOut(objectCoord[sortObject[objectName[j - 1]].iSeq].x - 5,
objectCoord[sortObject[objectName[j - 1]].iSeq].y - 8, strName);
if (sortObject[objectName[j - 1]].iNumber < 1000)
{
strNum.Format(" %d", sortObject[objectName[j - 1]].iNumber);
}
else
{
strNum.Format("%d", sortObject[objectName[j - 1]].iNumber);
}
dc.TextOut(objectCoord[sortObject[objectName[j - 1]].iSeq].x - 15,
objectCoord[sortObject[objectName[j - 1]].iSeq].y - 30, strNum);
//显示j位置的成员
strName.Format("%d", objectName[j]);
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);
//延迟1秒进行下一次排序以便将排序过程显示为动画
Sleep(1000);
}
}
}
} |
通过运行上述程序，我们非常清晰地看到了较小的数冒泡的全过程，这是缘于我们在每次排序之间利用Sleep(1000)插入了1秒钟的延迟。下面是我们追踪所得的一次冒泡排序的轨迹：
196 3993 2037 2953 318 2815 5770 960 7325 486
196 3993 2037 2953 318 2815 5770 960 486 7325
196 3993 2037 2953 318 2815 5770 486 960 7325
196 3993 2037 2953 318 2815 486 5770 960 7325
196 3993 2037 2953 318 486 2815 5770 960 7325
196 3993 2037 318 2953 486 2815 5770 960 7325
196 3993 318 2037 2953 486 2815 5770 960 7325
196 318 3993 2037 2953 486 2815 5770 960 7325
196 318 3993 2037 2953 486 2815 960 5770 7325
196 318 3993 2037 2953 486 960 2815 5770 7325
196 318 3993 2037 486 2953 960 2815 5770 7325
196 318 3993 486 2037 2953 960 2815 5770 7325
196 318 486 3993 2037 2953 960 2815 5770 7325
196 318 486 3993 2037 960 2953 2815 5770 7325
196 318 486 3993 960 2037 2953 2815 5770 7325
196 318 486 960 3993 2037 2953 2815 5770 7325
196 318 486 960 3993 2037 2815 2953 5770 7325
196 318 486 960 2037 3993 2815 2953 5770 7325
196 318 486 960 2037 2815 3993 2953 5770 7325
196 318 486 960 2037 2815 2953 3993 5770 7325 |
仔细的观察上述过程可以帮助我们更好地理解冒泡排序的内涵。下面的动画（GIF格式）演示了冒泡排序的过程：
 (编者注：本图为动画，请设置IE浏览器：工具－>internet->高级->多媒体，选择播放网页中的动画，即可观看，后同) |
对于n个待排序成员，冒泡排序需要进行n(n-1)/2次比较，平均情况下需进行3n(n-1)/4次交换；因为每交换一对不合顺序的元素，需进行三次操作，所以最坏情况下，交换次数是比较次数的三倍，即3n(n-1)/2 。因此，冒泡法是效率最差的排序方法，一般只适合于数组较小的情况。
因此，有学者提出了“拉锯法”、“双边冒泡法”等改进措施。“拉锯法”不再是总按同一方向读数组元素，而是这一遍从下到上把最小的送到最前面，下一遍从上到下把最大的元素送到最后面；“双边冒泡法”则每次除了冒出最小元素外，还“下沉”最大元素。
说明：本教程来源互联网或网友上传或出版商，仅为学习研究或媒体推广，wanshiok.com不保证资料的完整性。
2/2 首页 上一页 1 2 |
