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 中较小值位于最右端且需要移动到最左端时的大量移位问题。C C Java Python#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; jn; j) { for(k j-gap; k0; k - gap) { if(arr[kgap] arr[k]) break; else { int temp; temp arr[kgap]; arr[kgap] 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; in; i) printf(%d ,arr[i]); printf(\n); shellSort(arr, n); printf(Array after Sorting: ); for(int i 0; in; i) printf(%d , arr[i]); printf(\n); }输出Array before Sorting: 33 45 62 12 98 Array after Sorting: 12 33 45 62 98#includeiostream 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; jn; j) { for(k j-gap; k0; k - gap) { if(arr[kgap] arr[k]) break; else { int temp; temp arr[kgap]; arr[kgap] 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; in; i) cout arr[i] ; cout endl; shellSort(arr, n); cout Array after Sorting: ; for(int i 0; in; i) cout arr[i] ; cout endl; }输出Array before Sorting: 33 45 62 12 98 Array after Sorting: 12 33 45 62 98import 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; in; 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; jn; j) { for(int k j-gap; k0; k - gap) { if(arr[kgap] arr[k]) break; else { int temp; temp arr[kgap]; arr[kgap] arr[k]; arr[k] temp; } } } } System.out.print(Array After Sorting: ); for(int i 0; in; i) System.out.print(arr[i] ); System.out.println(); } }输出Array before Sorting: 33 45 62 12 98 Array After Sorting: 12 33 45 62 98def 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]