标签: insertion-sort

我正在研究书中的渐近符号，但我无法理解作者的意思。我知道if f(n) = \xce\x98(n^2) then f(n) = O(n^2)。然而，我从作者的话中了解到，对于插入排序函数算法f(n) = \xce\x98(n)和f(n)=O(n^2).

为什么？大欧米茄或大西塔会随着不同的输入而改变吗？

他说：

\n

然而，插入排序最坏情况运行时间上的 \xce\x98(n^2) 界限并不意味着每个输入上插入排序的运行时间上都有 \xce\x98(n^2) 界限。 ”

\n

然而，对于大哦表示法来说，情况有所不同。他什么意思？它们之间有什么区别？

我很困惑。我将其复制粘贴到下面：

\n

由于 O 表示法描述了一个上限，因此当我们使用它来限制算法的最坏情况运行时间时，我们对每个输入的算法运行时间都有一个限制。因此，O(n ^2) 插入排序最坏情况运行时间的限制也适用于每个输入的运行时间。然而，\xce\x98(n^2) 对插入排序最坏情况运行时间的限制，\n 并不意味着 \xce\x98(n^2) 对每个输入的插入排序运行时间的限制.\n 例如，当输入已排序时，插入排序会在\n \xce\x98(n) 时间内运行。

\n

假设A是一个数组,n是A中元素的数量,

recursive_insertion_sort(A, n)
    IF n > 1 THEN
        recursive_insertion_sort(A, n-1)
        key = A[n]
        i = n - 1
        DOWHILE A[i] > key AND i > 0
            A[i+1] = A[i]
            i = i - 1
        ENDDO
        A[i+1] = temp
    ENDIF
END

在这种情况下,有人可以解释递归是如何工作的吗？有一些我不明白的事情:

1. 我不明白为什么我们必须再次调用该函数,如果n> 1.
2. 当我们再次调用函数时,为什么要输入(n-1)？是这样我们从n = 2开始整个过程​​,前2个元素？
3. 一般如何递归递归？就像,一旦我们再次调用该函数,我们是否会忽略第4行的代码,并直接跳转到第二个调用？或者我们是否与第一个电话一起运行第二个电话？

桶排序是一种线性时间排序。

为什么我们要用插入排序呢？我们知道插入排序需要 O(n2) 时间。为什么我们不能在其中使用任何线性排序？正如我们所看到的，在每个桶中我们使用插入排序 O(n2)。桶排序的总复杂度是O(n)吗？为什么我们不使用 O(nlogn) 排序，例如合并排序或快速排序？

我对一个JAVA程序有一点问题.我试图做一个InsertionSort算法,但似乎是转换String程序通过stdin获取的问题.似乎程序只使用少量数字,但它不适用于这些数字:https: //dl.dropboxusercontent.com/u/57540732/numbers.txt

这是我的算法:

public class Sort {

    private static ArrayList<String> insertionSort(ArrayList<String> arr) {
        for (int i = 1; i < arr.size(); i++) {
            int valueToSort = Integer.parseInt(arr.get(i).trim());
            int j = i;
            while (j > 0 && Integer.parseInt(arr.get(j - 1).trim()) > valueToSort) {
                arr.set(j, arr.get(j-1));
                j--;
            }
            arr.set(j, Integer.toString(valueToSort));
        }
        return arr;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        ArrayList<String> al;
        String inputNumbers = sc.nextLine();
        String[] xs = inputNumbers.split(" ");
        al = new ArrayList<String>(Arrays.asList(xs)); …

我正在尝试Scala,我想看看如何在scala中实现插入排序,具有以下要求:

1. 嵌套for循环
2. Array [Int]用于输入
3. 如果可能的话,通过引用方式修改调用中函数内容的方法,否则返回一个数组[Int]

如果这不是实现插入排序的Scala方法,您仍然可以提供上述代码并解释该方法的错误.编辑:这是一个尝试使用while循环(doest工作),不,它不是一个功课问题,为什么敌意？

def insert_sort(a:Array[Int]):Array[Int]={
for(i <- 0 until a.length)
{
  var j=i+1

  while(j>1&&a(j)<a(j-1)&&j<a.length)
  {
      var c=a(j)
      a(j)=a(j-1)
      a(j-1)=c
      j-=1
  }
}
return a
}

在Java中,更快的是:创建,填充然后对下面的一组int进行排序

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    a[i] = Maths.rand(1, 500) // generate some random positive number less than 500
}
a.sort(); // (which algorithm is best?)

或者即时插入排序

int[] a = int[1000];
for (int i = 0; i < a.length; i++) {
    // not sure about the syntax
    int v = Maths.rand(1, 500) // generate some random positive number less than 500
    int p = findPosition(a, …

我正在开始使用堆的程序，其中必须将Sort，mergeSort和quickSort插入堆中。有人指示我使用课本中的代码作为基础，甚至无法编译示例代码。我不断收到错误：

not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation

现在我认为这与在sort.h文件中声明template <>类的顺序有关。但是，我无法想象教科书会发布根本无法编译的代码。你们介意看看吗？

完整错误：

In file included from Driver.cpp:4:0:
Sort.h: In instantiation of 'void heapsort(std::vector<Comparable>&) [with Comparable = int]':
Driver.cpp:47:21:   required from here
Sort.h:79:9: error: 'percDown' was not declared in this scope, and no declarations were found by argument-dependent lookup at the point of instantiation [-fpermissive]
Sort.h:104:6: note: 'template<class Comparable> void percDown(std::vector<Comparable>&, int, int)' declared here, later in the translation unit
Sort.h:83:9: …

这包括来自https://stackoverflow.com/help/on-topic的"软件算法"

这是来自课堂的讲座幻灯片

这是我们使用的插入排序的实现

public static void insertionSort(int[] a) {
     for (int i = 1; i < a.length; i++) {
          int temp = a[i];
          int j = i;
          while (j >= 1 && a[j - 1] > temp) {
                a[j] = a[j - 1];
         }
         a[j] = temp;
     }
}

我同意局部变量的空间复杂度将是O(1),因为它每次都是相同的局部变量,无论输入大小,i,j和temp都会占用一块内存.

但是我对阵列的空间复杂性感到困惑.http://www.cs.northwestern.edu/academics/courses/311/html/space-complexity.html有一个类似的例子,

int sum(int a[], int n) {
    int r = 0;
    for (int i = 0; i < n; ++i) {
       r += a[i];
    }
    return …

我正在阅读 Robert Sedgewick 的关于算法的书。

public static void sort(Comparable[] a)
{   // Sort a[] into increasing order.
    int N = a.length;
    for (int i = 1; i < N; i++)
    { // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
            exch(a, j, j-1);
    }
}

以上是java中的插入排序实现。这里作者提到如下改进。

通过缩短其内部循环将较大的条目移动到正确的位置而不是进行完全交换（从而将数组访问次数减少一半），大幅加快插入排序并不难

我很难理解上述改进。作者是什么意思

1. 将大条目移动到正确的一个位置，而不是完全交换，以及这将如何将数组访问减少一半。

请求以简单的例子举例，以便更好地理解。

我开始阅读“算法导论，第三版”一书，但遇到了一些对我来说不够清楚的关于“插入排序”算法的内容。

请先看一下图片：

首先，作者定义了 n = A.length。 A.length是数组 A 的长度。

因此，假设数组“A”的长度为 5。如果我从 j = 2（如图所示）到 A.Length = 5运行for循环，我会说第一行将运行 4 次，这意味着对于任何 n，它将运行 n - 1 次。另一方面，作者写道，第一行将运行 n 次。

我错过了什么？