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

前言

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

一、直接插入排序

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;
}

2.3 希尔排序的特征总结

• 1.希尔排序是对直接插入排序的优化。
• 2.当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近有序，这样就会很快。整体而言，可以达到优化的效果。
• 3.希尔排序的时间复杂度不好计算，需要根据数据进行推导，推导出来的的平均时间复杂度：O(N^1.3——N^2)。
• 4.稳定性：不稳定

到此这篇关于C语言常见排序算法之插入排序(直接插入排序,希尔排序)的文章就介绍到这了,更多相关C语言插入排序 内容请搜索程序员之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持程序员之家！

最新评论