【数据结构初阶】--排序(一)：直接插入排序，希尔排序-EW帮帮网

😘个人主页：@Cx330❀

👀个人简介：一个正在努力奋斗逆天改命的二本觉悟生

📖个人专栏：《C语言》《LeetCode刷题集》《数据结构-初阶》

前言：在之前的博客学习中，我们掌握了顺序表、链表、栈与队列以及二叉树的相关数据结构，对代码的理解和掌握有了一定的熟悉，那么接下来我们就进入数据结构最后一个章节的学习中去——排序，排序的种类有很多，有的排序可以有很多种方法去完成，其实每种排序单独拿出来都不会很难。但是如果让我们自己去实现的话就不是那么容易的了。

一、排序的概念及应用

常见的排序算法：

一、排序的概念及应用

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

我们在日常生活中也可以见到形形色色的排序，例如歌曲排行榜

常见的排序算法：

如图：

二、直接插入排序

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

在实际生活中，我们打扑克就运用到了插入排序

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

代码展现：

//直接插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			//升序:>   
            //降序:<
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else {
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

图解：

test.c:

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//直接插入排序
	InsertSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
int main()
{
	test1();
	return 0;
}

测试结果：

测试完成，打印没有问题，排成了升序，退出码为0

复杂度分析：

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

三、希尔排序

基本思想：希尔排序（Shell Sort）是一种改进的插入排序算法，其核心思想是通过将数组分割成若干个“子序列”逐步缩小排序范围，最终实现整体有序。

先选定⼀个整数（通常是gap = n/3+1），把待排序文件所有记录分成各组，所有的距离相等的记录分在同一组内，并对每⼀组内的记录进行排序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进行插入排序，当gap=1时，就相当于直接插入排序。

希尔排序的特性：

希尔排序是对直接插入排序的优化
当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果

代码展现：

//2)希尔排序
void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];
					end-=gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

图解：

为啥要用gap=gap/3-1：

test.c:

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//希尔排序
	ShellSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
int main()
{
	test1();
	return 0;
}

测试结果：

测试完成，打印没有问题，升序排列正确，退出码为0

复杂度分析：

时间复杂度：O(N^1.3)

四、直接插入排序和希尔排序的性能对比

除了通过时间复杂度以外，我们也可以通过下面这串代码来实现两种排序的性能对比

代码展示：

#include"Sort.h"
 
void PrintArr(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
}
 
void test1()
{
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	int size = sizeof(a) / sizeof(a[0]);
	printf("排序前:");
	PrintArr(a, size);
 
	//直接插入排序
	//InsertSort(a, size);
	//希尔排序
	ShellSort(a, size);
 
	printf("排序后:");
	PrintArr(a, size);
}
 
// 测试排序的性能对比
void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
 
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
 
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
 
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
 
	free(a1);
	free(a2);
}
 
int main()
{
	TestOP();
	//test1();
	return 0;
}

测试完成，可以看出10w个数据排序，希尔排序的用时比直接插入排序少很多(单位：ms)