首页 > 编程笔记 > 算法

C语言希尔排序(附带源码和解析)

希尔排序是一种高效的排序算法,由 Donald Shell 于 1959 年提出。这种算法是插入排序的一种更高效的改进版本。希尔排序的核心思想是将整个待排序的序列分割成若干子序列,然后分别进行直接插入排序,以此达到减少排序时间的目的。

希尔排序的基本原理

希尔排序的工作原理可以分为以下几个步骤:

  1. 选择一个增量序列 t1, t2, ..., tk,其中 ti > tj(i < j),tk = 1;
  2. 按增量序列个数 k,对序列进行 k 趟排序;
  3. 每趟排序,根据对应的增量 ti,将待排序列分割成若干长度为 m 的子序列,分别对各子表进行直接插入排序。


希尔排序的关键在于增量序列的选择。常见的增量序列有希尔增量、Hibbard 增量、Sedgewick 增量等。在本文中,我们将使用希尔增量,即每次将增量缩小为原来的一半,直到增量为 1。


让我们通过一个具体的例子来理解希尔排序的工作过程。假设我们有以下待排序的数组:

[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]

我们选择初始增量为数组长度的一半,即 5。


第一趟排序(增量为 5):

[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
 |        |        |
 8        3        0
    |        |        |
    9        5        6
       |        |
       1        4
          |        |
          7        6
             |
             2

排序后:[3, 5, 1, 6, 2, 8, 9, 4, 7, 0]

第二趟排序(增量为 2):

[3, 5, 1, 6, 2, 8, 9, 4, 7, 0]
 |  |  |  |  |
 3  5  1  6  2
    |  |  |  |  |
    5  1  6  2  0

排序后:[1, 2, 3, 4, 0, 5, 7, 6, 9, 8]

第三趟排序(增量为 1,即普通插入排序):

[1, 2, 3, 4, 0, 5, 7, 6, 9, 8]

排序后:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

C语言实现希尔排序

下面是希尔排序的 C 语言实现:

#include <stdio.h>

void shellSort(int arr[], int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组: ");
    printArray(arr, n);

    shellSort(arr, n);

    printf("排序后数组: ");
    printArray(arr, n);

    return 0;
}

运行结果:

原始数组: 8 9 1 7 2 3 5 4 6 0
排序后数组: 0 1 2 3 4 5 6 7 8 9

希尔排序的性能和优缺点

希尔排序的时间复杂度与增量序列的选择有关。在最坏情况下,希尔排序的时间复杂度为 O(n²),但在平均情况下,其时间复杂度为 O(n^1.3)。相比于简单插入排序的 O(n²),希尔排序在处理大规模数据时表现更为出色。
 

希尔排序的优点包括:


希尔排序的缺点包括:

总结

希尔排序是一种高效的排序算法,它通过将待排序序列分割成若干子序列进行插入排序,从而提高了排序的效率。虽然其时间复杂度不如一些更先进的排序算法(如快速排序、归并排序),但在处理中等规模数据时,希尔排序仍然是一个不错的选择。


你可能还想关注其它 9 种排序算法:

  1. C语言冒泡排序(附带源码和解析)
  2. C语言快速排序(附带源码和解析)
  3. C语言选择排序(附带源码和解析)
  4. C语言插入排序(附带源码和解析)
  5. C语言归并排序(附带源码和解析)
  6. C语言堆排序(附带源码和解析)
  7. C语言计数排序(附带源码和解析)
  8. C语言桶排序(附带源码和解析)
  9. C语言基数排序(附带源码和解析)

声明:《算法系列教程》为本站“54笨鸟”官方原创,由国家机构和地方版权局所签发的权威证书所保护。