标签: insertion-sort

假设我们有一个0索引序列S,取S [0]并将其插入S中的下一个值高于S [0]且前一个值低于S [0]的位置.形式上,S [i]应该放置在S [i-1] <S [i] <S [i + 1]的地方.按顺序继续按顺序对每个项目执行相同操作.在将元素放入正确的位置之前,从列表中删除元素.在列表上进行一次迭代后,应该对列表进行排序.我最近参加了考试,我忘了插入排序(不要笑),我这样做了.但是,我的教授认为这是错误的.据我所知,该算法确实产生了一个排序列表.

在列表中这样工作:

Sorting [2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 8, 5, 4, 7, 0, 6, 1, 10, 3, 9]
[2, 5, 4, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9]
[2, 4, 5, 7, 0, 6, 1, 8, 10, 3, 9] …

我正在研究Cormen的"算法导论"一书,我从伪代码创建了以下内容.但是,Array的前两个元素似乎没有排序.我无法发现错误(可能是因为它迟到了).所以我想知道是否有人能从第一眼看到.

#include <iostream>
#include <stdlib.h>

using namespace std;

int main(){
  int input;
  cout << "Enter length of desired array." << "\n";
  cin >> input;
  cout << "\n";

  int A [input];

  //Populate and print the Array.
  for(int i=0; i<input; i++){
    A[i] = rand()%99-1;
    cout << A[i] << " ";
  }

  cout << "\n";

  //Insertion sort.
  for(int j=2; j<input; j++){ //Iterate through the Array.
    int key = A[j]; //Store the current element into key.
    int i = j-1; //Iterator for while loop. …

我正在研究书中的渐近符号，但我无法理解作者的意思。我知道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

我试过寻找类似于我的问题,但没有找到太多帮助.

我有一个这种结构的链表:

struct PCB {
    struct PCB *next;
    int reg1, reg2;
};

我首先以这种方式创建10个PCB结构:

for(i=20;i<=30;i++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = i;
        curr->next  = head;
        head = curr;
    }

然后我需要再创建20个PCB结构,但是reg1需要使用它们生成它们的值rand().我正在这样做:

for (j = 0;j<20;j++) {
        curr = (struct PCB *)malloc(sizeof(struct PCB));
        curr->reg1 = rand()%100;
        curr->next  = head;
        head = curr;
    }

但是,当使用随机reg1值将这些PCB结构插入到链表中时,我需要按顺序将它们插入到链表中(插入排序).在单链接链表中处理此问题的最佳方法是什么？谢谢

编辑:我现在正在跟踪第一个创建的结构,以便能够从头开始循环链接列表:

// create root struct to keep track of beginning of linked list
root = (struct PCB *)malloc(sizeof(struct PCB));
root->next …

我试图了解更多关于如何使用Rcpp包的信息.所以我开始使用Rcpp测试基本的排序算法.我在这里开始了Hadley Wickham教程.

我以这种方式递归地成功实现了插入排序:

library(Rcpp)

vetor<-sample(100)
vetor
cppFunction("
    NumericVector insertionsortRC(NumericVector vetor, int n) {
        double aux;
        int i;

        if(n>1) {
            insertionsortRC(vetor,n-1);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

但函数要求2个参数,然后我尝试这样:

cppFunction("
    NumericVector insertionsortRC(NumericVector vetor) {
        int n = vetor.size();

        double aux;
        int i;

        if(n>1) {
            vetor.erase(n-1);
            insertionsortRC(vetor);
            aux=vetor[n-1];
            i=n-1;
            while(vetor[i-1]>aux && i>=0 ) {
                vetor[i]=vetor[i-1];
                i--;
                }
            vetor[i]=aux;
            }

        return vetor;
        }
    ")

我认为擦除在这里不是一个好主意,似乎我从内存中擦除了元素,并且在递归调用之后无法恢复它.我还想到问题可能在于vetor.erase(n-1); line,试过vetor.erase(n); 它编译了,但根本没用.

使用vetor.erase(n); 我在R中遇到以下错误:

insertionsortRC(vetor) …

最近我通过函数式编程风格实现了insert_sort算法,它变得更加简洁和声明.问题是如何将其更改为尾递归,如果列表的大小增加到10000,代码将抛出异常.

def InsertSort(xs: List[Int]): List[Int] = xs match {
    case Nil => Nil
    case x::rest => 
       def insert (x: Int, sorted_xs:List[Int]) :List[Int] = sorted_xs match{
           case Nil => List(x)
           case y::ys => if  (x <= y) x::y::ys else y::insert(x,ys)
       }
       insert(x,InsertSort(rest))
 }

我目前正在研究排序算法并找到了合并插入排序。我几乎找不到任何东西，但只有几篇论文和书籍参考。所以这个算法是由 Lester Ford, Jr. 和 Selmer Johnson 发现的。这里有部分描述：http : //www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf

我现在的问题是了解插入部分的工作原理，以及 1、3、5、11 的编号顺序，在如何插入的解释中提到。看着好眼熟，就是想不起来是什么了。

到目前为止，我所拥有的代码是这样的：

//pointer to array, array size, element size, compare function pointer
void sort(void *data, size_t n, size_t s, int (*fcomp)(void*, void*))
{
  if(!data) return;
  if(n < 2 || s == 0) return;

  size_t i = 0, j = 0, k = 0, l = 0, r = 0, m = 0;

  void *be = malloc((n/2)*s); //elements greater in pair comparison
  void *le = malloc((n/2 + n%2)*s);//elements …

假设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)); …