排序(希尔、快速、归并排序)

2023-09-13 22:17:38

文章目录

        1.排序的概念及其运用

        2.插入排序

        3.选择排序

文章内容

1.排序的概念及其运用

1.1排序的概念

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

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

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

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

1.2排序运用

1.3 常见的排序算法

      排序接口及性能测试的代码 (注意头文件) ：

// 排序实现的接口
// 插入排序
void InsertSort(int* a, int n);
// 希尔排序
void ShellSort(int* a, int n);
// 选择排序
void SelectSort(int* a, int n);
// 堆排序
void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);
// 冒泡排序
void BubbleSort(int* a, int n)
// 快速排序递归实现
// 快速排序hoare版本
int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
// 归并排序递归实现
void MergeSort(int* a, int n)
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
// 计数排序
void CountSort(int* a, int n)
// 测试排序的性能对比
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);
int* a4 = (int*)malloc(sizeof(int)*N);
int* a5 = (int*)malloc(sizeof(int)*N);
int* a6 = (int*)malloc(sizeof(int)*N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
int begin5 = clock();
QuickSort(a5, 0, N-1);
int end5 = clock();
int begin6 = clock();
MergeSort(a6, N);
int end6 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelectSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
printf("QuickSort:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
}

 2.插入排序

2.1基本思想：

        直接插入排序是一种简单的插入排序法，其基本思想是：

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

        实际中我们玩扑克牌时，就用了插入排序的思想

        我们先保证【0，end】有序，之后再插入后一个，也使其变得有序。end是从起始位置开始，依次向后，这样就能保证【0，end】有序，end不断＋＋，表示不断向数组内插入新元素。

        

2.2直接插入排序：

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;

	}
}

直接插入排序的特性总结：
1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.3 希尔排序( 缩小增量排序 )

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

    核心思想：让小的(大的)数，快速的到前面

希尔排序的特性总结：

        1. 希尔排序是对直接插入排序的优化。
        2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
        3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定：

        《数据结构(C语言版)》--- 严蔚敏

        

        希尔排序代码实现：

        单趟shell排序：

        相同颜色块发生交换，但交换完成后不能保证白块内的三个子块有序。随着gap的值不断减小，当gap = 1 时候，便是直接插入排序。

希尔排序：

void ShellSort(int* a, int n)
{

	//单躺希尔排序
	//int gap = 3;

	//for (int j = 0; j < gap; j++)
	//{
	//	for (int i = 0; i < n - gap; i += gap)
	//	{
	//		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;
	//	}
	//}




	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;

		for (int i = 0; i < n - gap; ++i)
		{
			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;
		}
	}


}

 

 3.选择排序

        3.1基本思想：

        每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

        3.2 直接选择排序:

  在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素，若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换，在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

代码：

void SelsctSort(int* a, int n)
{

	int begin = 0;
	int end = n - 1;

	while (begin < end)
	{
		int mini = begin;
		int maxi = end;

		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}

		}
		Swap(&a[begin] , &a[mini]);

		//begin 位置与 maxi位置重合 
		//在上一步中最大值已经被挪到下标为mini的位置
		if (begin == maxi)
		{
			maxi = mini;
		}

		Swap(&a[maxi], &a[end]);
		end--;
		begin++;

	}

}

直接选择排序的特性总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

3.3 堆排序

        堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

        堆排序前面的博客讲过此处不再细讲：

 

void AdjustDown(int* a, int size , int parent )
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		if (a[child] < a[child + 1] && child + 1 < size)
		{
			child = child + 1;
		}

		if (a[parent] < a[child])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}

}



void HeapSort(int* a, int n)
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n , i);
	}

	int end = n - 1;

	while (end > 0)
	{
		Swap(&a[0],&a[end]);
		AdjustDown(a , end , 0);
		end--;
	}

}

直接选择排序的特性总结：
1. 堆排序使用堆来选数，效率就高了很多。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

4.交换排序

       4.1 基本思想：

        所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

       4.2冒泡排序：

冒泡排序老相识了......

