标签: insertion-sort

我写了一个简单的插入排序程序,但输出不正确.

class InsertionSort{
    public static void main(String h[]){
    int[] a = {5,4,3,2,1};
    int i,j,temp;
        for(i=1;i<a.length;i++){
            j = i-1; 
            while(i>0 && a[j] > a[i]){
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        for(int x=0; x<a.length;x++){
            System.out.println(a[x]);   
        }
    }
}

我正在阅读"算法简介"并阅读插入排序.
我试图在没有先阅读解决方案的情况下自己实现它.

这是我的解决方案,这是插入排序吗？

#include <iostream>

using namespace std;

int main()
{
    // initialize an unsorted array
    int a[] = {5,6,4,7,3,8,2,9,0,1};

    // define variables
    int i,j,tmp;

    for (int j=1; j<10; ++j)
    {
        for (int i=0;i<j;++i)
        {
            if (a[j] < a[i])
            {
                tmp = a[j];
                a[j] = a[i];
                a[i] = tmp;
            }
        }

    }

    for (i=0;i<10;++i)
    {
        cout << a[i] << endl;
    }

    return 0;
}

好的,我已经阅读了,并理解为什么它不是插入排序...这要好得多.

   #include <iostream>

    using namespace std;

    int main()
    {
        // initialize an unsorted array
        int a[] …

我正在阅读算法入门书和伪代码

INSERTION-SORT(A)
1 for j ? 2 to length[A]
2   do key ? A[j]
3     ? Insert A[j] into the sorted sequence A[1  j - 1].
4     i ? j - 1
5     while i > 0 and A[i] > key
6      do A[i + 1] ? A[i]
7         i ? i - 1
8     A[i + 1] ? key

虽然维基上的伪代码是

 for j ?1 to length(A)-1
     key ? A[ j ]
     > A[ j ] is added in the sorted …

我已经写下插入排序比选择排序更快,这比冒泡排序快,并且他们所有3的运行时间都是O(n ^ 2),但是我能说什么来比较它们呢？

所以我有一个MergeSort算法,我希望将MergeSort与Insertion排序相结合,以减少合并的开销,问题是如何？我想使用插入排序对段进行排序,然后合并.

 public class mergesorttest{
    public static void main(String[]args){
        int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};
        mergeSort(d,0,d.length);
        for(int x:d) System.out.print(x+" "); 
        System.out.println(); 
    }

static void mergeSort(int f[],int lb, int ub){
    //termination reached when a segment of size 1 reached -lb+1=ub
    if(lb+1<ub){
        int mid = (lb+ub)/2;
        mergeSort(f,lb,mid);
        mergeSort(f,mid,ub);
        merge(f,lb,mid,ub);
    }
}

static void merge (int f[],int p, int q, int r){
    //p<=q<=r
    int i =p; int j = q; 
    //use temp array to store merged sub-sequence
    int temp[] = new int[r-p]; int t = 0; 
    while(i<q …

在找到插入排序的最坏情况分析时,有人可以逐步解释我们如何得到O(N ^ 2)吗？我正在阅读Cormen Intro to Algorithms一书的解释,但这种解释有点令人困惑.

我正在尝试实现插入排序.当我在while循环中编写swap方法时,该算法工作正常.但是当我尝试调用swap()函数时,它给出了错误的答案.具体来说,当我传递参数'j'时,它会使答案出错.你能告诉我我犯了哪个错误.(关于ideone![ http://ideone.com/MoqHgn])

#include <iostream>
using namespace std;

void swap(int *x, int *y, int *j) { 
    int temp = *x;
    *x = *y;
    *y = temp;
    *j--;
}

int main() {
    int N;
    scanf("%d", &N);
    int a[N];
    for(int i = 0; i < N; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i < N; i++) {
        int j = i;
        while(j > 0 && a[j-1] > a[j]) {
            swap(&a[j-1], &a[j], &j);
            //int temp = a[j];
            //a[j] = a[j-1]; …

for (int i = 1; i < data.Count; i++) 
{
    int j = i;
    while (j > 0)
    {
        if (numarray[j - 1] > numarray[j])
        {   
            int temp = numarray[j - 1];
            numarray[j - 1] = numarray[j];
            numarray[j] = temp;
            j--;

        }

        else
            break;
    }
}

有人可以帮我确定上面代码的排序算法是什么吗？我知道冒泡排序效率不高。如果我要改用插入排序算法，我该如何改进上面的代码。谢谢！

众所周知，插入排序的最佳情况运行时间为n，最坏情况运行时间为n ²。在这种情况下，它是否具有很大的 theta 值？

我从昨天开始学习这本书,在我理解并应用了第一个算法之后,我试着去了解自己并以不同的方式看待.这是在Java中显示的算法:

public static int[] sort(int[] array)
{
    for(int i = 1; i < array.length; i++){
        int value = array[i];
        int j = i - 1;

        while(j >= 0 && array[j] > value){
            array[j + 1] = array[j];
            j--;
        }
        array[j+1] = value;
    }

    return array;
}

这是我的:

public static int[] sortb(int[] array)
{
    for(int i = 0; i < array.length; i++){
        int value = array[i];
        int j = i;

        while(j < array.length && value > array[j]){
            array[j] = array[j + …

def insertion_sort(list):
    for index in range(1,len(list)):
        value = list[index]
        i = index - 1
        while i>=0:
            if value < list[i]:
                list[i+1] = list[i]
                list[i] = value
                i = i - 1
            else:
                break

a = [7,1,3,5,9,2,3]

print(insertion_sort(a))

此代码取自可汗学院的视频.但是,当我尝试在Jupyter Notebook和IDLE上自己运行它时,它输出None.我无法弄清楚为什么它与视频完全相同.在此先感谢您的帮助.

我已经实现了插入排序,我猜它很好.它从文件读取并正确排序它们输入10,100,1000,10000,10000.

但是,当我给出一百万输入时,它什么也没做.我甚至等了10分钟检查它是否太慢了.
我动态创建了我的数组,并尝试合并排序.它完美地工作了一百万输入但我无法理解为什么只有插入排序算法不能用于一百万输入.这是代码的一部分完成工作;

#include <iostream>
#include <fstream>

using namespace std;

void InsertionSort(int* array, int& size);
int main()
{
    int size;
    ifstream myfile("data.txt");
    myfile.open("data.txt");
    cout << "How many elements do you want to read" << endl;
    cin >> size;

    int* array = new int[size];
    for (int i = 0; i < size; i++) {
        myfile >> array[i];
    }

    InsertionSort(array, size);
    delete[] array;
}
void InsertionSort(int* array, int& size)
{
    int temp, j;

    for (int i = 1; i < size; i++) …

我正在使用算法类Khan Academy for JavaScript.我写了这样的代码:

 var insert = function(array, rightIndex, value) {
        for(var i = rightIndex;
            i > 0 && array[i-1] > value;
            i--) {
            array[i] = array[i-1];
        }   
        array[i] = value; 
    };

    var insertionSort = function(array) {
    for (var st = 1; st < array.length; st++) {
        insert(array, st, array[st]);
    }
    };

    var array = [22, 11, 99, 88, 9, 7, 42];
    insertionSort(array);
    println("Array after sorting:  " + array);
    Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

而现在我想知道这里有什么问题,我无法进入下一个级别...请帮助.:)