排序算法：选择排序、插入排序及对象排序详解

### 排序算法：选择排序、插入排序及对象排序详解 在排序算法的世界里，有多种不同的算法可供选择，每种算法都有其独特的特点和适用场景。本文将详细介绍选择排序、插入排序以及如何对对象进行排序。 #### 选择排序 选择排序与冒泡排序的输出结果相同，例如对于数据 `77 99 44 55 22 88 11 0 66 33`，排序后都会得到 `0 11 22 33 44 55 66 77 88 99`。 在选择排序程序中，索引小于或等于 `out` 的数据项始终是有序的。 选择排序的比较次数与冒泡排序相同，为 $N*(N - 1)/2$。例如对于 10 个数据项，需要进行 45 次比较，但交换次数少于 10 次；对于 100 个数据项，需要 4950 次比较，但交换次数少于 100 次。对于较大的 $N$ 值，比较时间将占主导地位，因此选择排序的时间复杂度为 $O(N^2)$，与冒泡排序相同。不过，由于交换次数较少，选择排序无疑更快。对于较小的 $N$ 值，选择排序可能会快得多，尤其是当交换时间远大于比较时间时。 #### 插入排序 插入排序在大多数情况下是本文所描述的基本排序算法中最好的。它的时间复杂度仍然是 $O(N^2)$，但在正常情况下，它的速度大约是冒泡排序的两倍，比选择排序也稍快。虽然它比冒泡排序和选择排序稍微复杂一些，但也不算太复杂。插入排序常被用作更复杂排序算法（如快速排序）的最后阶段。 ##### 以棒球运动员为例理解插入排序 假设棒球运动员最初随机排列。为了便于理解插入排序，我们从排序过程的中间阶段开始，此时队伍已经部分有序。 在队伍中间有一个想象的标记（比如地上的一件红色 T 恤），标记左边的球员是部分有序的，即每个球员都比他左边的球员高，但他们不一定处于最终位置，因为当之前未排序的球员插入他们之间时，他们可能还需要移动。 标记所在的球员（我们称之为“标记”球员）以及她右边的所有球员尚未排序。我们要做的是将标记球员插入到（部分）有序组中的适当位置。为此，我们需要将一些已排序的球员向右移动以腾出空间。我们将标记球员从队伍中取出（在程序中，这个数据项存储在一个临时变量中）。 然后，我们将已排序的球员向右移动。最高的已排序球员移动到标记球员的位置，次高的球员移动到最高球员原来的位置，依此类推。移动过程何时停止呢？想象你和标记球员一起向左走，在每个位置，你将另一个球员向右移动，同时将标记球员与即将移动的球员进行比较。当你移动完最后一个比标记球员高的球员时，移动过程停止。最后一次移动打开了一个空间，标记球员插入这个空间后，队伍就会保持有序。 此时，部分有序组增加了一个球员，未排序组减少了一个球员。标记 T 恤向右移动一个位置，再次位于最左边未排序球员的前面。这个过程会一直重复，直到所有未排序的球员都插入到部分有序组中的适当位置。 需要注意的是，部分排序在冒泡排序和选择排序中不会发生。在这些算法中，一组数据项在任何给定时间都是完全有序的；而在插入排序中，一组数据项只是部分有序。 ##### 使用 InsertSort Workshop 小程序演示插入排序 - **排序 100 个条柱**：使用 `Size` 按钮将条柱数量更改为 100，然后点击 `Run` 按钮，你将看到条柱自动排序。短红色外箭头标记了左边部分有序条柱和右边未排序条柱之间的分界线。蓝色内箭头从外箭头开始向左移动，寻找插入标记条柱的合适位置。 - **排序 10 个条柱**：使用 `Size` 按钮切换到 10 个条柱（如有必要，使用 `New` 按钮确保它们是随机排列的）。开始时，`inner` 和 `outer` 指向从左数第二个条柱（数组索引为 1），第一条消息是 `Will copy outer to temp`，这将为移动腾出空间。点击 `Step` 按钮，`outer` 处的条柱将被复制到 `temp` 中。接下来会发生什么取决于前两个条柱是否已经有序（左边的较小）。如果有序，你将看到消息 `Have compared inner - 1 and temp, no copy necessary`；如果无序，消息是 `Have compared inner - 1 and temp, will copy inner - 1 to inner`，这是为了给 `temp` 中的值重新插入腾出空间而进行的移动。在第一次遍历中，只有一次这样的移动；在后续遍历中，可能需要更多次移动。 ##### 插入排序的 Java 代码 以下是从 `insertSort.java` 程序中提取的执行插入排序的方法： ```java public void insertionSort() { int in, out; for(out = 1; out < nElems; out++) // out 是分界线 { long temp = a[out]; // 移除标记项 in = out; // 从 out 开始移动 while(in > 0 && a[in - 1] >= temp) // 直到找到较小的项 { a[in] = a[in - 1]; // 将项向右移动 --in; // 向左移动一个位置 } a[in] = temp; // 插入标记项 } // end for } // end insertionSort() ``` 在外部 `for` 循环中，`out` 从 1 开始向右移动，它标记着最左边的未排序数据。在内部 `while` 循环中，`in` 从 `out` 开始向左移动，直到 `temp` 小于数组元素，或者不能再向左移动为止。每次通过 `while` 循环，都会将另一个已排序元素向右移动一个位置。 以下是完整的 `insertSort.java` 程序： ```java // insertSort.java // demonstrates insertion sort // to run this program: C>java InsertSortApp //-------------------------------------------------------------- class ArrayIns { private long[] a; // ref to array a private int nElems; // number of data items //-------------------------------------------------------------- public ArrayIns(int max) // constructor { a = new long[max]; // create the array nElems = 0; // no items yet } //-------------------------------------------------------------- public void insert(long value) // put element into array { a[nElems] = value; // insert it nElems++; // increment size } //-------------------------------------------------------------- public void display() // displays array contents { for(int j = 0; j < nElems; j++) // for each element, System.out.print(a[j] + " "); // display it System.out.println(""); } //-------------------------------------------------------------- public void insertionSort() { int in, out; for(out = 1; out < nElems; out++) // out is dividing line { long temp = a[out]; // remove marked item in = out; // start shifts at out while(in > 0 && a[in - 1] >= temp) // until one is smaller, ```