void BubbleSort(int* a, int n)
{
	assert(a);

	int exchange = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i; j++)
		{
			if (a[j - 1] > a[j])
			{
				Swap(&a[j-1],&a[j]);
				exchange = 1;
			}

		}
		if (exchange == 0)
		{
			break;
		}

	}

}

冒泡排序的特性总结：
1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

4.3 快速排序

        快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

        快速排序有三个版本：

1. hoare版本

        ​​​​​​​选出key一般为最左端的值，然后让右边先走，找出比key小的值，之后左端走，找出比key大的值，然后交换，相遇停止，把key值放在停止的位置。

        单趟排完以后要求左边的比key小，右边的比key大。

问题来了，为什么选左边为key，先让右边的走？

        先说结论，因为要保证相遇位置的值小于key位置对应的值或者相遇位置就是key。

第一种情况：R先走遍历完整个数组，没有发现小于key位置对应的值，与key位置相交。

第二种情况：(R遇L)R找到比key位置小的值，L开始走找到比key位置大的值，交换。R向前走，此时与L相遇，这时下标对应的值是小于key，(L遇R)当R找到比key小，然后L开始走但是一直没找到比key大的值，直到相遇，这是相遇位置的值还是比key位置值小的值。

代码：

2. 挖坑法

        首先将坑位元素存储到key，然后找到小的元素放到坑位，之后对应小的元素就是坑位。如此循环往复。

//挖坑法

void PartSort2(int* a, int begin, int end)
{
	int key = a[begin];
	int piti = begin;

	while (begin < end)
	{
		//右找小
		while (begin < end && a[end] >= key )
		{
			end--;
		}

		a[piti] = a[end];
		piti = end;

		//左找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		
		a[piti] = begin;
		piti = begin;

	}

	a[piti] = key;
	return piti;

}

3. 前后指针法

注意红框地方，是前置++再去判断，不管进没有进判断语句，prev已经++

int PatrSort3(int* a, int begin, int end)
{

	int prev = begin, cur = begin+1;

	int keyi = begin;

	int midi = GetMidIndex(a , begin ,end);
	Swap(&a[keyi],&a[midi]);

	while (cur <= end)
	{
		//cur位置小于keyi发生交换
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			//++prev;
			Swap(&a[prev], &a[cur]);
		}

		cur++;
	}

	Swap(&a[keyi],&a[prev]);

	keyi = prev;
	return keyi;

}

找到大小剧中的key，对快排优化。 

int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	if (a[begin] < a[mid])
	{
		if (a[mid] < a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
	else // (a[begin] >= a[mid])
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] < a[end])
		{
			return begin;
		}
		else
		{
			return end;
		}
	}
}

快速排序：当end 与 begin 差值过小时，选择直接插入排序。

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin > 10)
	{
		int keyi = PatrSort3(a , begin , end);

		QuickSort(a , begin ,keyi- 1);
		QuickSort(a , keyi+1, end);
	}
	else
	{
		InsertSort(a+ begin , end-begin+1);
	}

}

5. 归并排序

5.1基本思想

        归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

5.2归并排序 

归并排序类似于后序遍历  左边return后，右边return  回到“根”后 ，然后开始排序。

下图为归并排序的展开逻辑图。

void _MergeSort(int* a, int begin , int end ,int* tmp)
{
	if (begin >= end)
	{
		return;
	}

	int mid = (begin + end) / 2;
	_MergeSort(a,begin,mid,tmp);
	_MergeSort(a, mid+1, end, tmp);

	//归并
	int begin1 = begin;
	int end1 = mid;
	int begin2 = mid + 1;
	int end2 = end;

	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}

	while(begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	memcpy(a+begin , tmp+begin,(end-begin +1)* sizeof(int));
}



void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int)* n);
	if (tmp == NULL)
	{
		perror("malloc fail");
	}

	_MergeSort(a,0,n-1,tmp);

	free(tmp);
}

更多推荐

网络爬虫-----爬虫的分类及原理

目录爬虫的分类1.通用网络爬虫：搜索引擎的爬虫2.聚焦网络爬虫：针对特定网页的爬虫3.增量式网络爬虫4.深层网络爬虫通用爬虫与聚焦爬虫的原理通用爬虫：聚焦爬虫：爬虫的分类网络爬虫按照系统结构和实现技术，大致可分为4类，即通用网络爬虫、聚焦网络爬虫、增量网络爬虫和深层次网络爬虫。1.通用网络爬虫：搜索引擎的爬虫比如用户在

