希尔排序

希尔排序 首页 / 结构和算法入门教程 / 希尔排序

希尔排序是一种高效的排序算法,它基于插入排序算法。如果较小的值在最右边并且必须移到最左边,则该算法避免了在插入排序的情况下的移位操作。

该算法对广泛分布的元素使用插入排序,首先对它们进行排序,然后对间距较小的元素进行排序。该间隔是根据Knuth的公式计算的-

Knuth公式

h=h * 3 + 1
where -
   h is interval with initial value 1

对于中等大小的数据集,此算法非常有效,因为该算法的平均复杂度和最坏情况的复杂度取决于间隙序列,众所周知,该间隙序列是Ο(n),其中n是项数,最坏的情况是空间复杂度为O(n)。

希尔排序原理

让我们考虑以下示例,以了解希尔排序的工作原理,我们采用与先前示例相同的数组,对于我们的示例和易于理解,我们采用4的间隔。为位于4个位置的间隔的所有值创建一个虚拟子列表。这些值是{35,14},{33,19},{42,27}和{10,44}

Shell Sort

我们比较每个子列表中的值,并在原始数组中交换它们(如果需要)。完成此步骤后,新数组应如下所示:

Shell Sort

然后,我们取间隔1,此间隔生成两个子列表-{14,27,35,42},{19,10,33,44}

Shell Sort

如果需要,我们将比较并交换原始数组中的值。完成此步骤后,数组应如下所示:

Shell Sort

最后,我们使用值1的间隔对数组的其余部分进行排序。希尔排序使用插入排序对数组进行排序。

以下是分步描述-

Shell Sort

我们看到它只需要四个交换就可以对数组的其余部分进行排序。

无涯教程网

希尔排序伪代码

以下是用于希尔排序的伪代码。

procedure shellSort()
   A : array of items 
	
   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1	    
   end while
   
   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 - interval]
            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

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 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++;
   }          
}

int main() {
   printf("Input Array: ");
   display();
   printline(50);
   shellSort();
   printf("Output Array: ");
   display();
   printline(50);
   return 1;
}
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 ]
==================================================

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

快速上手Kotlin开发 -〔张涛〕

面试现场 -〔白海飞〕

软件工程之美 -〔宝玉〕

MongoDB高手课 -〔唐建法(TJ)〕

架构实战案例解析 -〔王庆友〕

去无方向的信 -〔小麥〕

中间件核心技术与实战 -〔丁威〕

超级访谈:对话毕玄 -〔毕玄〕

零基础学Python(2023版) -〔尹会生〕

好记忆不如烂笔头。留下您的足迹吧 :)