-3 
package com.sort;

public class ArraySel {

    private Long[] a;
    private int nElems;

    public ArraySel(int max)
    {
        a = new Long[max];
        nElems = 0;
    }

    public void insert(long max)
    {
        a[nElems] = max;
        nElems++;
    }

    public void display()
    {
        for(int j = 0; j < nElems; j++)
        {
            System.out.print(a[j]+ "  ");
        }
        System.out.println();
    }

    public void insertionSort()
    {
        int in , out, flag = 0;
        long temp;
        for(out = 1; out < nElems; out++)
        {
            temp = a[out];
            in = out;
            while(in > 0 && a[in - 1] >= temp )
            {
                if(a[in] == a[in - 1 ])
                {
                    flag++;
                    in--;
                }
                else
                {
                    a[in] = a[in-1];
                    in--;
                }
            }
            a[in] = temp;
        }
    }

}

此代码采用未排序的数组并使用插入排序对其进行排序。当重复项以未排序的数组排列在一起时，由于多次移位的复杂性提高到O(N^2)，我试图O(N)通过确保在重复项排列在一起的情况下没有项目移动超过一次来做到这一点。

但是，当重复项没有排列在一起时，复杂性仍然存在O(N^2)。O(N)在这种情况下我们也可以使复杂性变得更复杂吗？

4

2 回答 2

2

复杂性不是由移动的数量给出的，而是由整体操作的数量给出的，在这种情况下也是比较的。

插入排序是 O(n^2) 平均复杂度，你不能让它比这更快。在 O(n) 中仅在最佳情况下工作，当输入字符串已经排序时（http://en.wikipedia.org/wiki/Insertion_sort）。

于 2014-06-23T09:48:45.240 回答
1

如果没有有关基础数据的更多信息，您可以使用排序算法实现的最佳 时间复杂度O(n log n)是（n是元素的数量）。

O(n²)诸如插入排序、冒泡排序、选择排序等排序算法，由于它们的双循环，都具有时间复杂度。事实上，当获得已经排序的元素列表时，它们有时往往会更好地工作。例如，插入排序O(n)对于完全排序的列表具有时间复杂度。

您无法改变这些算法的固有时间复杂度。您唯一能做的就是在输入列表中查找预排序区域时缩短算法。

于 2014-06-23T09:53:43.307 回答