十大经典排序算法——希尔排序

选择一个增量序列（gap sequence），用于将列表分成若干子列表。：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。：当增量为 1 时，对整个列表进行一次插入排序，完成排序。：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。O(1)，希尔排序是原地排序算法，不需要额外的存储空间。：O(n log n)，当增量序列选择合适时。：O(n log n) 到 O(n²) 之间。，时

—————————————————

974人浏览 · 2025-07-22 10:08:12

————————————————— · 2025-07-22 10:08:12 发布

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为缩小增量排序。它通过将待排序的列表分成若干子列表，对每个子列表进行插入排序，逐步缩小子列表的间隔，最终完成整

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录"基本有序"时，再对全体记录进行依次直接插入排序。

一、算法步骤

选择增量序列：选择一个增量序列（gap sequence），用于将列表分成若干子列表。常见的增量序列有希尔增量（n/2, n/4, ..., 1）等。
分组插入排序：按照增量序列将列表分成若干子列表，对每个子列表进行插入排序。
缩小增量：逐步缩小增量，重复上述分组和排序过程，直到增量为 1。
最终排序：当增量为 1 时，对整个列表进行一次插入排序，完成排序。

二、动图演示

（上图位插入排序，下图是希尔排序）

假设有一个待排序的列表 [8, 3, 1, 2, 7, 5, 6, 4]，使用希尔增量（初始增量为 n/2），排序过程如下：

初始状态：
- 列表：[8, 3, 1, 2, 7, 5, 6, 4]。
- 初始增量：4（列表长度 8 的一半）。
第一轮（增量为 4）：
- 将列表分成 4 个子列表：
  - 子列表 1：[8, 7]。
  - 子列表 2：[3, 5]。
  - 子列表 3：[1, 6]。
  - 子列表 4：[2, 4]。
- 对每个子列表进行插入排序：
  - 子列表 1：[7, 8]。
  - 子列表 2：[3, 5]。
  - 子列表 3：[1, 6]。
  - 子列表 4：[2, 4]。
- 排序后的列表：[7, 3, 1, 2, 8, 5, 6, 4]。
第二轮（增量为 2）：
- 将列表分成 2 个子列表：
  - 子列表 1：[7, 1, 8, 6]。
  - 子列表 2：[3, 2, 5, 4]。
- 对每个子列表进行插入排序：
  - 子列表 1：[1, 6, 7, 8]。
  - 子列表 2：[2, 3, 4, 5]。
- 排序后的列表：[1, 2, 6, 3, 7, 4, 8, 5]。
第三轮（增量为 1）：
- 将整个列表视为一个子列表，进行插入排序。
- 排序后的列表：[1, 2, 3, 4, 5, 6, 7, 8]。

三、代码实现

实例

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始增量
    while gap > 0:
        # 对每个子列表进行插入排序
        for i in range(gap, n):
            temp = arr[i]  # 当前待插入元素
            j = i
            # 在子列表中找到合适的位置插入
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # 缩小增量
    return arr

# 示例
arr = [8, 3, 1, 2, 7, 5, 6, 4]
sorted_arr = shell_sort(arr)
print(sorted_arr)  # 输出: [1, 2, 3, 4, 5, 6, 7, 8]

JavaScript

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) {          //动态定义间隔序列
        gap =gap*3+1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
                arr[j+gap] = arr[j];
            }
            arr[j+gap] = temp;
        }
    }
    return arr;
}

Python

def shellSort(arr):
    import math
    gap=1
    while(gap < len(arr)/3):
        gap = gap*3+1
    while gap > 0:
        for i in range(gap,len(arr)):
            temp = arr[i]
            j = i-gap
            while j >=0 and arr[j] > temp:
                arr[j+gap]=arr[j]
                j-=gap
            arr[j+gap] = temp
        gap = math.floor(gap/3)
    return arr

Go

func shellSort(arr []int) []int {
        length := len(arr)
        gap := 1
        for gap < length/3 {
                gap = gap*3 + 1
        }
        for gap > 0 {
                for i := gap; i < length; i++ {
                        temp := arr[i]
                        j := i - gap
                        for j >= 0 && arr[j] > temp {
                                arr[j+gap] = arr[j]
                                j -= gap
                        }
                        arr[j+gap] = temp
                }
                gap = gap / 3
        }
        return arr
}

Java

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

PHP

function shellSort($arr)
{
    $len = count($arr);
    $temp = 0;
    $gap = 1;
    while($gap < $len / 3) {
        $gap = $gap * 3 + 1;
    }
    for ($gap; $gap > 0; $gap = floor($gap / 3)) {
        for ($i = $gap; $i < $len; $i++) {
            $temp = $arr[$i];
            for ($j = $i - $gap; $j >= 0 && $arr[$j] > $temp; $j -= $gap) {
                $arr[$j+$gap] = $arr[$j];
            }
            $arr[$j+$gap] = $temp;
        }
    }
    return $arr;
}

C

void shell_sort(int arr[], int len) {
        int gap, i, j;
        int temp;
        for (gap = len >> 1; gap > 0; gap >>= 1)
                for (i = gap; i < len; i++) {
                        temp = arr[i];
                        for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
                                arr[j + gap] = arr[j];
                        arr[j + gap] = temp;
                }
}

C++

template<typename T>
void shell_sort(T array[], int length) {
    int h = 1;
    while (h < length / 3) {
        h = 3 * h + 1;
    }
    while (h >= 1) {
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h && array[j] < array[j - h]; j -= h) {
                std::swap(array[j], array[j - h]);
            }
        }
        h = h / 3;
    }
}

C#

static void ShellSort(int[] arr)
{
    int gap = 1;

    while (gap < arr.Length)
    {
        gap = gap * 3 + 1;
    }

    while (gap > 0)
    {
        for (int i = gap; i < arr.Length; i++)
        {
            int tmp = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > tmp)
            {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = tmp;
        }
        gap /= 3;
    }
}

Rust

fn shell_sort<T: Ord + Debug>(array: &mut [T]) {
    let mut grad = [1, 3, 5];
    grad.reverse();
    for step in grad {
        insert_sort_step(array, step)
    }
}

fn insert_sort_step<T: Ord + Debug>(array: &mut [T], step: usize) {
    for i in (0..array.len()).step_by(step) {
        for j in (0..i).step_by(step).rev() {
            if array[j + step] < array[j] {
                array.swap(j + step, j);
            } else {
                break;
            }
        }
    }
}