插入排序的錯誤輸出

Question

當我執行程序時出現錯誤的輸出，我不知道可能是什麼原因造成的。

正如你可以在下面我有一個數組。然而在執行程序時，我得到的輸出：

array[0]=3 
array[1]=1 
array[2]=1 
array[3]=5 
array[4]=5 
array[5]=8 

顯然，這是不是我的預期輸出這將是{} -1,3,4,5,7,8-。我究竟做錯了什麼？

#include <stdio.h> 
#include <stdlib.h> 
#define l 6 

void isnertionSort(int array[]); 

int main(void) 
{ 
    int array[l]={3,4,1,7,5,8}; 

    for(int i=0; i<l;i++) { 
    printf("array[%d]=%d\n", i, array[i]); 
    } 
    printf("\n"); 

    isnertionSort(array); 

    for(int i=0; i<l; i++){ 
    printf("array[%d]=%d\n", i, array[i]); 
    } 

    return 0; 
} 


void isnertionSort(int array[]) 
{ 
    int j,key; 
    for(int i =1;i<l;i++){ 
    key = array[i]; 

    j = i -1; 

    while(j>0 && array[j]>key){ 
     array[j+1]=array[i]; 
     j--;//j=j-1                         

    } 
    array[j+1]= key; 
    } 
} 

Answer 1

你的內部循環有兩個小錯誤。

while(j >= 0 && array[j]>key) { /* j> 0 changed to j>=0 */ 
    array[j+1]=array[j]; /* changed from i to j */ 
    j--; 
} 

這是非常方便的，如果你有insertion sort算法比較你實現調試。如果您縮進代碼，這樣也可以幫助您更輕鬆地發現這些錯誤。

Answer 2

對於初學者，程序中既沒有使用標題<stdlib.h>的聲明。所以指令

#include <stdlib.h> 

可能會被刪除。

對#defined名使用大寫字母好得多。例如

#define N 6 

這是難以區分低情況下信l和1爲代碼的讀取器。

您應該編寫一個通用的排序函數，而不是隻能接受固定6個元素的數組的函數。因此函數應該具有兩個參數，例如

void isnertionSort(int array[], size_t n); 

這個循環

1）不接觸與索引等於0和1的陣列的元件和2）組被聲明因爲key和array[i]是相同的值，所以大於key的所有元素都大於key。

array[j+1]=array[i]; 
      ^^^^^^^^ 

考慮到所有這些因素的程序可以看看下面的方式

#include <stdio.h> 

#define N 6 

void isnertionSort(int array[], size_t n); 

int main(void) 
{ 
    int array[N] ={ 3, 4, 1, 7, 5, 8 }; 

    for (size_t i = 0; i < N; i++) 
    { 
     printf("array[%zu] = %d\n", i, array[i]); 
    } 
    putchar('\n'); 

    isnertionSort(array, N); 

    for (size_t i = 0; i < N; i++) 
    { 
     printf("array[%zu] = %d\n", i, array[i]); 
    } 
    putchar('\n'); 

    return 0; 
} 

void isnertionSort(int array[], size_t n) 
{ 
    for(size_t i = 1; i < n; i++) 
    { 
     size_t j = i; 
     int value = array[i]; 

     for (; j != 0 && value < array[j-1]; --j) 
     { 
      array[j] = array[j-1]; 
     } 

     if (j != i) array[j] = value;   
    } 
} 

程序輸出是

array[0] = 3 
array[1] = 4 
array[2] = 1 
array[3] = 7 
array[4] = 5 
array[5] = 8 

array[0] = 1 
array[1] = 3 
array[2] = 4 
array[3] = 5 
array[4] = 7 
array[5] = 8