10.3 排序
10.3.1 冒泡排序
10.3.2 MATLAB的排序
数组的一个标准应用是将一列数字按升序排序。虽然MATLAB有自己的排序函数(sort)，但您可能对排序算法的实际工作方式感兴趣。
10.3.1 冒泡排序
基本思想是将未排序列表赋值给一个向量。然后通过一个过程对这些数字进行排序，这个过程实际上是多次遍历向量，交换顺序错误的连续元素，直到所有元素都处于正确的顺序. 这样的过程被称为冒泡排序，因为较小的数字会上升到列表的顶部，就像空气在水中的气泡。还有许多其他的排序方法，如快速排序，可以在大多数计算机科学教科书中找到。这些通常比冒泡排序更有效，但冒泡排序的优点是它是迄今为止最容易编程的方法。冒泡排序的结构方案如下:
冒泡排序是一种通过多次遍历数组，两两比较并交换顺序的排序算法。
冒泡排序的基本思想是通过多次遍历列表，通过交换相邻元素的位置来将较大（或较小）的元素逐渐"冒泡"到列表的顶部（或底部），即正确的顺序位置。
在冒泡排序的每一次循环中，会比较相邻的两个元素，如果它们的顺序不正确（比如j位置的元素大于j+1位置的元素），则交换它们的位置。在每一次循环的末尾，最大（或最小）的元素就会"冒泡"到正确的位置。通过多次循环，列表中的所有元素最终都会按照正确的顺序排列。
需要注意的是，冒泡排序可能不是最高效的排序算法，因为它的时间复杂度是，对于大型数据集可能会较慢。相比之下，一些其他排序算法（如快速排序）可能更为高效。但冒泡排序的优点是它的实现相对简单，易于理解和编写。
作为示例，考虑一个由五个数字组成的列表：27、13、9、5和3。这些数字最初被输入到向量 X 中。下表显示了这个问题中 MATLAB 的部分内存情况。
每一列都显示了每次循环时列表的情况。在每次循环中，变量发生变化的行上有一条竖线标记。表中还显示了每次循环中的比较次数。
对比排序算法的优劣可以通过计算它们进行的比较次数（或测试次数）进行比较，因为这是排序过程中占据大部分执行时间的操作。在冒泡排序的第 轮中，恰好进行 次比较，因此总的比较次数为
对于较大的 ，总的比较次数约为 。对于一个包含五个数字的列表，总共需要进行10次比较；但对于十个数字的列表，总共需要进行45次比较。所需的计算时间与列表长度的平方成正比。
下面的 bubble.m 函数与上面的结构计划略有不同，即使在最后一轮之前列表已经排序，它也会进行 N-1 轮。由于大多数实际列表都是部分排序的，因此在每次循环后检查是否进行了任何交换是有意义的。如果没有进行交换，那么列表就已经排序好了，因此可以消除不必要的（从而浪费时间的）比较。在这个函数中，sorted 变量被用来检测列表是否已经排序好，外部循环使用非确定性的 while 循环编码。函数代码如下：
function y = bubble(x)
n = length(x);
sorted = 0; % 用于检测是否已排序
k = 0; % 计算循环次数
while ~sorted
sorted = 1; % 假设列表已排序
k = k + 1; % 增加一次循环次数
for j = 1 : n - k % 每次循环减少比较次数
if x(j) > x(j + 1) % 是否按顺序
temp = x(j); % 交换位置
x(j) = x(j + 1);
x(j + 1) = temp;
sorted = 0; % 发生交换
end
end
end
y = x;
您可以在命令行上使用该函数对包含20个随机数的列表进行排序，如下所示：
r = rand(1, 20);
r = bubble(r);
注意，bubble 函数改变了输入向量。
% 定义输入列表
x = rand(1, 400);
% 开始计时
tic;
% 调用 bubble 函数进行排序
y = bubble(x);
% 结束计时并打印所需时间
elapsedTime = toc;
disp(['函数运行所需时间：', num2str(elapsedTime), ' 秒']);
函数运行所需时间：0.0022022 秒
10.3.2 MATLAB的排序
MATLAB的内置函数sort返回两个输出参数：排序后的列表（按升序排列）和一个包含排序使用的索引的向量，即原始列表中排序后数字的位置。例如，如果使用以下命令对随机数r进行排序：
r = rand(1,5);
[y, i] = sort(r)
则输出变量如下：
y =
0.03 0.23 0.65 0.94 0.98
i =
2.00 3.00 1.00 5.00 4.00
例如，数字（0.23）的索引是3，即在原始未排序列表r中的下标。
实际上，内置函数max和min也返回第二个输出变量，即索引。
MATLAB的sort函数非常快。我的电脑排序一百万个随机数只需要2.36秒！这是因为（a）它使用了快速排序算法，以及（b）该函数已经编译为内置函数，这使得代码更加快速。
