图

冒泡法

预备知识 Matlab 的函数

   我们先来看 Matlab 自带的排序函数 sort. 假设数列 age 是几个小朋友的年龄, name 是这几个小朋友对应的名字, 现在按年龄从小到大排序如下

1
2
3
4
5
6
7
>> age = [1, 6, 2, 5, 3];
>> name = ['a', 'b', 'c', 'd', 'e'];
>> [age1, order] = sort(x);
age1 = 1 2 3 5 6
order = 1 3 5 4 2
>> name1 = name(order);
name1 = 'acedb'
其中输出变量 order 是排序后每个数字在原来数列中的位置索引, 即 name1 等于 name(order). 现在我们用冒泡法实现 sort 的功能. sort 函数默认把数列升序排列, 即第二个输入变量默认为 'ascend'. 若要降序排列, 可以用 'descend' 作为第二个输入变量.

   冒泡法是一种简单的排序算法, 效率没有 sort 中的算法快, 所以在实际使用时还是建议用 sort. 冒泡法的算法为: 以升序排列为例, 给出一个数列, 先把第一个数与第二个进行比较, 若第一个数较大, 就置换二者的位置(具体操作是, 把第一个数的值赋给一个临时变量, 再把第二个数的值赋给第一个, 最后把临时变量的值赋给第二个), 再把第二个数与第三个进行比较, 若第二个较大, 就置换二者的位置, 这样一直进行到最后两个数, 完成第一轮. 然后再进行第二轮, 第三轮, 直到某一轮没有出现置换操作, 即可确定排序完成. 至于输出变量 order, 我们可以先令 order = 1:N, 每置换数列的两个数, 就把 order 中对应的两个数也置换即可. 这样, 数列与其原来的索引将始终一一对应.

  bubble.m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
% 冒泡法排序
function [x, order] = bubble(x, option)
N = numel(x); % 数列个数
order = 1:N; % 索引
changed = 1; % 是否有置换
while(changed == 1)
    changed = 0;
    for ii = 1:N-1
        if x(ii) > x(ii + 1)
            % 置换
            changed = 1;
            temp = x(ii);
            x(ii) = x(ii + 1);
            x(ii + 1) = temp;
            temp = order(ii);
            order(ii) = order(ii + 1);
            order(ii + 1) = temp;
        end
    end
end
% 是否是降序排列
if nargin > 1 && option(1) == 'd'
    x(:) = flipud(x(:));
    order = fliplr(order);
end
end

   第 6 行的循环每循环一次, 数列将从头到尾被扫描一遍. 每个循环开始时 changed 的值被设为 0, 若有任何置换, changed 则变为 1(第 11 行), 使 while 的判断条件成立, 循环继续. 为了使第一个循环发生, 在循环前必须把 changed 设为 1. 再来看第 9-18 行的判断结构. 如果前一个数大于后一个数, 则置换发生. 注意要置换数列中的两个数, 必须要设一个临时变量(temp). 函数的最后, 判断输入变量的个数, 如果只有一个变量, 则默认按照前面的代码升序排列, 若第二个变量为 'descend', 则把 xorder 翻转一下即可.

致读者: 小时物理百科一直以来坚持所有内容免费且不做广告,这导致我们处于日渐严重的亏损状态。长此以往很可能会最终导致我们不得不选择商业化,例如大量广告,内容付费,会员制,甚至被收购。因此,我们鼓起勇气在此请求广大读者热心捐款,使网站得以健康发展。如果看到这条信息的每位读者能慷慨捐助 10 元,我们几天内就能脱离亏损状态,并保证网站能在接下来的一整年里向所有读者继续免费提供优质内容。感谢您的支持。
—— 小时(项目创始人)

编辑词条 返回目录 返回主页 捐助项目 © 小时物理百科 保留一切权利