插入排序功能不起作用。为什么？

Question

void insertionsort(int a[], int n){
    int next, i, j;
    for(i=1; i<n; i++){
        if(a[i]<a[i-1]){
            for(j=i-2; j>=0; j--){
                if(a[j]<a[i]){
                    next = a[i];
                    a[i] = a[j];
                    a[j] = next;
                }
            }
        }
    }
}

这是一个应该按递增顺序排列数组元素的函数。为什么不起作用？

Answer 1

您的解决方案并不是算法所说的。您可以考虑不使用两个嵌套的for循环：

void insertionsort(int a[], int n){
   int i, key, j; 
   for (i = 1; i < n; i++) 
   { 
       key = a[i]; 
       j = i-1; 

       /* 
          Move all elements in the array at index 0 to i-1, that are 
          greater than the key element, one position to the right 
          of their current position 
       */
       while (j >= 0 && a[j] > key) 
       { 
           a[j+1] = a[j]; 
           j = j-1; 
       } 
       a[j+1] = key; 
   } 
}

Answer 2

你需要交换i-1索引值，并且第二个for循环条件应该是>。

void insertionsort(int a[], int n){
    int next, i, j;
    for(i=1; i<n; i++){
        if(a[i]<a[i-1]){
            for(j=i; j>0; j--){
                if(a[j - 1]>a[ j ]){
                    next = a[ j - 1];
                    a[j - 1] = a[j];
                    a[j] = next;
                }
            }
        }
    }
}