C语言直接插入排序与希尔排序如何使用

在C语言中，排序算法是数据处理中非常重要的一部分。直接插入排序和希尔排序是两种常见的排序算法，它们各有特点，适用于不同的场景。本文将详细介绍这两种排序算法的原理及其在C语言中的实现方法。

1. 直接插入排序

1.1 算法原理

直接插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理类似于我们整理扑克牌的方式：每次从未排序的部分取出一个元素，将其插入到已排序部分的适当位置，直到所有元素都被排序。

1.2 算法步骤

1. 从第一个元素开始，该元素可以认为已经被排序。
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。
3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
5. 将新元素插入到该位置后。
6. 重复步骤2~5，直到所有元素都被排序。

1.3 C语言实现

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 将大于key的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, n);
    printArray(arr, n);

    return 0;
}

1.4 时间复杂度

• 最坏情况：O(n^2)
• 最好情况：O(n)（当数组已经有序时）
• 平均情况：O(n^2)

2. 希尔排序

2.1 算法原理

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，也称为缩小增量排序。它通过将原始数组分割成若干子序列，分别进行直接插入排序，随着增量逐渐减小，最终对整个数组进行一次直接插入排序。

2.2 算法步骤

1. 选择一个增量序列 t1, t2, …, tk，其中 ti > tj, tk = 1。
2. 按增量序列个数 k，对序列进行 k 趟排序。
3. 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。
4. 仅增量因子为1时，整个序列表来处理，表长度即为整个序列的长度。

2.3 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[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    shellSort(arr, n);
    printArray(arr, n);

    return 0;
}

2.4 时间复杂度

• 最坏情况：O(n^2)（取决于增量序列的选择）
• 最好情况：O(n log n)
• 平均情况：O(n log n)

3. 总结

直接插入排序和希尔排序都是基于插入排序的算法，但希尔排序通过引入增量序列，使得排序效率得到了显著提升。直接插入排序适用于小规模数据或部分有序的数据，而希尔排序则适用于中等规模的数据集。在实际应用中，选择合适的排序算法可以大大提高程序的运行效率。