9

我很难理解为什么在 o(n) 中插入排序的最佳情况？

     for (int i = 0; i < size; i++) {

                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }

                }
     }

让我们考虑一个示例初始数组 [1,2,3,4,5] size = 5 第一个循环将从 i = 0 变为 size - 1，第二个循环将从 i 变为 1 但假设，内部 for 循环也可以从 0 到 size - 1 换句话说，内部 for 循环也执行 (n-1) 次，类似于外部 for 循环我同意不会有交换，但会有比较，并且它将与未排序的数组完全相等？然后 n-1 (外循环) * n - 1(内循环) = n^2 - n + 1 = O(n^2)
谁能解释我哪里错了？

4

6 回答 6

7

起初，这似乎不是插入排序的正确代码。您似乎正在以相反的方式使用冒泡排序代码。
在插入排序代码中，您不会用落在它之前的每个大元素替换一个小元素，而是我们略过落在它之前的所有大元素，并且只有当我们处于没有任何元素的地方或那里时不再是大元素，然后我们将小元素放在那个地方并移动/移动所有其他后续元素。

作为 O(n) 时间的一部分：
让我们考虑一个包含五个已排序元素的数组 - arr[11,13,15,17,19]。我们从第一个位置元素移动到最后一个位置。
第 1 步：取元素 11，因为它是第一个元素，我们保持原样。
Step 2:取元素 13, 寻找在它之前的元素(即元素 11), 因为 13>11, 因此不需要再寻找落在 11 之前的元素。
Step 3:取元素 15, 寻找元素落在它之前（即元素 13），因为 15>13，因此不再需要查看落在 13 之前的元素。
步骤 4：取元素 17，寻找落在它之前的元素（即元素 15），如17>15，因此不再需要查看 15 之前的元素。
步骤5：取元素19，寻找落在它之前的元素（即元素17），因为19>17，因此不再需要寻找落在17之前的元素。

正如我们看到的，对于五个已经排序的元素，我们只需要 5 次比较，因此对于“n”个排序的元素，我们只需要 O(n) 次比较。

我希望上面的例子能澄清你的疑问。

于 2015-06-11T06:46:40.893 回答
5

您的代码始终在 O(n^2) 中运行。当你找到元素应该在的位置时，你必须打破内部 for 循环。

于 2013-01-19T14:19:15.190 回答
2

考虑以下插入排序的实现：

    for (i=1; i<n; i++) {
        j=i;
        while ((j>0) && (s[j] < s[j-1])) {
            swap(&s[j],&s[j-1]);
            j = j-1;
        }
    }

任何排序算法的最佳情况是输入已经排序。在这种情况下，while 循环的条件总是返回 false，因此它只迭代外部 for 循环，以 O(n) 时间复杂度在线性时间内完成这项工作。

于 2015-08-31T00:16:18.973 回答
1

这是实现插入排序的一种方法。

获取一个输入列表和一个最初为空的输出列表。

遍历输入列表并将每个项目放置在输出列表上的适当位置。从第一个元素开始遍历输出列表，找到合适的位置。

现在，如果您的输入已经排序，那么插入点将始终位于输出列表的开头或结尾。第一种可能性对应于最好的情况；第二个对应于最坏的情况。

例如，我的输入数据是：4 3 2 1。

然后输出列表构建为：

4
3 4
2 3 4
1 2 3 4

由于查看第一个元素只需要 O(1)，因此时间复杂度在于输入的大小或 O(N)。

于 2013-01-19T14:17:35.860 回答
0

当数组已经排序时，插入排序的最佳情况是O(n) 。

但是您的算法仍将 O(n^2) 用于排序情况。因此，仅当条件失败时，您才应该进入第二个循环。这样，在排序列表的情况下，您将永远不会进入内部循环。

检查以下链接：http ://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/insertionSort.htm

http://en.wikipedia.org/wiki/Insertion_sort

于 2013-01-19T14:28:32.917 回答
0

更改您的方法以具有此中断条件，您将获得最佳案例复杂度为 O(n)。

    void insertionSort0(List<Integer> list)
{
    int loop=0;
    for(int i=1;i<list.size();i++)
    {
        int target=(Integer)list.get(i);
        int pos=0;

        for(int j=i-1;j>=0;j--)
        {
            loop++;
            if((Integer)list.get(j)>target)
            {
                list.set(j+1, (Integer)list.get(j));
                pos=j;
            }
            else
            {
                break;
            }


        }


            list.set(pos, target);

    }
    System.out.println("loop in for insertion sort" +loop);
}
于 2015-06-27T06:41:28.303 回答