pascal 冒泡法讲解
发表在 深坑帝国 10-15 14:14:10
1
1792
0
冒泡排序，就像将数据比作泡泡，轻的上浮，重的下沉。在第i次排序中，有n-i次将相邻的数据比较，若符合条件则交换。每一趟交换都会产生至少一个有序数据。
- 中文名
- 冒泡排序
- 外文名
- bubble sort
- 时间复杂度
- O(n^2)
- 空间复杂度
- O(n)
思想
对1至n个
，在第i趟排序中设置
flag:=true，未排序的标志。从下往上
，以j作为内层循环变量，共做n-i次比较。在第j趟比较中，若r[j+1]
算法
当数据已经从小到大排好序时，此算法只执行一趟冒泡，做n-1次数据
，不移动对象，这是最好的情形。
最坏的情形是算法执行n-1趟冒泡，第i趟做n-i次比较，进行n-i次交换。这样在最坏情形下总的数据比较次数
和对象移动次数RMN为：
该排序的
较好。
但也可以通过删减把冒泡程序改成不稳定程序。
该程序内容简短，时间与功效不如简单排序的另外两种——
和
，适合初学者使用。
代码
此为从小到大排序的程序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | i，j：循环变量flag：状态指针n：数据数量r：排序数据（数组）temp：交换变量for i:=1 to n-1 do//最多做n－1趟排序 begin flag:=true;//至未排序的标志 for j:=n-1 downto i do//从底部向上扫描 if r[j+1]<r[j] then//交换元素 begin temp:=r[j+1]; r[j+1]:=r[j]; r[j]:=temp; flag:=false; end; if flag then break;//本趟排序中未发生交换，则终止 end; |
登录或注册后发布评论
