java - 这种排序的实现是否考虑插入排序？

Question

这种插​​入实现是否被认为是正确的？这与我见过的其他一些例子有点不同。

public static int[] insertionSort(int[] numbers) {
    for (int i = 1; i < numbers.length; i++) {
        int index = i;
        for (int j = i-1; j >= 0 ; j--) {
            if (numbers[index] < numbers[j]) {
                int temp = numbers[index];
                numbers[index] = numbers[j];
                numbers[j] = temp;
                index--;
            }
        }

    }


    return numbers; 

}

Answer 1

你的逻辑是对的，它应该有效，基本上它是插入排序，你是对的。但是，您的算法将在当前实现中进行不必要的迭代。

即使我们已经找到了插入的位置，内部循环也会遍历 i 左侧的所有值。结果，您的 index 值将指向正确的位置，但循环会进一步进行，但 if 条件直到下一个 才会满足我值。

要解决此问题，您只需添加下一个即可:

else {
  break;
}

它应该完成内部循环并转到外部循环的下一个值。不过，最好将内循环替换为 while，以使代码更具可读性。

至于复杂度，即使对于排序数组，您当前的代码也将以 O(n^2) 复杂度工作。通过这样的增强，它的平均运行时间仍然是 O(n^2)，但在最好的情况下，它将提高到 O(n)。