设计与分析 - 希尔排序

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

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

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

该算法对于中等规模的数据集非常有效，因为其平均和最坏情况复杂度均为 O(n)，其中n是项目数。

希尔排序算法

以下是希尔排序的算法。

步骤 1 - 初始化 h 的值

步骤 2 - 将列表分为等间隔 h 的较小子列表

步骤 3 - 使用插入排序对这些子列表进行排序

步骤 3 - 重复直到完成列表排序

伪代码

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

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

例子

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

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

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

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

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

以下是分步描述 -

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

例子

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

#include <stdio.h>
void shellSort(int arr[], int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else {
               int temp;
               temp = arr[k+gap];
               arr[k+gap] = arr[k];
               arr[k] = temp;
            }
         }
      }
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {33, 45, 62, 12, 98}; // initialize the array
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   shellSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 33 45 62 12 98
Array after Sorting: 12 33 45 62 98

#include<iostream>
using namespace std;
void shellSort(int *arr, int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
      for(j = gap; j<n; j++) {
         for(k = j-gap; k>=0; k -= gap) {
            if(arr[k+gap] >= arr[k])
               break;
            else {
               int temp;
               temp = arr[k+gap];
               arr[k+gap] = arr[k];
               arr[k] = temp;
            }
         }
      }
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {33, 45, 62, 12, 98}; // initialize the array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   shellSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 33 45 62 12 98
Array after Sorting: 12 33 45 62 98

import java.io.*;
import java.util.*;
public class ShellSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {33, 45, 62, 12, 98}; //initialize an array
      System.out.print("Array before Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      int gap;
      for(gap = n/2; gap > 0; gap = gap / 2) { //initially gap = n/2, decreasing by gap /2
         for(int j = gap; j<n; j++) {
            for(int k = j-gap; k>=0; k -= gap) {
               if(arr[k+gap] >= arr[k])
                  break;
               else {
                  int temp;
                  temp = arr[k+gap];
                  arr[k+gap] = arr[k];
                  arr[k] = temp;
               }
            }
         }
      }
      System.out.print("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 33 45 62 12 98
Array After Sorting: 12 33 45 62 98

def shell_sort(array,n):
   gap = n//2 #using floor division to avoid float values as result
   while gap > 0:
      for i in range(int(gap),n):
         temp = array[i]
         j = i
         while j >= gap and array[j-gap] >temp:
            array[j] = array[j-gap]
            j -= gap
            array[j] = temp
      gap = gap // 2 #using floor division to avoid float values as result

arr = [33, 45, 62, 12, 98]
n = len(arr)
print("Array before Sorting: ")
print(arr)
shell_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[33, 45, 62, 12, 98]
Array after Sorting: 
[12, 33, 45, 62, 98]