基于Java+SpringBoot+Vue前后端分离美食烹饪互动平设计和实现

博主介绍：✌全网粉丝30W+,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌🍅文末获取源码联系🍅👇🏻精彩专栏推荐订阅👇🏻不然下次找不到哟2022-2024年最全的计算机软件毕业设计选题

关于单片机的分频定时器的记录

记录一内部时钟：对于单片机的频率原来一直不太明白，现在在学习进行记录：主频：以一个72M的STM32单片机作为主频为例子，这个72M主频说得是一秒钟产生72000000（七千两百万）个脉冲或周期，就是一秒钟振荡七千两百万次。分频对于分频来说，实际就是相当于间接降低这个主频，减少这个震荡次数，比如我分频系数为72，那么我

Git从入门到起飞(详细)

Git从入门到起飞Git从入门到起飞什么是Git？使用git前提(注册git)下载Git在Windows上安装Git在macOS上安装Git在Linux上安装Git配置Git配置全局用户信息配置文本编辑器创建第一个Git仓库初始化仓库拉取代码添加文件到仓库提交更改推送Git基本操作查看提交历史比较文件差异撤销更改分支管

争议不断：TikTok如何处理儿童数据隐私问题

在数字时代，社交媒体已经成为了人们生活中不可或缺的一部分，而TikTok，作为全球最热门的社交媒体平台之一，尤其受到年轻用户的喜爱。然而，伴随着TikTok的快速崛起，也涌现出了一系列的争议，其中最引人关注的之一是关于儿童数据隐私的问题。TikTok：年轻一代的最爱TikTok是一款以短视频为主的应用，允许用户制作、编

【flutter】架构之商城main入口

架构之商城main入口前言一、项目模块的划分二、入口main的配置三、配置文件怎么做总结前言本栏目我们将完成一个商城项目的架构搭建，并完善中间的所有功能，总页面大概200个，如果你能看完整个栏目，你肯定能独立完成flutter项目的整体研发工作。首先新建一个叫blog_mall的项目，能看到这里的，我想都知道该怎么创建

外包干了2个月，技术退步明显。。。。。

先说一下自己的情况，大专生，18年通过校招进入武汉某软件公司，干了接近4年的功能测试，今年年初，感觉自己不能够在这样下去了，长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试，已经让我变得不思进取，谈了2年的女朋友也因为我的心态和工资和我分手了。于是，我决定要改变现状，冲击下大厂。刚开始准备时

14：00面试，14：06就出来了，问的问题有点变态。。。

从小厂出来，没想到在另一家公司又寄了。到这家公司开始上班，加班是每天必不可少的，看在钱给的比较多的份上，就不太计较了。没想到5月一纸通知，所有人不准加班，加班费不仅没有了，薪资还要降40%,这下搞的饭都吃不起了。还在有个朋友内推我去了一家互联网公司，兴冲冲见面试官，没想到一道题把我给问死了：如果模块请求http改为了h

基于STM32CUBEMX驱动TMOS模块STHS34PF80(5)----配置嵌入式函数

基于STM32CUBEMX驱动TMOS模块STHS34PF80----4.中断获取信号概述视频教学样品申请视频教程参考Demo参考Demo完整代码下载内嵌函数地址串口配置IIC配置IO口设置串口重定向参考程序初始化IIC写函数IIC读函数获取ID设备的自动引导过程和关机模式配置省电模式温度数据的灵敏度值设置低通滤波器温

【面试题】智力题

文章目录腾讯1000瓶毒药里面只有1瓶是有毒的，问需要多少只老鼠才能在24小时后试出那瓶有毒。有两根不规则的绳子，两根绳子从头烧到尾均需要一个小时，现在有一个45分钟的比赛，裁判员忘记带计时器，你能否通过烧绳子的方式来为这场比赛计时？有25匹马，5条赛道，每条赛道同时只能有一匹马跑，假设每匹马的水平都很稳定，在没有计时

go并发处理业务

