直接插入排序与希尔排序

目录

一，排序的概念

二，插入排序

2.1直接插入排序

2.2 希尔排序

---

一，排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些或某些关键字的大小，递增或递减的排列

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对顺序保持不变，即在原序列中，r[i]=r[j],且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

二，插入排序

这里以排升序为例。

2.1直接插入排序

插入排序的基本思想是把待排序按其关键吗值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实现步骤：

1，将待排元素提取出来（tmp）

2，将待排元素与已排元素的序列中从尾部开始扫描提取元素进行比较

3，如果比尾部元素小于，将该比较的元素向后移一位。待排元素与下一个扫描的元素进行比较。

4，重复2,3，直到遇到比待排元素小停止，放在待排元素后面的位置，如果所有元素都大于已排元素，则将待排元素插入下标为0的位置

5，重复1-4，直到完成排序

代码如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n-1; i++)
	{
		int end = i;	//已排元素尾部
		int tmp = a[end + 1];//待排元素
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
		
	}
	
}
int main()
{
	int a[10] = { 9,2,8,1,0,3,6,5,7,4 };
	InsertSort(&a,10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
 
}

代码思路分析：

直接插入排序的特性总结：

1，元素集合越接近有序，直接插入排序算法的时间效率高。

2，时间复杂度：O(N^2)

3, 空间复杂度：O(1),它是一种稳定的排序算法

5，稳定性：稳定

2.2 希尔排序

希尔排序又称为缩小增量法，基本思想是：先定一个增量gap，把待排序文件中所有元素按下标的增量分为几个组，对每组使用插入排序算法进行排序。然后增量每减少一次，就载按照下标的增量进行排序，直到增量为1排完序为止，增量大于1时称为预排序。

实现步骤：

1，先初始化增量，增量为0时结束程序。增量为1时相当于直接插入排序。

2，在这个增量下，下标按照增量进行分组排序，将每个组按照直接插入排序思想进行排序，只不过组里的相邻元素需跳过增量大小的距离。

3，然后增量再缩小，如果增量为0时结束。

4，重复2,3步骤，直到程序结束。

#define _CRT_SECURE_NO_WARNINGS 1
#include
void ShellSort(int* a, int n)
{
	int gap = n;    //gap增量
	while(gap>0)
	{
		gap = gap / 2;
		for (int i = 0; i < n - gap ; i ++)//gap的单趟排
		{
			int end = i;
				int tmp = a[end + gap];
				while (end >= 0)//组排序
				{
					if (tmp < a[end])
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			
		}
	}
}
int main()
{
	int a[10] = { 9,2,8,1,0,3,6,5,7,4 };
	ShellSort(&a, 10);
	for (int i = 0; i < 10; i++)
	{
		printf("%d ", a[i]);
	}
 
}

代码思路分析：

希尔排序的特性总结：

1，希尔排序是对直接插入排序的优化。

2，当gap>1时都是预排序，目的是让数组更接近有序。当gap == 1 时，数组已经有序的了。

3，希尔排序的时间复杂度不好计算，因为gap的取值方法是不固定的，导致很难计算。因此好些树中给出的希尔排序的时间复杂度都不固定。

好了到这里就结束了，希望能对大家有所帮助！