Shell Sort 算法

Shell sort 是一种高效的排序算法，基于 insertion sort 算法。该算法避免了 insertion sort 中较小值位于最右端需要移动到最左端时的大量移位问题。

该算法首先对间隔较大的元素使用 insertion sort 进行排序，然后对间隔较小的元素进行排序。这种间隔称为 interval。该间隔根据 Knuth 的公式计算如下 −

h = h * 3 + 1
其中 
   h 是初始值为 1 的 interval

该算法对于中等规模的数据集非常高效，其平均情况和最坏情况的时间复杂度均为 O(n)，其中 n 是元素数量。

Shell Sort 算法

以下是 Shell sort 的算法步骤。

1. 初始化 h 的值。
2. 将列表划分为间隔为 h 的较小子列表。
3. 使用 insertion sort 对这些子列表进行排序。
4. 重复上述步骤，直到整个列表排序完成。

伪代码

以下是 Shell sort 的伪代码。

procedure shellSort()
   A : array of items

   /* 计算 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:

         /* 选择要插入的值 */
         valueToInsert = A[outer]
         inner = outer;
            
            /*向右移动元素*/
            while inner > interval -1 &&  A[inner - interval] 
			>= valueToInsert do:
               A[inner] = A[inner - interval]
               inner = inner  interval
            end while
         
         /* 在空位处插入数字 */
         A[inner] = valueToInsert
         end for
   
   /* 计算 interval*/
   interval = (interval -1) /3;
   end while
end procedure

示例

让我们通过以下示例来了解 Shell sort 的工作原理。我们使用之前示例中的相同数组。为了便于理解，我们取 interval 为 4。在间隔为 4 个位置的所有值上创建虚拟子列表。这里这些值为 {35, 14}，{33, 19}，{42, 27} 和 {10, 14}。

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

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

我们在原始数组中比较并交换值（如果需要）。完成此步骤后，数组应该如下所示 −

最后，我们使用 interval 为 1 对数组的其余部分进行排序。Shell sort 使用 insertion sort 来排序数组。

以下是逐步演示 −

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

实现

Shell sort 是一种高效的排序算法，基于 insertion sort 算法。该算法避免了 insertion sort 中较小值位于最右端且需要移动到最左端时的大量移位问题。

#include <stdio.h>
void shellSort(int arr[], int n){
   int gap, j, k;
   for(gap = n/2; gap > 0; gap = gap / 2) { //初始 gap = n/2，每次减少 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}; // 初始化数组
   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) { //初始 gap = n/2，每次减少 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}; // 初始化数组
   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}; //初始化数组
      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) { //初始 gap = n/2，每次减少 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 #使用整除避免浮点数结果
   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 #使用整除避免浮点数结果

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]