C程序 插入排序

下面是关于"C程序 插入排序"的完整使用攻略。

插入排序是什么？

插入排序是一种简单直观的、比较常用的排序算法。其基本思想是将待排序的数组分成两部分，已排序和未排序，然后将未排序的元素一个一个插入到已排序部分的正确位置上，直到整个数组都被排序。

插入排序的实现

下面是一份C程序的插入排序实现，以进行升序排序为例。

#include <stdio.h>

void insertion_sort(int arr[], int n) {
    int i, j, key;

    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

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

    insertion_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

插入排序的示例解析

我们来看一个使用插入排序的示例：如何对一个整数数组进行排序。

示例一

假设有一个未排序的整数数组：[ 12, 11, 13, 5, 6 ]。

1. 首先，将第一个元素（12）视为已排序数组，将第二个元素（11）视为未排序数组。
2. 比较11和12，发现11比12小，将11插入到已排序数组的第一个位置，得到已排序数组为：[ 11, 12 ]，未排序数组为：[ 13, 5, 6 ]。
3. 将第三个元素（13）视为未排序数组，将它和已排序数组中的每一个元素进行比较。发现13比12大，于是13插入到已排序数组的第二个位置，得到已排序数组为：[ 11, 12, 13 ]，未排序数组为: [ 5, 6 ]。
4. 将第四个元素（5）插入到已排序数组中。由于它比已排序数组中所有的元素都要小，因此将5插入到已排序数组的第一个位置，得到已排序数组为：[ 5, 11, 12, 13 ]，未排序数组为：[ 6 ]。
5. 最后，将最后一个元素（6）插入到已排序数组。将6和已排序数组中的元素进行比较，发现6比11小，于是将6插入到已排序数组的第二个位置，得到已排序数组为：[ 5, 6, 11, 12, 13 ]，未排序数组为空。
6. 数组已经排序完成。

示例二

还有一个示例是对字母数组进行排序，文字表述略有些不便，我们这里就直接通过代码来举例：

#include <stdio.h>

void insertion_sort(char arr[], int n) {
    int i, j;
    char key;

    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    char arr[] = { 'd', 'a', 'c', 'b', 'e' };
    int n = sizeof(arr) / sizeof(char);

    insertion_sort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%c ", arr[i]);
    }
    printf("\n");
    return 0;
}

上面的代码使用插入排序对字母数组进行排序。运行结果如下：

Sorted array: a b c d e

结论

以上就是C程序插入排序的完整使用攻略，包含了对算法的解释、代码的说明以及两个排序示例的详细解析。希望对你有所帮助！