手写插入排序算法

实力程序员

关注

发布于: 2 小时前

今天给大家介绍插入排序算法，并且给出源码实现。

插入排序算法的思想是，对于一个包含 N 个未排序元素的数组，我们可以从位置 1 开始，通过比较元素 1 和元素 0，把元素 1 插入到元素 0 的前面或者后面，实现这两个元素的有序排列。

然后再取元素 2，这个元素前面的序列都已经是有序的了，因此只要找到元素 2 在前面序列中的位置，进行插入，那么元素 0 至元素 2 就都排好序了。

再取元素 3，向前面有序序列进行插入,依次进行，一直到最后一个 N-1 元素插入完成，这样整个数组就都排好序了。

因此，插入算法的核心步骤是查找和插入。

查找，可以通过遍历比较，也可以通过二分法进行查找。

插入，对于内存位置连续的数组，可以直接用 memmove, 内存位置不连续的只能逐个元素进行位置交换。

插入排序算法的思路比较容易理解，用 C 语言的代码实现如下：

void insert_sort(int* parr, int count) {    for (int i = 1; i < count; i++) {        int val = parr[i];        int pos = get_insert_pos(parr, i, val);        if (pos != i) {            memmove(parr + pos + 1, parr + pos, (i - pos) * sizeof(int));            parr[pos] = val;        }    }}

复制代码

用遍历方式实现的 get_insert_pos() 函数，如下：

static int get_insert_pos(int* parr, int count, int val) {    for (int i = 0; i < count; i++) {        if (parr[i] > val) {    // the first bigger item            return i;        }    }
    return count;   // val is the biggest one}

复制代码

更快的方式，是用二分法进行查找，代码如下：

static int get_insert_pos(int* parr, int count, int val) {    int low = 0;    int high = count - 1;    while (low < high) {        int mid = (low + high) / 2;        if (parr[mid] > val) {            high = mid - 1;        } else {            low = mid + 1;        }    }
    return parr[low] > val ? low : low + 1;}

复制代码

我的微信号是实力程序员，欢迎大家转发至朋友圈，分享给更多的朋友。

发布于: 2 小时前阅读数: 2

原文链接:【http://xie.infoq.cn/article/ad27f0a3c0a64ecf3aabe3b35】。

实力程序员

关注

实力程序员，用实力说话！ 2021.05.24 加入

超过20年一线产品研发和技术管理的实力程序员

发布

暂无评论

创作场景

手写插入排序算法

实力程序员

评论