使用 C 的数据结构和算法：希尔排序

概述

希尔排序是一种非常高效的排序算法，其基于插入排序算法。此算法避免了插入排序中的大量移动，即在较小的值位于最右边并且必须移动到最左边的情况下。此算法先对广泛分布的元素使用插入排序进行排序，然后对间隔较小的元素排序。此间隔被称为间隔。此间隔基于 Knuth 的公式计算：其中 h 为间隔，初始值为 1。对于中等大小的数据集，此算法是非常高效的，因为其平均和最坏情况复杂度为 O(n)，其中 n 表示项目的数量。

伪代码

procedure shellSort( A : array of items )
   int innerPosition, outerPosition
   int valueToInsert, interval = 1
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 +1	    
   
   while interval > 0 do:
      for outer = interval; outer < A.length; outer ++ do:
         /* select value to be inserted */
	      valueToInsert = A[outer]
         inner = outer;
         /*shift element towards right*/
         while inner > interval -1 && A[inner - interval] >= valueToInsert do:
            A[inner] = A[inner-1]
            inner = inner - interval
         end while
         /* insert the number at hole position */
         A[inner] = valueToInsert
      end for
      /* calculate interval*/
      interval = (interval -1) /3;	  
   end while
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 shellSort(){
   int inner, outer;
   int valueToInsert;
   int interval = 1;   
   int elements = MAX;
   int i=0;
   while(interval <= elements/3){
      interval = interval*3 +1;                   
   }
   while(interval > 0){
      printf("iteration %d#:",i); 
      display();
      for(outer = interval; outer < elements; outer++){
         valueToInsert= intArray[outer];
         inner = outer;
         while(inner > interval -1 && 
            intArray[inner - interval] >= valueToInsert){
            intArray[inner] = intArray[inner - interval];
            inner -=interval;
            printf(" item moved :%d\n",intArray[inner]);
         }
         intArray[inner] = valueToInsert;
         printf(" item inserted :%d, at position :%d\n",valueToInsert,inner);
      }
      interval = (interval -1) /3;           
      i++;
   }          
}
main(){
   printf("Input Array: ");
   display();
   printline(50);
   shellSort();
   printf("Output Array: ");
   display();
   printline(50);
}

输出

如果我们编译并运行以上程序，它会产生以下输出 -

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