直接插入排序是一种简单的排序算法,算法思想是将未排序的数据依次插入到已经排序的数据中,从而得到一个完全有序的序列。下面是一个使用 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 即可。