C语言直接插入排序


直接插入排序是一种简单的排序算法,算法思想是将未排序的数据依次插入到已经排序的数据中,从而得到一个完全有序的序列。下面是一个使用 C 语言实现的直接插入排序算法:

void insertion_sort(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;
    }
}

解释一下这段代码:

首先,我们定义了一个 insertion_sort 函数,它接受一个整数数组 arr 和数组长度 len 作为参数。

然后,我们在函数内部定义了一些变量,包括 i,j 和 key。

i 表示未排序部分的第一个元素的下标,也就是当前要插入的元素,初始值为 1。

key 是当前要插入的元素的值,它将在排序过程中被不断移动。

j 则表示已排序部分的最后一个元素的下标,初始值为 i - 1。

接下来,我们进入排序的主循环。循环从 i = 1 开始,一直到 i < len,也就是未排序部分的最后一个元素。

在循环内部,我们通过赋值操作将 arr[i] 的值保存到 key 中,这样就可以在后面的操作中不断移动 key。

接着,我们用 j 从 i - 1 开始向前遍历已排序部分,将所有大于 key 的元素都向后移动一位。

最终,我们将 key 插入到正确的位置上,也就是 j + 1 的位置。

外层循环不断执行,最终实现了整个数组的排序。

需要注意的是,这里的直接插入排序采用的是升序排序。如果需要降序排序,只需将 while 循环中的条件改为 arr[j] < key 即可。