冒泡法

閱讀原文

預備知識　Matlab 的函數

　　 我們先來看 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 6order = 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

0001 % 冒泡法排序0002 function [x, order] = bubble(x, option)0003 N = numel(x); % 數列個數0004 order = 1:N; % 索引0005 changed = 1; % 是否有置換0006 while(changed == 1)0007 changed = 0;0008 for ii = 1:N-10009 if x(ii) > x(ii + 1)0010 % 置換0011 changed = 1;0012 temp = x(ii);0013 x(ii) = x(ii + 1);0014 x(ii + 1) = temp;0015 temp = order(ii);0016 order(ii) = order(ii + 1);0017 order(ii + 1) = temp;0018 end0019 end0020 end0021 % 是否是降序排列0022 if nargin > 1 && option(1) == d0023 x(:) = flipud(x(:));0024 order = fliplr(order);0025 end0026 end

（剩下部分見頂部的「閱讀原文」）

推薦閱讀：