插入排序的實現

Question

這是我的代碼。

#include<stdio.h> 
void insert(int member,int arr[],int size) 
{ 
    int i,j; 
    for(i=0;i<size;i++) 
    { 
     if(member<arr[i]) 
     { 

      for(j=0;j<size-i;j++) 
      { 
       arr[size]=arr[size-1]; 
     } 
     arr[i]=member; 
     break; 
     } 
    }  
} 
void insertsort(int arr[],int size) 
{ 
    int newsize=1,member; 
    for(newsize=1;newsize<size;newsize++) 
    { 
    member=arr[newsize]; 
    insert(member,arr,newsize); 
    } 
} 
void main() 
{ 
    int arr[100]; 
    int size,i; 
    printf("enter the size"); 
    scanf("%d",&size); 
    printf("enter numbers"); 
    for(i=0;i<size;i++) 
    { 
     scanf("%d",&arr[i]); 
    } 
    insertsort(arr,size); 
    for(i=0;i<size;i++) 
    printf("\n %d",arr[i]); 
} 

我不知道是什麼問題，但在進入

元素的數量：5;

輸入數字45 23 87 345 12

輸出12 45 87 345 345

誰能告訴我是什麼問題？

Answer 1

在您插入函數中，將arr[size]=arr[size-1];更改爲arr[size-j]=arr[size-j-1];。

當你做插入時，我想你想在插入點1步後右移所有數字，但是你只能移動最右邊的一個。

void insert(int member,int arr[],int size) 
{ 
    int i,j; 
    for(i=0;i<size;i++) 
    { 
     if(member<arr[i]) 
     { 
      for(j=0;j<size-i;j++) 
      { 
       arr[size-j]=arr[size-j-1]; 
      } 
      arr[i]=member; 
      break; 
     } 
    }  
} 

Answer 2

for(i=1; i<N; i++) 
    { 
     Temp = A[i]; 
     j = i-1; 
     while(Temp<A[j] && j>=0) 
     { 
      A[j+1] = A[j]; 
      j = j-1; 
     } 
     A[j+1] = Temp; 
    } 

Answer 3

下面是插入排序代碼：

int InsertionSort() 
{ 
    int max; 
    int *numarray = 0; 
int i,j,k,temp; 

printf("\nProgram for Ascending order of Numeric Values using INSERTION SORT"); 
    printf("\n\nEnter the total number of elements: "); 
    scanf("%d", &max); 

    numarray = (int*) malloc(sizeof(int) * max); 

    for(i = 0; i < max; i++) 
    { 
     printf("\nEnter [%d] element: ", i + 1); 
     scanf("%d", &numarray[i]); 
    } 

    printf("Before Sorting : "); 
    for(k = 0; k < max; k++) 
     printf("%d ", numarray[k]) 
    printf("\n"); 

    for(i = 1; i < max; i++) 
    { 
     j = i; 
     while(j > 0) 
     { 
      if(numarray[j-1] > numarray[j]) 
      { 
       temp = numarray[j - 1]; 
       numarray[j - 1] = numarray[j]; 
       numarray[j] = temp; 
       j--; 
      } 
      else 
       break; 
     } 
     printf("After iteration %d ": ", i); 
     for(k = 0; k < max; k++) 
      printf("%d ", numarray[k]); 
     printf("/*** %d numbers from the begining of the array are input and they are sorted ***/\n", i + 1); 
    } 

    printf("\n\nThe numbers in ascending orders are given below:\n\n"); 
    for(i = 0; i < max; i++) 
    { 
     printf("Sorted [%d] element: %d\n",i + 1, numarray[i]); 
    } 

    free(numarray); 
    return 0; 
} 

的輸出將是一個使用插入排序

輸入元件的總數數值的升序

程序： 8

輸入[1]元素：80

輸入[2]元素：60

輸入[3]元素：40

輸入[4]的元素：20

輸入[5]元素：10

輸入[6 ]元素：30

輸入[7]元素：50

輸入[8]元素：70

個

升序訂單中的數字給出如下：

排序[1]元素：10

排序[2]元素：20

排序[3]元素：30

排序[4]的元素：40

排序[5]的元素：50

排序[6]元件：60

排序[7]元素：70

排序[8]元素：80

Answer 4

這裏是C＃中的插入排序。您可以輕鬆地將其轉換爲C或C++

class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] set = new[] { 5, 3, 2, 9, 6, 1, 7, 2 }; 
     int[] result = InsertionSort(set); 
    } 

    static int[] InsertionSort(int[] list) { 
     if (list.Length < 2) { 
      return list; 
     } 
     for (int i = 0; i < list.Length - 1; i++) { 
      for (int j = i + 1; j > 0 && list[j - 1] > list[j]; j--) { 
       int temp = list[j - 1]; 
       list[j - 1] = list[j]; 
       list[j] = temp; 
      } 
     } 
     return list; 
    } 
} 

Answer 5

A是未排序的元素的數組.. 的想法非常相似，你怎麼在你的手在一個典型的紙牌遊戲排序卡。 你拿起第一張牌。然後你選擇第二張牌等等，然後向後比較，直到你找到一張比當前牌大的牌。然後，當您向後移動時，將當前卡片插入此位置，有效地將所有卡片向右移。在此循環之後，您手中的所有元素都將被排序。 我有一個更詳細的描述http://www.worldkosh.com/2016/12/22/insertion-sort/

該文章的靈感來自Cormen，Thomas H. Leiserson，Charles E. Rivest，Ronald L.; Stein，Clifford（2001）[1990]。算法介紹（第二版）。

僞代碼 假設0基於起始索引

Insertion_sort(array A) { 
    for(int i = 1;i < n; i++) { 
     key = A[i]; 
     for(int j = i-1; j>= 0 and A[j]>key; j--) { 
      A[j +1] = A[j]; 
     } 
     A[j+1] = key;  
    } 
}