点击这里

这是一种基于比较的就地排序算法。 这里，维护一个始终排序的子列表。 例如，维护数组的下半部分以进行排序。 要在此已排序的子列表中“插入”的元素必须找到其适当的位置，然后将其插入其中。 因此名称插入排序。

用C实现 (Implementation in C)

#include <stdio.h>
#include <stdbool.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {
   int i;
   for(i = 0;i < count-1;i++) {
      printf("=");
   }
   printf("=\n");
}
void display() {
   int i;
   printf("[");
   // navigate through all items 
   for(i = 0;i < MAX;i++) {
      printf("%d ",intArray[i]);
   }
   printf("]\n");
}
void insertionSort() {
   int valueToInsert;
   int holePosition;
   int i;
   // loop through all numbers 
   for(i = 1; i < MAX; i++) { 
      // select a value to be inserted. 
      valueToInsert = intArray[i];
      // select the hole position where number is to be inserted 
      holePosition = i;
      // check if previous no. is larger than value to be inserted 
      while (holePosition > 0 && intArray[holePosition-1] > valueToInsert) {
         intArray[holePosition] = intArray[holePosition-1];
         holePosition--;
         printf(" item moved : %d\n" , intArray[holePosition]);
      }
      if(holePosition != i) {
         printf(" item inserted : %d, at position : %d\n" , valueToInsert,holePosition);
         // insert the number at hole position 
         intArray[holePosition] = valueToInsert;
      }
      printf("Iteration %d#:",i);
      display();
   }  
}
void main() {
   printf("Input Array: ");
   display();
   printline(50);
   insertionSort();
   printf("Output Array: ");
   display();
   printline(50);
}

如果我们编译并运行上面的程序，它将产生以下结果 -

输出 (Output)

Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
 item moved : 6
 item moved : 4
 item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item inserted : 2, at position : 0
Iteration 3#:[2 3 4 6 1 9 7 ]
 item moved : 6
 item moved : 4
 item moved : 3
 item moved : 2
 item inserted : 1, at position : 0
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
 item moved : 9
 item inserted : 7, at position : 5
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================