手写插入排序算法
【摘要】 今天给大家介绍插入排序算法,并且给出源码实现。插入排序算法的思想是,对于一个包含N个未排序元素的数组,我们可以从位置1开始,通过比较元素1和元素0,把元素1插入到元素0的前面或者后面,实现这两个元素的有序排列。然后再取元素2,这个元素前面的序列都已经是有序的了,因此只要找到元素2在前面序列中的位置,进行插入,那么元素0至元素2就都排好序了。再取元素3,向前面有序序列进行插入,依次进行,一直到...
今天给大家介绍插入排序算法,并且给出源码实现。
插入排序算法的思想是,对于一个包含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;
}
我的微信号是 实力程序员,欢迎大家转发至朋友圈,分享给更多的朋友。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)