插入排序算法

Question

我对数据结构和算法很陌生。我刚刚实现了一个插入排序算法。我只想确定我的代码是否正常。

import java.util.Arrays;

public class Main {

    public static void main(String[] args) {

        int[] test = {40, 1, 5, 0, 9};

        for (int i = 0; i < test.length; i++) {

            for (int j = i - 1; j >= 0; j--) {

                if (test[i] < test[j]) {
                    //swap if i is smaller than j .
                    int temp = test[j];
                    test[j] = test[i];
                    test[i] = temp;

                        /*we swap the j's value with i.we also have to check the other left items
                        so we have to make i at the index where we just swapped.*/

                    i = j;

                }
            }
        }
        System.out.println(Arrays.toString(test));


    }
}

Answer 1

是插入排序

吗？

总之，没有。但在更长的时间内，它显然与插入排序有关，但仍然没有。

该算法与基于交换的插入排序所做的交换序列相同(还有一个基于移动的插入排序版本，在实践中效率更高)。就这样，案子结了？实际上不是，因为这个算法总是重置外循环的循环变量，这是一种通常不是插入排序的一部分的行为，它以一种基本的方式改变了它。

就交换的数量而言，这个算法(据我所知)仍然在最坏的情况下使O(n平方)交换。但我认为它可以进行O(N)比较，这比插入排序要糟糕得多。

非正式地:让我们假设最坏的情况，每一个下一项都是在数组的排序部分开始时插入的。因此，每次插入后，i被重置为零。重新运行算法，从零到刚刚停止进行O(n平方)比较(但是零交换，因为它正在运行的元素已经排序)，而且由于这发生了n次，所以总共是O(N)比较。(为了更恰当地说，我应该说从i=0到i=n的I平方之和是O(N)中包含的n的函数，但“非正式的”.)

通过

工作吗？

是的，但效率很低。

什么会使其插入排序

如果不是更改i，而是比较和交换j和j+1的位置，内环将做与现在相同的事情，但不会重置i。这将使其成为使用插入作为其策略的O(n平方)算法，因此IMO将限定为插入排序。通常，当比较为假时，插入排序被描述为具有内循环停止，但我不认为继续会使其不-插入排序，这只会使插入排序的实现效率低下。