使用 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]
==================================================