使用 C 的 DSA —— 插入排序

概述

插入排序是一种简单的排序算法。这种排序算法是基于比较的原地算法，其中选取一个项目，搜索其合适的位置，然后将该项目插入该特定位置，使有序列表不断增大。这种算法不适合大数据集，因为其平均情况和最坏情况复杂度均为 O(n²)，其中 n 是项目的数量。

伪代码

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert
   for i = 1 to length(A) inclusive do:
      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i
      /*locate hole position for the element to be inserted */
      while holePosition > 0 and A[i-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while
      /* insert the number at hole position */
      A[holePosition] = valueToInsert
   end for
end procedure

范例

#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[i-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();
   }  
}
main(){
   printf("Input Array: ");
   display();
   printline(50);
   insertionSort();
   printf("Output Array: ");
   display();
   printline(50);
}

输出

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

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 moved :6
   item inserted :7, at position :4
iteration 6#: [1, 2, 3, 4, 7, 6, 9]
Output Array: [1, 2, 3, 4, 7, 6, 9]
==================================================