c语言实现【希尔排序】：数据结构最后一章排序算法。全部使用c语言代码实现。包含算法定义，思想，文字版实现过程，动图演示等。_数据结构希尔排序c语言

题目

本栏目是数据结构C语言版的十大排序算法，因为我只考常用的一些排序算法，所以会只更新一部分常用算法，每个排序分为算法思想，算法代码和执行结果三个部分展现。

更新第五篇：C语言实现希尔排序

---

以下是本篇文章正文内容，欢迎朋友们进行指正，一起探讨，共同进步。——来自考研路上的lwj。QQ：2394799692

一、算法思想

1.算法执行过程动图演示：

2.定义：

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

3.算法思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1
时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.我的总结：

首先设置增量d为数组元素/2，划分子表，然后对每个子表排序，然后再次将d/2，划分子表，排序，直到d=1为止。

稳定性为：不稳定
>时间复杂度为：
好的情况：O（n^1.3）
坏的情况：O（n^2）
>空间复杂度为： O（1）

5.学习笔记：

二、代码部分

1.引入库

代码如下（示例）：

#include<stdio.h>
1

2.主函数部分

代码如下（示例）：

void sort(int a[], int n)
{
	int i, j, d, temp;
	for(d=n/2;d>=1;d=d/2)//d为增量
		for(i=d+1;i<n;i++)//直接插入排序
			if (a[i] < a[i - d])
			{
				temp = a[i];
				for (j = i - d; j >= 0 && a[j] > temp; j = j - d)
					a[j + d] = a[j];
				a[j + d] = temp;
			}
}
void main()
{
	int a[] = { 10,9,8,7,6,5,4,3,2,1 };
	int n = sizeof(a) / sizeof(int);
	sort(a, n);
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

三、执行结果

输入：

a[] = { 10,9,8,7,6,5,4,3,2,1 };
1

输出：

1 2 3 4 5 6 7 8 9 10
1