数据结构---插入类排序（直接插入排序、折半插入排序、希尔排序，C语言）

118 阅读 0 评论 78 点赞

我是靠谱客的博主迷你小霸王，这篇文章主要介绍数据结构---插入类排序（直接插入排序、折半插入排序、希尔排序，C语言），现在分享给大家，希望可以做个参考。

插入类排序有直接插入排序、折半插入排序、希尔排序

直接插入排序

算法思想：每趟将一个待排序的关键字按照其值的大小插入到已经排好的部分有序序列的适当位置上，直到所有待排关键字都被插入到有序序列中为止。

工作流程：1）查找出待插入元素应该被插入的位置 2）给插入位置腾出空间，将待插入元素复制到表中的插入位置。

是边比较边移动元素的。

本算法的时间复杂度为：O(n2)

复制代码

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
38
39
40
41
42
43
44
45
46
#include <stdio.h>
#include <malloc.h>
#define maxSize 100
int R[maxSize] = { 0 };
int count = 0;
void Indata()
{
	int i = 0;
	printf("请输入整数数据(按回车键结束输入):");
	while (1)
	{
		scanf_s("%d", &R[i]);
		i++;
		count++;
		char c = getchar();
		if ('n' == c)
			break;
	}
}

void InsertSort(int r[], int n)
{
	int i, j;
	int temp;
	for (i = 1; i < n; i++)
	{
		temp = r[i];     //将待插入关键字暂存于temp中
		j = i - 1;
		while (j >= 0 && temp < r[j])
		{
			r[j + 1] = r[j];
			--j;
		}
		r[j + 1] = temp;
	}
	printf("n直接插入排序后序列为:");
	for (i = 0; i < n; i++)
		printf("%d ", r[i]);
}

void main()
{
	 Indata();
	 InsertSort(R, count);
	 system("pause");
}

折半插入排序

和直接插入排序是类似的，只是将比较和移动操作分离出来。即先折半查找出元素的待插入位置，然后再统一地移动待插入位置之后的所有元素

复制代码

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
/***********折半插入排序*************/
void InsertSort2(int r[], int n)
{
	int i, j, low, high, mid;
	int temp;
	for (i = 1; i < n; i++)
	{
		temp = r[i];
		low = 0; high = i - 1;
		//找到位置
		while (low <= high)
		{
			mid = (low + high) / 2;
			if (temp < r[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
		//插入
		for (j = i - 1; j >= high + 1; j--)
			r[j + 1] = r[j];
		r[high + 1] = temp;
	}
	for (i = 0; i < n; i++)
		printf("%d ", r[i]);
}

希尔排序

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/***********希尔排序***********/
void ShellSort(int r[], int n)
{
	int i, j, temp, gap;
	int m;
	for (gap = n / 2; gap > 0; gap = gap / 2)
	{
		for (i = gap; i < n; i++)
		{
			temp = r[i];
			for (j = i; j >= gap && r[j - gap] > temp; j -= gap)
				r[j] = r[j - gap];
			r[j] = temp;
		}
	}
	for (m = 0; m < n; m++)
		printf("%d ", r[m]);
}