引言实际上，在服务端程序开发和爬虫程序开发时，我们的大多数业务都是IO密集型业务，什么是IO密集型业务，通俗地说就是CPU运行时间只占整个业务执行时间的一小部分，而剩余的大部分时间都在等待IO操作。IO操作包括http请求、数据库查询、文件读取、摄像设备录音设备的输入等等。这些IO操作会引起中断，使业务线程暂时放弃cp

热文推荐
  1. Mybatis常见面试题总结

    梳理面试过程中Mybatis相关的常见问题。为保证知识点覆盖，参考了《Mybatis从入门到精通》、《深入浅出Mybatis技术原理与实战》、《Mybatis技术内幕》等书籍。Mybatis简介Mybatis是一款优秀的持久层框架(ORM框架)，它支持自定义SQL、存储过程以及高级映射。Mybatis免除了几乎所有的J

  2. 2023 Google 开发者大会：Web平台新动向

    目录前言一、OpeninWordPressplayground二、WebGPU三、新的核心Web指标INP四、Webview1、CustomTabs2、JavaScriptEngine五、Passkeys六、ViewTransitionsAPI七、GoogleChrome开发者工具优化1、覆盖HTTP的响应标头2、改变

  3. 《机器学习核心算法》分类算法 - 朴素贝叶斯 MultinomialNB

    「作者主页」：士别三日wyx「作者简介」：CSDNtop100、阿里云博客专家、华为云享专家、网络安全领域优质创作者「推荐专栏」：小白零基础《Python入门到精通》朴素贝叶斯1、朴素贝叶斯API2、朴素贝叶斯算法实际应用2.1、获取数据集2.2、划分数据集2.3、特征归一化2.4、贝叶斯算法处理并评估3、常见问题4、

  4. 大数据-Hive

    Hive简介Hive是基于Hadoop的一个【数据仓库工具】，可以将结构化和半结构化的数据文件映射为一张数据库表，并提供简单的sql查询功能。因为比直接用MapReduce开发效率更高，Hive的主要作用就是用来做离线数据分析。本质是：将HQL转化成MapReduce程序特点可扩展性Hive可以自由的扩展集群的规模，一

  5. Mybatis深度解析：从起源到现代应用的全景视角

    🌷🍁博主猫头虎带您GotoNewWorld.✨🍁🦄博客首页——猫头虎的博客🎐🐳《面试题大全专栏》文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺🌊《IDEA开发秘籍专栏》学会IDEA常用操作，工作效率翻倍~💐🌊《100天精通Golang(基础入门篇）》学会Golang语言，畅玩云原生，走遍大

  6. C语言天花板——指针(初阶)

    🌠🌠🌠大家在刚刚接触C语言的时候就肯定听说过，指针的重要性以及难度等级，以至于经常“谈虎色变”，但是今天我来带大家走进指针的奇妙世界。🎇🎇🎇一、什么是指针🤔指针理解的两个要点：1️⃣指针是内存中一个最小单元的编号，也就是地址2️⃣平常口语中说的指针，通常指的是指针变量，是用来存放地址的变量数据存储在内存中

  7. Java基于SpringBoot的藏区特产销售系统的研究与实现

    今天为大家带来的是基于Java+SpringBoot+Vue的藏区特产销售系统，大家有兴趣的可以看一下博主介绍：✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W+,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌文章目录1.简介2.主要技术3功能分析4系统分析5

  8. RabbitMQ 几种模式

    一、HelloWorld模式在这一部分中，我们将用Java编写两个程序。发送单个消息的生产者和接收消息并打印出来的消费者。模型如下所示：在下图中，“P”是我们的生产者，“C”是我们的消费者。中间的框是一个队列RabbitMQ代表使用者保留的消息缓冲区。1.1生产者1.1.1添加依赖<!--指定jdk编译版本--><bu

  9. Weblogic SSRF 漏洞复现

    SSRF实例WeblogicSSRF到GetShell​Weblogic中存在一个SSRF漏洞，利用该漏洞可以发送任意HTTP请求，进而攻击内网中redis、fastcgi等脆弱组件。测试环境搭建编译及启动测试环境sudodockercomposeup-d访问http://10.9.75.58:7001/console