排序算法（三）直接插入排序与折半插入排序一、什么是插入类排序？二、需要了解的几类插入类排序算法。

131 阅读 0 评论 87 点赞

我是靠谱客的博主鲤鱼铅笔，这篇文章主要介绍排序算法（三）直接插入排序与折半插入排序一、什么是插入类排序？二、需要了解的几类插入类排序算法。，现在分享给大家，希望可以做个参考。

一、什么是插入类排序？

插入类排序默认有一个已经排好序的序列，而后面的操作就是将未排好序的元素有序插入到已排好序的序列中。

将所有未排好序的元素插入到合适位置，即可得到一个有序序列。

二、需要了解的几类插入类排序算法。

（1）、直接插入排序

直接插入排序是一种基本的插入排序算法。算法思路很简单！以升序为例：

<1>、将序列的第一个元素看成一个有序序列（任何一个单元素都可以看成有序序列）。

<2>、从第二个元素开始向后遍历。将第二个元素插入到第一个元素的前面（如果比第一个元素小），否则位置不变。

<3>、然后继续看第三个元素，此时前两个元素是按升序有序的。将第三个元素按顺序和第二个元素、第一个元素进行比较，将其放入合适的位置。

<4>、直到最后一个元素也被放入前面的有序序列的合适位置，那么排序完成。

过程如下图 :

直接插入排序源代码 :

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
**功能: 直接插入法升序排序一个序列
**参数说明:
**@record : 序列数组 @len : 序列长度
**返回值: 无
*/
void InsertSort(int record[], int len)
{
	int i, j;
	int value;   //存储待插入元素值

	//从第二个元素开始插入排序，第一个元素默认是有序的
	for (i = 1; i < len;i++)
	{
		value = record[i];

		//寻找合适的插入位置
		j = i - 1;
		while (j >= 0 && record[j] >= value)
		{
			record[j + 1] = record[j];
			j--;
		}

		//将待排元素插入到合适的位置
		record[j + 1] = value;
	}
}

（2）、折半插入排序

折半插入与直接插入很像！唯一的区别在于它寻找插入位置的方法不同，直接插入是对有序表进行顺序遍历查找，而折半插入中的“折半”就体现在此处，它寻找插入位置是进行折半查找。大大增加了查找效率，但未改变移动元素的时间耗费。

折半插入排序源代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void BinSort(int record[], int len)
{
	int i, j;
	int value;   //存储待插入元素值
	int low, high, mid;  //用于折半查找的变量

	//从第二个元素开始插入排序，第一个元素默认是有序的
	for (i = 1; i < len;i++)
	{
		value = record[i];

		//折半法寻找插入位置
		low = 0;
		high = i - 1;
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (value < record[mid])
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}

		//移动元素，为放置待排元素腾位置
		for (j = i - 1; j >= low;j--)
		{
			record[j + 1] = record[j];
		}

		//将待排元素插入到合适的位置
		record[low] = value;
	}
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int main(void)
{
	int record[] = { 48,62,35,77,55,14,35,98 };
	int len = sizeof(record) / sizeof(record[0]);
	int i = 0;

	printf("排序前: n");
	for (i = 0;i < len;i++)
	{
		printf("%d  ", record[i]);
	}
	puts("");

	BinSort(record, len);

	printf("排序后: n");
	for (i = 0;i < len;i++)
	{
		printf("%d  ", record[i]);
	}
	puts("");

	return 0;
}