C语言常见排序算法之插入排序(直接插入排序,希尔排序)

接下来我将为大家详细讲解“C语言常见排序算法之插入排序(直接插入排序, 希尔排序)”。

直接插入排序

算法思路

直接插入排序算法的实现思路是：将一个无序的数据序列分为一个有序子序列和一个无序子序列两部分，将无序子序列的元素一个一个插入到有序子序列中，直到插入完所有元素，最终形成一个新的有序序列。在具体编写代码时，我们会将数据序列看作是一个数组来进行操作。

代码实现

下面是一个 C 语言版本的实现示例：

void InsertionSort(int arr[], int len) {
    int i, j, key;
    for (i = 1; i < len; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

示例说明

我们来看一下具体的示例：

假设有一个整数数组 arr，初始值为 [6, 3, 5, 2, 4, 1]，按照直接插入排序算法的思路，我们需要将其排序为一个新的有序数组。

排序的过程如下：

1. 初始序列：[6, 3, 5, 2, 4, 1]
2. 第一轮排序：将 3 插入到已排序的子序列中，使其有序。序列变为：[3, 6, 5, 2, 4, 1]
3. 第二轮排序：将 5 插入到已排序的子序列中，使其有序。序列变为：[3, 5, 6, 2, 4, 1]
4. 第三轮排序：将 2 插入到已排序的子序列中，使其有序。序列变为：[2, 3, 5, 6, 4, 1]
5. 第四轮排序：将 4 插入到已排序的子序列中，使其有序。序列变为：[2, 3, 4, 5, 6, 1]
6. 第五轮排序：将 1 插入到已排序的子序列中，使其有序。序列变为：[1, 2, 3, 4, 5, 6]

最终得到的排序好的数组为 [1, 2, 3, 4, 5, 6]。

希尔排序

算法思路

希尔排序是插入排序的一种更高效的改进版本。它的基本思路是：将待排序的数据分成若干个子序列，分别进行插入排序。待整个序列中的元素基本有序时，再对全体元素进行插入排序。在具体编写代码时，我们也会将数据序列看作是一个数组来进行操作。

代码实现

下面是一个 C 语言版本的实现示例：

void ShellSort(int arr[], int len) {
    int i, j, gap;
    int temp;
    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;
        }
    }
}

示例说明

我们来看一下具体的示例：

假设有一个整数数组 arr，初始值为 [6, 3, 5, 2, 4, 1]，按照希尔排序算法的思路，我们需要将其排序为一个新的有序数组。

排序的过程如下：

1. 初始序列：[6, 3, 5, 2, 4, 1]
2. 第一轮排序：将元素间隔为 3 的子序列排序，得到序列：[2, 3, 1, 6, 4, 5]
3. 第二轮排序：将元素间隔为 1 的子序列排序，得到序列：[1, 2, 3, 4, 5, 6]

最终得到的排序好的数组为 [1, 2, 3, 4, 5, 6]。

希尔排序的优势在于它可以在比较少的操作次数内将一个序列的元素进行排序，从而实现高效率的排序。在实际应用中，希尔排序被广泛地应用于各种需要对大规模数据进行排序的场景中。