排序算法大荟萃——冒泡排序算法
1、基本思想：将无序数组R垂直排列，从下往上扫描数组R，对比相邻的两个元素，如果上面的元素值小于下面的值，则调整这两个相邻元素的位置，然后继续向上扫描，直到排好序为止。2、排序过程：
（1）初始化：读取无序数组R
（2）第一趟扫描：从数组R底部开始向上扫描，依次比较相邻的两个元素，若发现数值较小的在上面，则交换两个元素的位置。即依次比较（R、R）、（R、R）、。。。、（R、R），对于每对元素（R、R），若R.key < R.key，则交换R和R的内容。
第一趟扫描完毕，关键字最小的元素在第一个位置R。
（3）第二趟扫描：扫描R，扫描完毕时，关键字次小的元素在第二个位置R
最后，经过n-1趟扫描可得到有序数组R
注：若发现某趟扫描中，没有元素进行位置交换，说明所有元素处于有序状态，该趟扫描结束后可以停止排序。因此，可以引入一个布尔量exchange，每趟扫描前，将exchange置为false，如果排序过程（即扫描过程）发生了元素交换，则将exchange置为true，每趟扫描结束后检查exchange，若exchange为false，则终止算法，不再进行下一趟排序。
3、代码如下：
void BubbleSort(SeqList R)
{
int i,j;
Boolean exchange;
for(int i = 1; i < n; i++)
{
exchange=false;
for(j=n-1;j >= i; j--)
{
if(R.key < R.key)
{
R=R;
R=R;
R=R;
exchange=TRUE;
}
if(!exchange)
return;
}
}
}
冒泡排序是稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，平均时间复杂度为O(n^2)，空间复杂度为O(1)。
摘至程序员面试宝典，侵权必删。
页:
[1]