习题答案
题目回顾
在上一篇文章中,我们以数列从小到大排列为例,讲了选择排序。结尾处的思考题如下:
如果要实现从大到小排列,上述代码该做如何修改呢?
同样,要解答这个问题也很简单,下面放上答案。
答案
我们知道,从小到大排序时,选择排序就是选出最小的数,并将其放在最开始的位置。同理,从大到小排序时,只需要选出最大的数,将其放在最开始的位置就可以了。参考如下代码:
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个数字,请将其从小到大依次排列。
算法解析
所谓“插入排序”,重点在“插入”。具体说来,就是评估数列里面的每一个元素。这种评估依次进行,数列中,如果它前面的数值比它小(从小到大排序时),则把它放在比它小的数值后,直到最后一个元素评估完成。
整个过程理解起来并不难,结合下面的动图演示将会更加清晰直接。
详细步骤
下面让我们来分步骤拆解整个插入排序:
- 从第一个元素开始,该元素可以认为已经被排序;
- 取出下一个元素,在已经排序的元素序列中从后向前扫描;
- 如果该元素(已排序)大于新元素,将该元素移到下一位置;
- 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
- 将新元素插入到该位置后;重复步骤2~5,直到最后一个元素完成。
整个流程如下图所示:
伪代码
接下来,我们使用伪代码实现上述过程
InsertSort?(input?ele[],input?length)
for?i <-- 1 to n-1
????for?j <-- i-1 to 0
????if?a[i] > a[j]?break
if?j!=i-1
temp <-- a[i]
for?k <-- i to j+2
????a[k] <-- a[k-1]
a[j+1] <-- temp
end
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.?如果要实现从大到小排列,上述代码该做如何修改呢?
思考题答案依旧会在下篇连载中公布,大家加油哦!