习题答案

题目回顾

在上一篇文章中，我们以数列从小到大排列为例，讲了选择排序。结尾处的思考题如下：

如果要实现从大到小排列，上述代码该做如何修改呢？

同样，要解答这个问题也很简单，下面放上答案。

答案

我们知道，从小到大排序时，选择排序就是选出最小的数，并将其放在最开始的位置。同理，从大到小排序时，只需要选出最大的数，将其放在最开始的位置就可以了。参考如下代码：

public static void selectSort(int[] arr) {    for (int i = 0; i < arr.length; i++) {        int min = i;        for (int j = i; j < arr.length; j++) {            if (arr[j] > arr[min]) {                min = j;            }        }                if (min != i) {            int temp = arr[i];            arr[i] = arr[min];            arr[min] = temp;        }    }}

怎么样，你答对了吗？

---

本篇文章的内容是讲第三种排序方法——插入排序。
还是之前的问题：

问题挑战

现有如下数字：
3，44，38，5，47，15，36，26，27，2，46，4，19，50，48
一共15个数字，请将其从小到大依次排列。

算法解析

所谓“插入排序”，重点在“插入”。具体说来，就是评估数列里面的每一个元素。这种评估依次进行，数列中，如果它前面的数值比它小（从小到大排序时），则把它放在比它小的数值后，直到最后一个元素评估完成。
整个过程理解起来并不难，结合下面的动图演示将会更加清晰直接。

详细步骤

下面让我们来分步骤拆解整个插入排序：

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置后；重复步骤2~5，直到最后一个元素完成。

整个流程如下图所示：

伪代码

接下来，我们使用伪代码实现上述过程

InsertSort(inputele[],inputlength)fori <-- 1 to n-1forj <-- i-1 to 0ifa[i] > a[j]breakifj!=i-1temp <-- a[i]fork <-- i to j+2a[k] <-- a[k-1]a[j+1] <-- tempend

Java代码实现

接下来，我们使用Java编程语言实现上述算法。

public static void insertSort(int[] arr) {    int temp;    int j;    for (int i = 1; i < arr.length; i++) {        for (j = i - 1; j >= 0; j--) {            if (arr[i] > arr[j])            break;        }        if (j != i - 1) {            temp = arr[i];            for (int k = i; k > j + 1; k--) {                arr[k] = arr[k - 1];            }            arr[j + 1] = temp;        }    }}

思考题

1.如果要实现从大到小排列，上述代码该做如何修改呢？

思考题答案依旧会在下篇连载中公布，大家加油哦！