Lwaxx的博客

十大排序算法（十） - 希尔排序算法

发表于 分类于 ， 阅读次数： Valine：

希尔排序（Shell Sort）是一种插入排序的改进算法，它通过比较相距一定间隔的元素进行排序，逐步减小间隔，最终实现整体有序。本文将详细介绍希尔排序的工作原理，提供示例和Python、Go、Java以及C语言的实现代码。

希尔排序的基本思想

希尔排序的核心思想是将整个待排序序列分割成若干个子序列，分别对这些子序列进行插入排序，然后逐步减小子序列的间隔，直到间隔为1，最终对整个序列进行一次插入排序。这样，插入排序的效率会得到大幅提升。

具体步骤如下：

  1. 确定间隔序列： 选择一个间隔序列，一般是逐步减半，直到间隔为1。
  2. 间隔排序： 对间隔序列所对应的子序列进行插入排序。
  3. 逐步缩小间隔： 重复第二步，逐步减小间隔，直到间隔为1，完成最终的插入排序。

希尔排序的示例

让我们通过一个示例来理解希尔排序的工作原理。假设我们有一个整数数组 [12, 34, 54, 2, 3]，我们希望按升序排序它。

  1. 选择间隔序列： 假设我们选择间隔序列为 [2, 1]。
  2. 间隔为2的排序： 分别对间隔为2的子序列进行插入排序。
    • 第一轮：[12, 3] [34, 2] [54]
  3. 间隔为1的排序： 对整个序列进行一次插入排序。
    • 第二轮：[3, 2, 12, 34, 54]
      最终，我们得到了排序后的数组 [2, 3, 12, 34, 54]。

希尔排序的时间复杂度

希尔排序的时间复杂度取决于间隔序列的选择。一般来说，间隔序列的选择直接影响到希尔排序的性能。

  1. 最好情况时间复杂度： O(n log n)
  2. 平均情况时间复杂度： 取决于间隔序列
  3. 最坏情况时间复杂度： O(n^2)

希尔排序是一种不稳定的排序算法，适用于中等大小的数据集。它是插入排序的改进版本，通过减小元素移动的距离来提高排序效率。

示例代码

以下是希尔排序的示例代码，分别使用Python、Go、Java和C语言编写。

Python 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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

arr = [12, 34, 54, 2, 3]
shell_sort(arr)
print("排序后的数组:", arr)

Go 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
package main

import "fmt"

func shellSort(arr []int) {
	n := len(arr)
	gap := n / 2

	for gap > 0 {
		for i := gap; i < n; i++ {
			temp := arr[i]
			j := i

			for j >= gap && arr[j-gap] > temp {
				arr[j] = arr[j-gap]
				j -= gap
			}

			arr[j] = temp
		}

		gap /= 2
	}
}

func main() {
	arr := []int{12, 34, 54, 2, 3}
	shellSort(arr)
	fmt.Println("排序后的数组:", arr)
}

Java 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.util.Arrays;

public class ShellSort {
    public static void shellSort(int arr[]) {
        int n = arr.length;
        int gap = n / 2;

        while (gap > 0) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;

                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }

                arr[j] = temp;
            }

            gap /= 2;
        }
    }

    public static void main(String[] args) {
        int arr[] = {12, 34, 54, 2, 3};
        shellSort(arr);
        System.out.print("排序后的数组: ");
        System.out.println(Arrays.toString(arr));
    }
}

C 语言 希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>

void shellSort(int arr[], int n) {
    int gap = n / 2;

    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j = i;

            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }

            arr[j] = temp;
        }

        gap /= 2;
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);
    shellSort(arr, n);
    printf("排序后的数组: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

以上示例代码展示了不同编程语言中的希尔排序算法实现。这些示例帮助你理解希尔排序的工作原理，并提供了可供参考和使用的代码示例。希尔排序是一种高效的排序算法，可以在大多数情况下获得不错的性能。