|
|
|
若设R[1…n]为待排序的n个记录，且假设为从上至下纵向排列，则要求将n个给定记录由小到大排序的冒泡排序（Bubble Sort）的基本思路如下。
|
|
|
|
（1）对当前还未排好序的、指定范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让关键字较大的结点往下沉，关键字较小的结点往上冒。即若R[j].key>R[j+1].keg，则将R[j].key与R[j+1].key交换。
|
|
|
|
（2）初始化时，排序范围是R[1…n]，以后的排序范围由前一遍的扫描结果确定：当自上而下将当前排序范围内的结点执行一遍比较之后，若最后往下沉的结点是R[j]，R[j]下沉到R[j+1]的位置，R[j+1]以下的结点比较后会发现它们都不再需要交换。因此，下一趟的排列范围可以缩减为从R[1]到R[j]。
|
|
|
|
（3）整个排列过程最多执行n-1趟。若某一趟的比较没有结点交换，所有相邻结点的排列顺序都与排序要求一致，则线性表为有序的。
|
|
|
|
|
|
|
|
可见，对n个结点的线性表采用冒泡排序，外循环最多执行n-1趟，每一趟最多执行n-1次比较；第2趟最多执行n-2次比较；依次类推，第n-1趟最多执行1次比较。因此，整个排序过程最多执行n(n-1)/2次比较。由于关键字相等的结点不交换，所以冒泡排序算法是稳定的。
|
|
|
