经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
决胜经典算法之插入排序
来源:cnblogs  作者:萧文翰  时间:2019/9/24 11:30:36  对本文有异议

习题答案

题目回顾

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

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

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

答案

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

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?(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.?如果要实现从大到小排列,上述代码该做如何修改呢?

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

原文链接:http://www.cnblogs.com/wenhanxiao/p/11576954.html

 友情链接:直通硅谷  点职佳