C语言深入探究直接插入排序与希尔排序使用案例讲解

直接插入排序

算法描述

直接插入排序的基本思想是将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数增加1的有序表。具体算法流程如下：

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

代码示例

下面是一个C语言的直接插入排序算法实现。

void insertion_sort(int arr[], int len) {
    int i, j, temp;

    for (i = 1; i < len; i++) {
        temp = arr[i];

        for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
            arr[j + 1] = arr[j];
        }

        arr[j + 1] = temp;
    }
}

使用示例

下面是一个使用直接插入排序对一个整型数组进行排序的样例代码。假设数组元素为{9, 3, 4, 6, 1, 8, 7, 2, 5}，排序后应该得到{1, 2, 3, 4, 5, 6, 7, 8, 9}。

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

    insertion_sort(arr, len);

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

    printf("\n");

    return 0;
}

输出结果：

1 2 3 4 5 6 7 8 9 

希尔排序

算法描述

希尔排序是插入排序的一种改进，区别在于它会对序列进行多次的插入排序，并且每次排序的序列会以一定间隔进行分组。希尔排序的基本思想是将一个大的序列分成若干个子序列，对每个子序列进行插入排序，然后逐步减小子序列的间隔，再次进行插入排序，直到子序列的间隔为1时，整个序列进行一次插入排序，排序完成。具体算法流程如下：

1. 将序列按照一定间隔分为若干个子序列
2. 对每个子序列分别进行直接插入排序
3. 逐步缩小子序列的间隔直至为1
4. 对整个序列进行一次插入排序

代码示例

下面是一个C语言的希尔排序算法实现。

void shell_sort(int arr[], int len) {
    int i, j, temp, gap;

    for (gap = len / 2; gap > 0; gap /= 2) {
        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;
        }
    }
}

使用示例

下面是一个使用希尔排序对一个整型数组进行排序的样例代码。假设数组元素为{9, 3, 4, 6, 1, 8, 7, 2, 5}，排序后应该得到{1, 2, 3, 4, 5, 6, 7, 8, 9}。

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

    shell_sort(arr, len);

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

    printf("\n");

    return 0;
}

输出结果：

1 2 3 4 5 6 7 8 9 

通过使用上面的代码示例，可以看到，希尔排序相对于直接插入排序在效率上有更好的表现。