1.冒泡法:
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:
#include <iostream.h>
void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
for(int j=Count-1;j>=i;j--)
{
if(pData[j]<pData[j-1])
{
iTemp = pData[j-1];
pData[j-1] = pData[j];
pData[j] = iTemp;
}
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
图 示 :
before_compare|one_turn|two_turn|three_turn|four_turn|five_turn|
six_turn 10 10 10 10 10 10 4 9
9 9 9 9 4 10 8 8 8 8 4
9 9 7 7 7 4 8 8 8 6 6 4
7 7 7 7 5 4 6 6 6 6 6 4
5 5 5 5 5 5 通过上图可以看出,冒泡法形象的描述来,4 这
个元素就像一个气泡逐渐冒到上面来了。 我们排序的有 7 个元素,最坏的情况全部倒序,
4 这个元素要冒上来需要 6 次。因此,n 个元素,最坏的情况,需要移动:1+2+3+ ...+
(n-1)=1/2*n(n-1)次。倒序(最糟情况)
第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换 3 次)
第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换 2 次)
第一轮:7,8,10,9->7,8,9,10(交换 1 次)
循环次数:6 次
交换次数:6 次