使用 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("=
");
}
void display(){
   int i;
   printf("[");
   // navigate through all items 
   for(i=0;i<MAX;i++){
      printf("%d ",intArray[i]);
   }
   printf("]
");
}
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
" , intArray[holePosition]);
      }

      if(holePosition!= i){
         printf(" item inserted : %d, at position : %d
"
            , 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]
==================================================

dsa_using_c_sorting_techniques.html