数据结构0405冒泡排序课件.ppt

1、冒泡排序交换排序的基本思想两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换，直到整个序列全部满足要求为止。冒泡排序冒泡排序就是一种最简单的交换排序方法，它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录如气泡般逐渐往上“漂浮”，对应顺序表就是往左移动，或者使关键字大的记录如石块一样逐渐“下沉”，对应顺序表的右移。也正是这个原因，我们称这种排序方法为冒泡排序。例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891049 38 65 97 76 13 27 304938第一轮排序例 题设待排序记录为：49 38

2、 65 97 76 13 27 30 01234567891038 65 97 76 13 27 30493849第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 97 76 13 27 304965第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 97 76 13 27 306576第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 97 76 13 27 309776第一轮排序例

3、 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 97 13 27 309713第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 97 13 27 309713第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 13 97 27 309727第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 13 97

4、 27 309727第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 13 27 97 309730第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 13 27 97 309730第一轮排序例 题设待排序记录为：49 38 65 97 76 13 27 30 01234567891038 49 65 76 13 27 30 97第一轮排序结果冒泡排序的算法void bubble_sort(SqList&L)int m,i,j,flag=1;

5、RedType x;m=L.length-1;while(m0)&(flag=1)flag=0;for(j=1;j L.rj+1.key)flag=1;x=L.rj;L.rj=L.rj+1;L.rj+1=x;/交换 /endif m-;/endwhile 冒泡排序的算法效率最坏情况下，总的关键字比较次数KCN为KCN=n(n-1)/2n2/2记录移动次数RMN为RMCN=3n(n-1)/23n2/2RMN之所以要乘以3，是因为每次交换都要移动3次记录。所以，冒泡排序的时间复杂度为O(n2)时间复杂度方面，最好情况下，待排序记录已经有序，则只需进行一趟排序，在排序过程中进行n-1次关键词比较，并且不移动记录。冒泡排序的算法效率 空间复杂度方面，冒泡排序只有在两个记录交换时需要一个辅助空间来暂存记录，所以空间复杂度为O(1)。算法的特点（1）是稳定的排序方法（2）可用于链式存储结构（3）移动记录次数较多，算法平均时间性能较直接插入排序要差。