希尔排序算法
希尔排序是一种高效的排序算法，它基于插入排序算法。该算法避免了插入排序中较大的移位，即较小的值位于最右侧，需要移到最左侧。
该算法对分布较广的元素使用插入排序，首先对它们进行排序，然后再对分布较近的元素进行排序。这个间距称为间隔。该间隔基于 Knuth 公式计算，如下所示 −
h = h * 3 + 1 where − h is interval with initial value 1
该算法对于中等规模的数据集非常高效，因为其平均和最坏情况复杂度均为 O(n)，其中 n 为项目数。
希尔排序算法
以下是希尔排序的算法。
1. 初始化 h 的值。 2. 将列表划分为 h 间隔相等的较小子列表。 3. 使用插入排序对这些子列表进行排序。 4. 重复此操作，直到完整列表排序完毕。
伪代码
以下是希尔排序的伪代码。
procedure shellSort()
A : array of items
/* 计算间隔 */
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 -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}; //初始化数组
printf("排序前的数组：");
for(int i = 0; i<n; i++)
printf("%d ",arr[i]);
printf("
");
shellSort(arr, n);
printf("排序后的数组：");
for(int i = 0; i<n; i++)
printf("%d ", arr[i]);
printf("
");
}
输出
排序前的数组：33 45 62 12 98 排序后的数组：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}; //初始化数组
cout << "排序前的数组：";
for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
shellSort(arr, n);
cout << "排序后的数组：";
for(int i = 0; i<n; i++)
cout << arr[i] << " ";
cout << endl;
}
输出
排序前的数组：33 45 62 12 98 排序后的数组：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("排序前的数组：");
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("排序后的数组：");
for(int i = 0; i<n; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
输出
排序前的数组：33 45 62 12 98 排序后的数组：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 #使用底部除法来避免结果为浮点值
arr = [33, 45, 62, 12, 98]
n = len(arr)
print("排序前的数组：")
print(arr)
shell_sort(arr, n);
print("排序后的数组：")
print(arr)
输出
排序前的数组： [33, 45, 62, 12, 98] 排序后的数组： [12, 33, 45, 62, 98]
