数据结构&算法 希尔排序

  • 希尔排序

    希尔排序是一种高效的排序算法,它基于插入排序算法。如果较小的值在最右边并且必须移到最左边,则该算法避免了在插入排序的情况下的大移位。该算法对广泛分布的元素使用插入排序,首先对它们进行排序,然后对间距较小的元素进行排序。该间隔称为间隔。该间隔是根据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}
    shellsort
    我们比较每个子列表中的值,并在原始数组中交换它们(如果需要)。完成此步骤后,新数组应如下所示:
    shellsort
    然后,我们取间隔1,此间隔生成两个子列表-{14,27,35,42},{19,10,33,44}
    shellsort
    如果需要,我们将比较并交换原始数组中的值。完成此步骤后,数组应如下所示:
    shellsort
    最后,我们使用值1的间隔对数组的其余部分进行排序。希尔排序使用插入排序对数组进行排序。
    以下是分步描述-
    shellsort
    我们看到它只需要四个交换就可以对数组的其余部分进行排序。
  • 算法

    以下是希尔排序的算法。
    
    步骤 1 − 初始化h的值
    步骤 2 − 将列表划分为更小的子列表,子列表的间隔为h
    步骤 3 − 使用插入排序对这些子列表排序
    步骤 4 − 重复此操作,直到完成列表排序
    
  • 伪码

    现在我们将看到希尔排序函数的伪代码。正如我们的算法指出的两个主要功能-分和合并。希尔排序与递归一起工作,我们将以相同的方式看到实现。
    
    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;
    }
    
    尝试一下