标签: insertion-sort

我不明白:为什么我的插入排序实现每次跳过合并排序,对于任何大小的n？

    public List<Int32> InsertionSort(List<Int32> elements, Boolean ascending = true)
    {
        for (Int32 j = 1; j < elements.Count; j++)
        {
            Int32 key = elements[j];
            Int32 i = j - 1;

            while (i >= 0 && (elements[i].CompareTo(key) > 0) == ascending)
                elements[i + 1] = elements[i--];

            elements[i + 1] = key;
        }

        return elements;
    }

    public List<Int32> MergeSort(List<Int32> elements, Boolean ascending = true)
    {
        Sort(elements, 0, elements.Count - 1);

        return elements;
    }

    private void MergeSort(List<Int32> elements, Int32 startIndex, Int32 …

我有一个工作插入排序算法,可以对存储在数组中的整数进行排序.在另一个程序中,我创建了一个包含单词和计数的结构.我需要使用相同的插入排序按字母顺序对存储在数组中的结构进行排序.我理解如何比较它们,但是我找不到交换它们的方法.想法？

typedef struct { char * word; int count; } wordType;

这包括来自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 …

例如,插入排序被描述为部分排序数组的有效算法.但是,如何精确定义"部分排序"？

如果我有一个字符串数组,例如

string[] names = {"John Doe", "Doe John", "Another Name", "Name Another"};

如何使用插入排序对此数组进行排序？

维基百科有一些例子:https://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Insertion_sort#C.23

static void InsertSort(IComparable[] array)
{
    int i, j;

    for (i = 1; i < array.Length; i++)
    {
        IComparable value = array[i];
        j = i - 1;
        while ((j >= 0) && (array[j].CompareTo(value) > 0))
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = value;
    }
}

和

static void InsertSort<T>(IList<T> list) where T : IComparable<T>
{
    int i, j;

    for …

所以我试图将下面的代码变成一个递归方法,插入排序,但是尽管我尝试的却不能.谁能帮我？

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

编辑:我在想这样的事情,但它对我来说看起来并不是很复杂......

public static void insertionSort(int[] array, int index){
    if(index < array.length){
        int j = index;
        int B = array[index];
        while ((j > 0) && (array[j-1] > B)){
            array[j] = array[j-1];
            j--;
        }
        array[j] = B;
        insertionSort(array, index + 1); …

现在我已经有一段时间了,我遇到了一个错误.现在我正在制作的程序是一本地址簿,我正在使用插入排序对对象的arraylist进行排序,我称之为书籍(地址条目).现在我很快就发现我的分拣机没有正确排序,所以我制作了一个简单的程序来测试分拣机,而且它再次起作用.我想知道你们是否可以看看它并帮助我.

这是我的分拣机:

import java.util.ArrayList;
public class Sorts {

    /**
     * Sorts and array of integer from low to high
     * pre: none
     * post: Integers has been sorted from low to high
     */
    public static void insertionSort(ArrayList<String> test) {
        Comparable temp;
        int previousIndex;
        ArrayList<String> objectSort = test;

        for (int i = 1; i < objectSort.size(); i++) {
            temp = objectSort.get(i);
            previousIndex = i - 1;

            while ((objectSort.get(previousIndex).compareTo((String) temp)) == 1 && (previousIndex > 0)) {
                objectSort.set(previousIndex + 1, objectSort.get(previousIndex));
                previousIndex …

以下是我的插入排序代码:

void InsertionSort(vector<int> & ioList)
{
  int n = ioList.size();
  for (int i = 1 ; i < n ; ++i)
  {
    for (int j = 0 ; j <= i ; ++j)
    {
      //Shift elements if needed(insert at correct loc)
      if (ioList[j] > ioList[i]) 
      {
        int temp = ioList[j];
        ioList[j] = ioList[i];
        ioList[i] = temp;
      }
    }
  }
}

算法的平均复杂度为O(n ^ 2).

根据我对大O符号的理解,这是因为在这种情况下我们运行两个循环(外部一个n-1次,内部一个1,2,... n-1 = n(n-1)/ 2次因此由此产生的算法的无症状复杂性为O(n ^ 2).

现在我已经读过,输入数组已经排序的情况就是最好的情况.在这种情况下,算法的大O复杂度是O(n).但是我无法理解这是如何可能的,因为在两种情况下(平均情况和最佳情况)我们必须运行相同次数的循环并且必须比较元素.唯一可以避免的是元素的转移.

那么复杂性计算也涉及这种交换操作的一个组成部分？

任何人都可以解释为什么插入排序的时间复杂度为Θ(n²)？

我很确定我将时间复杂性理解为一个概念,但我并不真正理解如何将它应用于这种排序算法.我应该只看数学证据来找到这个答案吗？

我的插入排序算法出现此错误:

insertionsort.lpr(19,17)错误:不兼容的类型:得到"布尔"预期"LongInt"

这是我的代码的第19行

 while j > 0 and A[j]>key do            

我试过在互联网上搜索谷歌,但我找不到任何语法错误或任何东西.

如果它有帮助,这是完整的代码:

program instert;
uses crt;
const
  N = 5;
var
   i:integer;
   j:integer;
   key:integer;
   A : Array[1..N] of Integer;


procedure insertionsort;
  begin
  for i := 2 to N  do
    begin
    key := A[1];
    j:= i - 1;
        while j > 0 and A[j]>key do
        begin
          A[j+1] := A[j] ;
          j := j-1;
        end;
    A[j+1] := key ;
   end;
 end;

begin
  A[1]:= 9;
  A[2]:= 6;
  A[3]:= 7;
  A[4]:= 1;
  A[5]:= 2; …