C语言常见排序算法之插入排序(直接插入排序,希尔排序)

2024-04-02 19:04:59 134人浏览独家记忆

摘要

目录前言一、直接插入排序1.1 基本思想1.2 算法思想1.3 程序实现1.4 直接插入排序的总结二、希尔排序2.1 算法思想2.2 程序实现2.3 希尔排序的特征总结前言

前言

本期为大家带来的是常见排序算法中的插入排序，主要有直接插入排序以及它的升级版——希尔排序，包您一看就会，快来试试吧~

一、直接插入排序

1.1 基本思想

在生活当中，这种排序方式处处可见：

在玩扑克牌的时候我们就会采用插入排序的思想，当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们则将牌插入至第一张牌的左边，反之就插入至右边（升序）。以图为例：我们拿起一张7，发现比最后一张牌10小，自然7与10就要交换位置，交换完成后，发现7前面的数字比自己小，就不用交换了，所以就找到7的位置了。

我们会发现，在拿起一张牌准备插入时，待插入的区间已经是有序的，我们要做的是，插入后使区间依旧有序。

1.2 算法思想

当插入第 i (i>=1)个元素时，前面的array[0],a[1]……a[i-1] 已经排序好，此时用a[i]的排序码与 a[i-1],a[i-2]……进行比较，找到插入位置，原来位置上的数据元素顺序往后移。

用一组实例来观察一下是算法是怎么实现的的：

1.3 程序实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//打印数据
void Print(int* a,int  n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}
 
//直接插入排序
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 (a[end] > tmp)//修改此处符号即可升序降序切换
			{
				a[end+1] = a[end];
				--end;
			}
			else
			{
				break;
			}
			a[end + 1] =tmp;
		}
	}
	//打印数据
	Print(a,n);
}
 
int main()
{
	int a[6] = { 5,2,4,6,1,3 };
	//直接插入排序
	InsertSort(a,sizeof(a)/sizeof(a[0]));
	return 0;
}

1.4 直接插入排序的总结

1.元素集合越接近有序，直接插入排序算法时间效率越高
2.时间复杂度：O(N^2)(最坏情况) ，最好情况时间复杂度是O(N);
3.空间复杂度：O(1),是一种稳定的排序算法
4.稳定性：稳定

二、希尔排序

希尔排序是一种特殊的插入排序，是直接插入排序基础上的优化。

2.1 算法思想

希尔排序又称为缩小增量法，希尔排序的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个组，所有距离为“gap”的记录分在同一组内，并对每一个组内的记录进行排序。然后，取，重复上述分组和排序工作。当“gap”（间隔）==1，所有记录在统一组内排好序。

1.先进行预排序，使数组接近有序
2.直接插入排序

预排序：分组排，间隔为 gap 是一组，假设 gap ==3;

9 8 7 6 5 4 3 2 1 0,如果将这组数据升序排序，使用直接插入排序，算法的复杂度就是 O(N^2);

每个 gap 间隔的小分组都再进行插入排序。

优点：大数，小数更快的到达两端，当gap等于1时，就是直接插入排序，这时候时间复杂度就是大大降低。

2.2 程序实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
 
//希尔排序
void shellSort(int* a, int n)//升序
{
	int gap = n;
	while (gap > 1)//当gap等于1时，就是直接插入排序
	{
		gap = gap / 2;
		//把间隔为gap的多组数据同时排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end>=0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
	//打印数据
	Print(a, n);
}
int main()
{
	int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
	//希尔排序
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}