首页 > 编程语言 >十大经典排序算法——插入排序与希尔排序(超详解)

十大经典排序算法——插入排序与希尔排序(超详解)

时间:2024-06-22 21:29:55浏览次数:22  
标签:arr end int 插入排序 gap 详解 排序

一、插入排序

1.基本思想

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

2.直接插入排序

当插入第 end + 1 个元素时,前面的arr[0],arr[1],...  ,arr[end]已经排好序,此时用arr[end + 1]的值与arr[end],arr[end - 1],... 的值进行比较,找到插入位置将arr[end + 1]插入,原来位置上的元素顺序后移。

3.图示

3.时间复杂度:

时间复杂的一般是看最坏的情况

最坏的情况—逆序,时间复杂度:O(N^{2})

最好的情况—顺序,时间复杂度为:O(N)

4.直接插入排序特性总结

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

(2)时间复杂度:O(N^{2})

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

(4)稳定性:稳定 

5.参考代码

//插入排序
void InsertSort(int* arr, int n)
{
	for (int i = 0; i < n-1; i++)
	{//[0,end]是有序的,end + 1位置的值插入到[0,end],保持有序
		int end = i;
		int tmp = arr[end + 1];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

二、希尔排序

1.基本思想

希尔排序又称缩小增量法, 希尔排序的基本思想是:现有选定一个整数gap,把待排序的文件中所有记录分成几个组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。然后,重复上述分组和排序的工作。直到gap==1时,所有记录在同一组内排好序

2.操作

(1)预排序(让数组接近有序)

(2)插入排序 

思想:根据给出的整数gap,将数组分组,再分别对这些组进行插入排序

gap > 1 是预排序,gap == 1 是插入排序 

gap越大,大的数可以越快跳到后面,小的数可以越快跳到前面,得到的数据也越不接近有序。

gap越小,跳的越慢,也越接近有序。当gap是1,相当于插入排序。

代码实现: 两种方式

int gap = 3;
//多组并着走
for (int i = 0; i < n - gap; ++i)
{
	int end = i;
	int tmp = arr[end + gap];
	while (end >= 0)
	{
		if (tmp < arr[end])
		{
			arr[end + gap] = arr[end];
			end -= gap;
		}
		else
		{
			break;
		}
	}
	arr[end + gap] = tmp;
}	
int gap = 3;
//一组一组走
for (int j = 0; j < gap; j++)
{
	for (int i = 0; i < n - gap; i += gap)
	{
		int end = i;
		int tmp = arr[end + gap];
		while (end >= 0)
		{
			if (tmp < arr[end])
			{
				arr[end + gap] = arr[end];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		arr[end + gap] = tmp;
	}
}

3.如何选择希尔增量

希尔排序的分析是个复杂的问题,因为它的时间是所取“增量”序列的函数,者设计一些数学上尚未接轨的难题。因此,到目前为止尚未有人求得一种最好的增量序列,但大量的研究已经得出一些局部的结论。如有人指出,当增量序列为dlta[k]= 2^{t-k+1}-1时,希尔排序的时间复杂度为O(N^{\frac{3}{2}}),其中t为排序趟数,1\leqslant k\leqslant t\leqslant \left \lfloor{log_{2}}^{(n+1)}\right \rfloor。还有人在大量的实验中推出:当n在某个特定范围内,希尔排序所需的比较和移动次数越为n^{1.3},当n\rightarrow∞时,可减少到n({log_{}}^{n})^{2^{\left \lfloor 2 \right \rfloor}}。增量序列可以有各种取法,但需要注意:应是增量序列中的值没有除以1以外的公因子,并且最后一个增量值必须等于1。

gap的取值有多种。最初Shell提出取gap= \left \lfloor n/2 \right \rfloorgap= \left \lfloor gap/2 \right \rfloor,直到gap= 1,后来Knuth提出取gap= \left \lfloor gap/3 \right \rfloor + 1。(+1是为了保证最后一个gap的值是1) 

在Knuth所著的《计算机程序设计技巧》中,利用大量的实验统计资料得出,当n很大时,关进码平均比较次数和对象平均移动次数大约在n^{1.25}1.6n^{1.25}范围内,这是利用直接插入排序作为子序列排序方法的情况下得到的。

4.希尔排序完整图示: 

gap = gap / 3 + 1(+1是为了保证最后一个gap的值是1) 

5.希尔排序的特性总结 

(1)希尔排序是对直接插入排序的优化

(2)当gap > 1时都是预排序,目的是让数组更接近与有序。当gap == 1时,数组已经接近有序了,这样就会很快。对整体而言,可以达到优化的效果。

(3)希尔排序的时间复杂度不好计算,因为gap的取值方式有很多种,导致难以计算。    大约是在O(N^{1.3})左右。

理解一下过程:

(4)稳定性:不稳定

6.代码实现 

void SellSort(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 (tmp < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}	
	}
}

三、排序效率对比

将插入排序,希尔排序,堆排序的运行效率进行对比

http://t.csdnimg.cn/QtpwY堆排序详解在这篇文章!

void TestOP()
{
	srand(time(0));
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	int* a3 = (int*)malloc(sizeof(int) * N);


	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];


	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	
	int begin2 = clock();
	SellSort(a2, N);
	int end2 = clock();
	
	int begin4 = clock();
	HPSort(a4, N);
	int end4 = clock();

	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("HPSort:%d\n", end4 - begin4);

	free(a1);
	free(a2);
	free(a3);
}


int main()
{
	int arr[] = { 9,1,2,5,7,4,6,3,8 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	TestOP();
	return 0;
}

上图为代码运行结果,同样是十万个随机数,插入排序相较于希尔排序和堆排序就逊色一些。

标签:arr,end,int,插入排序,gap,详解,排序
From: https://blog.csdn.net/2401_83431652/article/details/139861174

相关文章

  • 【CPP】插入排序、希尔排序
    目录1.插入排序1.1直接插入排序简介代码分析1.2直接插入对比冒泡排序简介代码对比分析(直接插入排序与冒泡的复杂度效率区别)1.3希尔排序简介代码分析1.插入排序基本思想:把一个待排数字按照关键码值插入到一个有序序列中,得到一个新的有序序列。1.1直接插入排序......
  • 嵌入式秋招面试中,一定要掌握的嵌入式c基础——关键字详解(1)
    哈喽,大家好,这里是自律鸽。正如标题所强调的,在嵌入式秋招面试中,被问到c语言相关知识的概率几乎达到了百分之百。我本人也在去年的秋招中深切体验了这一点。因此,我想与大家分享一些面试中常问的嵌入式c基础,这些也都是我在求职过程中积累的宝贵经验。关键字1、sizeof:经常被问到......
  • 详解 ClickHouse 的分片集群
    一、简介分片功能依赖于Distributed表引擎,Distributed表引擎本身不存储数据,有点类似于MyCat之于MySql,成为一种中间件,通过分布式逻辑表来写入、分发、路由来操作多台节点不同分片的分布式数据ClickHouse进行分片集群的目的是解决数据的横向扩容,通过分片把一份完整......
  • python 快速排序
     快速排序快速排序是一种非常高效的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。 以下是一个使用Python实现的快速排序的示例代码: pythond......
  • 如何用GO语言实现快速排序算法?
    本章教程,介绍一下如何用GO语言实现基础排序算法中的快速排序。快速排序(Quicksort)是一种高效的排序算法,它采用分治法策略,将一个数组分成两个子数组,然后递归地对这两个子数组进行排序。一、程序代码packagemainimport( "fmt" "math/rand" "time")//quickSo......
  • 掌握ChatGPT:提示工程入门详解
    随着人工智能的发展,提示工程成为了使用ChatGPT等语言模型的核心技术。对于初学者,理解和运用提示工程是提高与ChatGPT互动效果的关键。什么是提示工程?提示工程是通过设计和优化输入文本(提示)来引导AI生成特定输出的过程。它包括思路链(Chain-of-Thought)、提示链接(PromptChain......
  • MySQL-文件排序原理详解
    目录Usingfilesort文件排序原理详解filesort文件排序方式示例验证下各种排序方式:单路排序的详细过程:双路排序的详细过程:单路排序相对于双路排序具有以下特点:Usingfilesort文件排序原理详解filesort文件排序方式单路排序:是一次性取出满足条件行的所有字段,然后在s......
  • DCF协议详解
    1概述DCF机制是IEEE802.11标准的核心接入机制,网络中所有节点都应该具备该功能。DCF主要采用带有冲突避免的载波侦听多路访问(CarrierSenseMultipleAccessCollisionAvoidance,CSMA/CA)协议,当使用CSMA时,一个想要发送数据的站点首先侦听传输煤质一段定长时间,如果......
  • 使用MPI 实现奇偶排序
    使用MPI实现奇偶排序0号进程获得待排序序列并输出排序好的序列使用文件进行输入输出进行性能测试与对比代码奇偶排序头文件引入#include<iostream>#include<algorithm>#include<mpi.h>#include<fstream>#include<chrono>定义规模#defineN100000000......
  • Python 冒泡排序
    冒泡排序是一种简单的排序算法,它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。以下是一个用Python实现的冒泡排序算法的例子:pythondefbubble_sort(lst):n=len......