冒泡法

                     

贡献者： 待更新

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

>> 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。冒泡法的算法为：以升序排列为例，给出一个数列，先把第一个数与第二个进行比较，若第一个数较大，就置换二者的位置（具体操作是，把第一个数的值赋给一个临时变量，再把第二个数的值赋给第一个，最后把临时变量的值赋给第二个），再把第二个数与第三个进行比较，若第二个较大，就置换二者的位置，这样一直进行到最后两个数，完成第一轮。然后再进行第二轮，第三轮，直到某一轮没有出现置换操作，即可确定排序完成。至于输出变量 order，我们可以先令 order = 1:N，每置换数列的两个数，就把 order 中对应的两个数也置换即可。这样，数列与其原来的索引将始终一一对应。

% 冒泡法排序
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'，则把 x 和 order 翻转一下即可。