插入排序的实现

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;  
    } 
}