(a) (i) 描述当冒泡排序用于将 $n$ 个数字的列表按升序排序时，如何执行第一次传递。

(ii) 写出冒泡排序停止的情况。

从列表左端开始的冒泡排序用于将十个数字的列表按升序排序。经过多次传递后，列表为：

$0.9 \quad 1.2 \quad 1.5 \quad 0.5 \quad 1.4 \quad 1.1 \quad 0.7 \quad 1.7 \quad 2.2 \quad 3.2$

(b) 确定此列表上可能已进行的最大传递次数。必须给出理由。

(c) 完成冒泡排序以产生升序的数字列表。只需给出每次完整传递结束后的列表状态。

(d) 使用首次适应递减装箱算法确定上面列出的十个数字如何装入大小为 4 的箱子中。

第一次传递从列表左端开始，逐对比较相邻数字。若左边数字较大就交换；每次比较后向右移动一位，直到比较完最后一对。

Compare the first value with the second value and swap them if the first value is larger.

Then compare the value now in the second position with the value in the third position, again swapping them if they are in the wrong order. Continue comparing successive adjacent pairs in this way until the end of the list is reached.

冒泡排序在某次完整传递没有发生任何交换时停止，因为此时列表已经有序；若尚未提前停止，排到只剩一个元素无需再比较时也会停止，即最多进行 $n-1$ 次传递。

A bubble sort stops when either

• a complete pass is made with no swaps, or
• only one item remains to be sorted, after at most $n-1$ passes.

从左端开始进行升序冒泡排序时，每完成一趟，尚未排定部分的最大数就会移动到最右端的正确位置。当前列表末尾恰有三个最大的数 $1.7,2.2,3.2$ 已按正确次序处于最终位置，所以此前至多完成了三趟。

After each pass, the largest remaining value is placed in its final position at the right-hand end of the list.

Only the three largest values, $1.7$, $2.2$ and $3.2$, are in their final positions. Therefore the maximum possible number of passes already completed is

从题给状态继续由左向右逐对比较。每趟只记录完整传递后的列表；第五趟得到升序列表后，还要进行第六趟并确认没有交换，才能按冒泡排序的停止条件结束。

The states after successive complete passes are:

Hence the sorted list is

先将数字按递减顺序排列，再依次把每个数字放进第一个仍容得下它的箱子。每次都必须从第一个箱子重新检查，不能直接放进当前最空的箱子。

First arrange the values in decreasing order:

Applying first-fit in this order gives:

Thus the items are packed into