订阅
0有用+1
发展历史
播报编辑
Donald Shell, 1924-2015希尔排序是基于插入排序的以下两点性质而提出改进方法的：
- 1.插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。
- 2.但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
1961年，IBM 公司的女程序员 Marlene Metzner Norton（玛琳·梅茨纳·诺顿）首次使用 FORTRAN 语言编程实现了希尔排序算法。在其程序中使用了一种简易有效的方法设置希尔排序所需的增量序列：第一个增量取待排序记录个数的一半，然后逐次减半，最后一个增量为 1。该算法后来被称为 Shell-Metzner 算法 [3]，Metzner 本人在2003年的一封电子邮件中说道：“我没有为这种算法做任何事，我的名字不应该出现在算法的名字中。” [4]
2025年，有研究采用形式化方法，借助Frama-C平台对希尔排序程序进行了源代码级别的正确性验证。
算法思想
播报编辑
希尔排序(Shell Sort)是插入排序的一种改进版本，也称为缩小增量排序。其改进基于插入排序的两点性质：插入排序在对几乎已经排好序的数据操作时效率高；但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。 [5]
希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。 [1] [5]
希尔排序按其设计者希尔（Donald Shell）的名字命名，该算法由希尔在1959年所发表。 [2]
希尔排序的时间复杂度取决于增量序列，最坏情况为O(n²)，最好情况为O(n log n)，平均情况在O(n log n)到O(n²)之间。 [5]对于较好的增量序列（如Knuth、Sedgewick序列），平均时间复杂度在O(n^{1.25})到O(n^{1.5})之间。 [6]
算法步骤
播报编辑
希尔排序是插入排序的一种改进版本，也称为缩小增量排序。 [5]其通用步骤首先需要选择一个递减的增量序列。然后按照当前增量将待排序序列分割成若干子序列，并对每个子序列分别进行直接插入排序。之后减小增量值，重复上述分组与排序过程。当增量最终减至1时，整个序列作为一组进行最后一次直接插入排序，即完成排序。 [1] [5-6]
复杂度分析
播报编辑
希尔排序的时间复杂度最坏情况为O(n²)，最好情况为O(n log n)，平均情况在O(n log n)到O(n²)之间，取决于增量序列 [5]。对于较好的增量序列（如Knuth序列、Sedgewick序列），平均时间复杂度在O(n^{1.25})到O(n^{1.5})之间 [6]。空间复杂度为O(1)，是原地排序算法，不需要额外的存储空间。希尔排序是不稳定的排序算法，可能改变相同元素的相对顺序 [5]。
增量序列
播报编辑
希尔排序的关键在于一个称为增量序列的概念，它决定了每次划分子序列的间隔。 [6]增量序列是一个递减的整数序列，其中最后一个增量必须为1。
实践中，研究者们提出了多种增量序列以优化希尔排序的性能，常见的增量序列包括Shell原始序列、Hibbard序列、Knuth序列以及Sedgewick序列等。 [6]Shell原始序列即初始间隔为n/2，并逐次减半，直至1。
希尔排序的性能关键在于增量序列的选择。采用较好的增量序列（如Sedgewick序列）时，算法的平均时间复杂度可以达到O(n^{1.25})到O(n^{1.5})之间。 [6]
与其他算法的对比
播报编辑
希尔排序常与几种经典排序算法进行对比以明确其特点。与插入排序相比，希尔排序是其改进版本，平均时间复杂度通常为O(n^{1.25}) ~ O(n^{1.5})，远优于插入排序的O(n²)，两者同为原地排序（空间复杂度O(1)），但希尔排序是不稳定排序算法，而插入排序是稳定的 [5-6]。与归并排序对比，归并排序的时间复杂度稳定为O(n log n)且是稳定的，但需要O(n)的额外存储空间；希尔排序则是原地排序但不稳定。与快速排序相比，快速排序的平均时间复杂度为O(n log n)，空间复杂度为O(log n)，同样不稳定 [6]；希尔排序在中等规模数据集上表现良好，实现相对简单。希尔排序的适用场景主要包括中等规模数据集、需要比简单插入排序更高效的场合，以及作为更复杂排序算法的预处理步骤 [5]。
代码实现
播报编辑
伪代码
input: an array a of length n with array elements numbered 0 to n − 1
inc ← round(n/2)
while inc > 0 do:
for i = inc .. n − 1 do:
temp ← a[i]
j ← i
while j ≥ inc and a[j − inc] > temp do:
a[j] ← a[j − inc]
j ← j − inc
a[j] ← temp
inc ← round(inc / 2.2)
Golang
func ShellSort(nums []int) []int{
//外层步长控制
for step := len(nums) / 2; step > 0; step /= 2 {
//开始插入排序
for i := step; i < len(nums); i += step {
//满足条件则插入
for j := i - step; j >= 0 && nums[j+step] < nums[j]; j -= step {
nums[j], nums[j+step] = nums[j+step], nums[j]
}
}
}
return nums
}
vb.net
Function Shell(Byval lines() As Integer) As Integer()
dim c() As Integer=lines.clone,div,i,j,k As Integer,Data As Integer
if UBound(c)=1 then return lines
For div=len/2 To 1
div/=2
For i=0 To div Step 1
For j=i To len-div
For k=j to len Step div
If(data[j]>data[k])
swapInt(data+j,data+k)
End If
Next
Next
Next
Next
End Function
javascript
var arr = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04];
var len = arr.length;
for (var fraction = Math.floor(len / 2); fraction > 0; fraction = Math.floor(fraction / 2)) {
for (var i = fraction; i <= len; i += fraction) {
for (var j = i - fraction; j >= 0 && arr[j] > arr[fraction + j]; j -= fraction) {
var temp = arr[j];
arr[j] = arr[fraction + j];
arr[fraction + j] = temp;
}
}
}
console.log(arr);
pascal
const size=12;
type arr=array[1..size]ofinteger;
var a:arr; i,j,k,t:integer;
procedure DataInput;//生成随机数列
begin
randomize;
for i:=1 to size do
begin
a[i]:=random(99)+1;
write(a[i]:3);
end;
writeln;
end;
procedure DataOutput;//输出
begin
for i:=1 to size do write(a[i]:3);
end;
procedure insertionsort(var a:arr);
begin
for i:=2 to size do
begin
t:=a[i];
j:=i-1;
while (j>0) and (t<a[j]) do
begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=t;
end;
end;
begin
DataInput;
k:=size;
while k>1 do
begin
k:=k div 2;
for j:=k+1 to size do
begin
t:=a[j];
i:=j-k;
while (i>0) and (a[i]>t) do
begin
a[i+k]:=a[i];
i:=i-k;
end;
a[i+k]:=t;
end;
end;
DataOutput;
end.
Kotlin
fun sort(arr: IntArray) {
var gap = arr.size / 2
while (1 <= gap) {
for (i in gap..arr.size - 1) {
var j = i - gap
val tmp = arr[i]
while (j >= 0 && tmp < arr[j]) {
arr[j + gap] = arr[j]
j -= gap
}
arr[j + gap] = tmp
}
gap /= 2
}
}
JAVA
public static void main(String[] args){
int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1};
System.out.println("排序之前：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
//希尔排序
int gap = array.length;
while (true) {
gap /= 2; //增量每次减半
for (int i = 0; i < gap; i++) {
for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
int k = j - gap;
while (k >= 0 && array[k] > array[k+gap]) {
int temp = array[k];
array[k] = array[k+gap];
array[k + gap] = temp;
k -= gap;
}
}
}
if (gap == 1)
break;
}
System.out.println();
System.out.println("排序之后：");
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
}
C#
using System;
using System.Collections.Generic;
namespace Demo
{
class Program
{
public static List<int> ShellSort(List<int> data)
{
for (int gap = data.Count / 2; gap > 0; gap = gap / 2) {
for (var i = gap; i < data.Count; i++) {
var j = i;
var current = data[i];
while (j - gap >= 0 && current < data[j - gap]) {
data[j] = data[j - gap];
j = j - gap;
}
data[j] = current;
}
}
return data;
}
public static void Main(String[] args)
{
var iArray = new List<int> { 1, 5, 3, 6, 10, 55, 55, 100, 9, 2, 87, 12, 34, 75, 33, 47 };
var newArray = ShellSort(iArray);
Console.WriteLine(string.Join(",", newArray));
}
}
}
C语言
#include<stdio.h>
#include<math.h>
#define MAXNUM 10
void shellSort(int array[],int n,int t);//t为排序趟数
void main()
{
int array[MAXNUM],i;
for(i=0;i<MAXNUM;i++)
scanf("%d",&array[i]);
shellSort(array,MAXNUM,(int)(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分
for(i=0;i<MAXNUM;i++)
printf("%d ",array[i]);
printf("\n");
}
//根据当前增量进行插入排序
void shellInsert(int array[],int n,int dk)
{
int i,j,temp;
for(i=dk;i<n;i++)//分别向每组的有序区域插入
{
temp=array[i];
for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
array[j+dk]=array[j];
if(j!=i-dk)
array[j+dk]=temp;//插入
}
}
//计算Hibbard增量
int dkHibbard(int t,int k)
{
return (int)(pow(2,t-k+1)-1);
}
//希尔排序
void shellSort(int array[],int n,int t)
{
void shellInsert(int array[],int n,int dk);
int i;
for(i=1;i<=t;i++)
shellInsert(array,n,dkHibbard(t,i));
}
//此写法便于理解，实际应用时应将上述三个函数写成一个函数。
C++
template <typename _RIter>
void insert_sort(_RIter st, _RIter ed, int delta) {
for(_RIter i = st + delta; i < ed; i += delta) {
for(_RIter j = i; j > st; j -= delta)
if(*j < *(j - delta)) std::swap(*j, *(j - delta));
else break;
}
}
template <typename _RIter>
void shell_sort(_RIter st, _RIter ed) {
for(int delta = ed - st; delta; delta /= 2)
for(int i = 0; i < delta; i++)
insert_sort(st + i, ed, delta);
}
AS3
//需要排序的数组
var arr:Array = [7, 5, 8, 4, 0, 9];
var small:int;//最小下标
var temp:int;
for(var i:int = 0; i < arr.length; i++){
small = i;
for(var j:int = i + 1; j < arr.length + 1; j++){
if(arr[j] < arr[small]){
small = j;
}
}
if(small != i){
temp = arr[i];
arr[i] = arr[small];
arr[small] = temp;
}
trace(arr[i]);
}
Ruby
def shell_sort(array)
gap = array.size
while gap > 1
gap = gap / 2
(gap..array.size-1).each do |i|
j = i
while j > 0
array[j], array[j-gap] = array[j-gap], array[j] if array[j] <= array[j-gap]
j -= gap
end
end
end
array
end
PHP
function shell_sort(&$arr) {
if(!is_array($arr)) return;
$n = count($arr);
for ($gap = floor($n/2); $gap > 0; $gap = floor($gap/=2)) {
for($i = $gap; $i < $n; ++$i) {
for($j = $i - $gap; $j >= 0 && $arr[$j + $gap] < $arr[$j]; $j -= $gap) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + $gap];
$arr[$j + $gap] = $temp;
}
}
}
}
Python3.x
def shell_sort(seq):
"""
希尔排序
思想：通过控制增量将序列分组，组内直接插入排序完再缩小增量再分组排序，
如8个序列，最初增量为8/2=4，所以1~4为一组，5~8为一组，1-5比较、2-6比较、
3-7比较、4-8比较，此时组内比较再增量/2分组，直到最后增量为1时排序次数就少很多
:param seq: 待排序的序列
:return:
"""
seq_len = len(seq)
step = seq_len >> 1
# 增量小于1说明最终排序已完成
while step:
for i in range(step, seq_len):
# j记录元素原始位置，用于查找前面所有小于当前元素的元素
j = i
while seq[j] < seq[j-step] and j-step >= 0:
seq[j], seq[j-step] = seq[j-step], seq[j]
# 改变下标，查看前面是否还有更小的值
j -= step
print(f"增量{step}的排序：", seq)
# 每次增长减小一半
step = step >> 1
Objective-C
+ (NSArray *)shellSort:(NSArray *)unsortDatas {
NSMutableArray *unSortArray = [unsortDatas mutableCopy];
int len = (int)unSortArray.count;
for (int gap = floor(len / 2); gap > 0; gap = floor(gap/2)) {
for (int i = gap; i < len; i++) {
for (int j = i - gap; j >= 0 && [unSortArray[j] integerValue] > [unSortArray[j+gap] integerValue]; j-=gap) {
NSNumber *temp = unSortArray[j];
unSortArray[j] = unSortArray[gap+j];
unSortArray[gap+j] = temp;
}
}
}
return [unSortArray copy];
}
Rust
pub fn shell_sort(nums:&Vec<i32>)->Vec<i32>{
let mut nums = nums.to_vec();
fn insertion(nums: &mut Vec<i32>, start: usize, gap: usize) {
for i in ((start + gap)..nums.len()).step_by(gap) {
let val_current = nums[i];
let mut pos = i;
// make swaps
while pos >= gap && nums[pos - gap] > val_current {
nums[pos] = nums[pos - gap];
pos = pos - gap;
}
nums[pos] = val_current;
}
}
let mut count_sublist = nums.len() / 2; // makes gap as long as half of the array
while count_sublist > 0 {
for pos_start in 0..count_sublist {
insertion(&mut nums, pos_start, count_sublist);
}
count_sublist /= 2; // makes gap as half of previous
}
return nums
}
研究进展
播报编辑
希尔排序的正确性对软件可靠性至关重要。已有研究采用形式化方法，借助Frama-C平台及其ACSL规范语言，对希尔排序程序进行源代码级别的正确性验证。验证过程中的主要难点在于构造嵌套循环的循环不变式。通过设计合适的循环不变式，并借助Alt-Ergo、CVC4、Z3等定理证明器进行验证，最终证明了希尔排序程序的功能正确性与内存安全性。
排序过程
播报编辑
缩小增量
三趟结果
04 13 27 38 49 49 55 65 76 97
Shell排序
Shell排序的算法实现:
1． 不设监视哨的算法描述
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d为当前增量
for(i=d+1;i
if(R[ i ].key
R[0]=R[i];j=i-d； //R[0]只是暂存单元，不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]； //后移记录
j=j-d； //查找前一记录
}while(j＞0&&R[0].key
R[j+d]=R[0]； //插入R到正确的位置上
} //endif
算法分析
播报编辑
优劣
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间的时间复杂度为O(
时间性能
1．增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了较好的结果：当n较大时，比较和移动的次数约在n^1.25到(1.6n)^1.25之间。
2．Shell排序的时间性能优于直接插入排序
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插入排序有较大的改进。
