关于插入排序法的实现

来源：2-2 实现插入排序法

weixin_慕仙7241916

2022-08-23 15:17:39

老师您好，想请问插入排序使用这个写法有什麽缺点吗？运行起来时间复杂度也是n^2

我的想法是从 j 往前比较，发现可插入的位置就先keep起来，最后再进行交换(其实逻辑跟SelectionSort一样)，感觉似乎与您的逻辑差不多，但不是很确定我的写法是否正确

public static <E extends Comparable<E>> void sort(E[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[minIndex].compareTo(arr[j]) < 0) {
                    minIndex = j;
                }
            }
            E t = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = t;
        }
    }

写回答

1回答

liuyubobobo

2022-08-26

已采纳

你的这个问题慕课网的通知系统没有通知到，我今天查慕课网的后台刚看到，回答完了，抱歉。

==========

你的这个算法是错误的。要想看到这个错误也很简单，对 [3, 2, 1] 这个数组的排序就是失败的。你可以运行这个 main 函数试验一下：

public static void main(String[] args) {

    Integer[] arr = {3, 2, 1};
    sort(arr);
   
    // 打印输出的结果不是 1 2 3 
    for(int e: arr) System.out.print(e + " ");
    System.out.println();
   
}

首先，插入不是简单的交换一个元素的过程。

比如在 2，3 中插入 1

2 3 1 要变成 1 2 3

请注意，2 和 3 的索引都变了，而不是只有 3 的索引变了。

请据此再理解一遍，我们写的代码：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/04-Insertion-Sort/02-Insertion-Sort/src/InsertionSort.java

12行或者 17 行，为什么是在一个循环里做 swap。

其次，你所谓的找到插入的位置也有问题。

比如 2 3 1，处理 1 的时候，插入的位置应该是把 1 插入到索引 0 的前面。但是你的代码，插入的位置（我理解是被 minIndex 存储的）是 1。

我的建议是：

基于这个[3, 2, 1]这个极小的测试用例，单步跟踪一下，看看这个代码每一步运行的时候，各个变量是怎样变化的？每个变量在每一步的变化和你的预期是否一样？如果不一样，哪里不一样？为什么会出现这个问题？是因为你头脑里的算法有问题？还是其实这个代码没有正确的把你头脑中的算法表达出来？

你可以根据我提出的这些问题，再思考一下你的代码。如果有想不明白的，或者你觉得没问题，但不明白为什么实际程序执行起来确有问题的地方，可以再提问。

继续加油！：）