数据结构-C语言-排序（1）

代码位置：test-c-2024: 对C语言习题代码的练习 (gitee.com)

一、前言：

1.1-排序定义：

排序就是将一组杂乱无章的数据按照一定的规律（升序或降序）组织起来。

1.2-排序分类：

常见的排序算法：

插入排序
a. 直接插入排序
b. 希尔排序
选择排序
a. 选择排序
b. 堆排序
交换排序
a. 冒泡排序
b. 快速排序
归并排序
a. 归并排序
非比较排序
a.计数排序
b.基数排序

1.3-算法比较：

今天，我们这里要实现的是直接插入排序和希尔排序。

二、直接插入排序：

2.1-思路：

其中传入的数组a为需要排序的数组，len为数组长度。这里的思路是直接从数组的第二个位置开始一直到数组的最后一个位置，依次与前面数据比较（当数组个数为一个时不需要排序所以从第二个数据开始比较插入），因为排序默认情况下采用升序，所以这里我们也采用升序的方式。

原理：将tem设为要插入的元素，依次与前面元素比较，若前面元素比它大则需将tem前移直到遇到比它小的元素时才结束，并将tem插入那个元素后。

2.2-过程图：

2.3-代码如下：

代码中我加入了打印函数便于观察插入的过程。

//升序
void InsertSort(int* a,int len)			//直接插入排序
{
	printf("原数组顺序：");
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	for (int i = 1; i < len; i++)
	{
		int end = i - 1;
		int tem = a[i];		//插入排序从第二个元素开始
		//将tem插入到区间 [ 0 , end ] 中，保持有序
		while (end >= 0)
		{
			if (a[end] > tem)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tem;
		printf("排序第%d趟：", i);
		for (int i = 0; i < len; i++)
		{
			printf("%d  ", a[i]);
		}
		printf("\n");
	}
}

2.4-效果图：

2.5-性质：

由上述代码及图片见:

时间复杂度：

直接插入排序的时间复杂度在最好的情况（原数组升序）下为O(N)，在最坏的情况（原数组降序）下为O(N^2).。

空间复杂度：

因为没开辟空间，所以空间复杂度为O（1）。

稳定性：

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

三、希尔排序：

2.1-思路：

　其中传入的数组a为需要排序的数组，len为数组长度。这里的思路是直接从数组的第gap个位置开始一直到数组的最后一个位置，依次与前面相差gap个数据位置的数据比较，因为排序默认情况下采用升序，所以这里我们也采用升序的方式。将tem设为要插入的元素，依次与前面相距gap个元素的位置比较，若前面元素比它大则需将tem前移直到遇到比它小的元素时才结束，并将tem插入那个元素后。说白了就是把相距gap个数据位置的数据放在一起比较进行插入排序。

原理：希尔排序是按照不同步长gap对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。

2.3-代码如下：

//升序
void ShellSort(int* a, int len)				//希尔排序
{
	printf("原数组顺序：");
	for (int i = 0; i < len; i++)
	{
		printf("%d  ", a[i]);
	}
	printf("\n");
	//gap是多少合适？
	//gap越大，跳的越快，越不接近有序
	//gap越小，跳的越慢，越接近有序
	int gap = len;
	while (gap > 1)
	{
		gap = gap / 2;
		for (int j = 0; j < gap; j++)
		{
			for (int i = gap + j; i < len; i += gap)
			{
				int end = i - gap;
				int tem = a[end + gap];
				//将tem插入到区间 [ 0 , end ] 中，保持有序
				while (end >= 0)
				{
					if (a[end] > tem)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tem;
			}
			
		}

		printf("gap=%d时排序：",gap);
		for (int i = 0; i < len; i++)
		{
			printf("%d  ", a[i]);
		}
		printf("\n");
	}
	
}

2.4-效果图：

2.5-性质：

由上述代码及图片见:　

时间复杂度：

　　希尔排序是按照不同步长gap对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比O(n^2)好一些。希尔排序的时间复杂度在最好的情况（原数组升序）下为O(N)，在最坏的情况下为O(N^1.3).。