当前位置:首页 > 技术 > 正文内容

数据结构【C语言版】五千字长文手把手带你手撕快速排序,归并排序!

Lotus2022-11-01 20:16技术

数据结构之八大算法详解(2)——快速排序,归并排序

快速排序

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

hoare版本

单趟排序:

  1. 选择一个key(一般是一个或者最后一个)
  2. 单趟排序,要求小的在key的左边,大的在key的右边!

hoare.gif

右边先开始找小,找到小的就停下来。然后左边开始找大,找到大的就停下俩,然后两个互换!再继续从右边开始,以此循环,最后直到两个相遇!与key进行交换!

左边做如何保证最后的相遇点一定比key要小呢?答案是右边先走保证的!

我们可以分为两种情况

  1. R停下来,L撞到R相遇,相遇位置比key要小

    因为R停下来的位置一定比key小!

  2. L停下来,R撞到了L相遇,相遇位置比key还要小!

image-20220925170234443.png

所以我们可以看出来右边先走可以保证无论是那种情况都是相遇位置比key小!

==如果是右边第一个做key的话要反过来!==

==单趟排序的时间复杂度为O(N)==

单趟排序的价值

  1. key已近到了它的最终位置!
  2. 它分割出了两个子区间!如果子区间有序了,那么整体也就有序了!那么如何让子区间有序呢?——进行子问题递归!
int PartSort(int* a, int left, int right)//升序!
{
	int key = left;
	while (left < right)
	{
		while (a[right] >= a[key] && left < right)//如果不用>=,而是 > 这个条件如果不加入会进入死循环!例如 6 6 6 6 6 6 这种!
			//如果不加入left < right 可能会导致错过!5 1 2 3 4
		{
			right--;
		}
		while (a[left] <= a[key] && left < right)
		{
			left++;
		}
		if (left < right)
			swap(&a[left], &a[right]);
	}
	int meet = left;
	swap(&a[key], &a[left]);//把key和相遇位置进行交换!
                                          
	return meet;
}
                                          
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	//单趟排序完毕,整个区间被分为[0,keyi-1] keyi [keyi+1,end]
                                          
	QuickSort(a, 0, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

image-20220925195511137.png

我们可以看出来快速排序看起来就像是一个二叉树!

递归深度为:logN

时间复杂度为 nlogn

n+(n-1)+(n-1-2)+(n-1-2-4)+......+(n-(1+2+4+...2^logn^))

最后一层约等于 n-logn 与n的差别是不大的!

所以可以粗略的算成是 n*logn

关于快排的优化

以上的情况我们都是默认每次选都是在中间!

但是快排最害怕的情况是有序!或者接近有序的情况!

image-20220925200951647.png

这种情况下快排的递归深度为N

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

n+(n-1)+n-2+......1 = n(n-1)+(n(n-2)*(-1))/2 = n(n-1)/2=n^2^/2-n/2

这种情况下很容易导致递归深度太深导致栈溢出!

所以为了防止这种情况我们要优化选key逻辑!

  1. 随机选一个位置做!
  2. 针对有序,选正中间的值做key
  3. 三数取中!——第一个,中间位置,最后一个,选出中间值!
int GetMidIndex(int* a, int left, int right)
{
	int mid = (right + left) / 2;
    //mid = left + (right-left)/2
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else
	{
		if (a[left] < a[right])
		{
			return left;
		}
		else if (a[mid] > a[right])
		{
			return mid;
		}
		else
		{
			return right;
		}
		
	}
}//三数取中

int PartSort(int* a, int left, int right)//升序!
{
	int key = GetMidIndex(a,left,right);
	swap(&a[left], &a[key]);
	key = left;
	while (left < right)
	{
		while (a[right] >= a[key] && left < right)
		{ 
			right--;
		}
		while (a[left] <= a[key] && left < right)
		{
			left++;
		}
		if (left < right)
			swap(&a[left], &a[right]);
	}
	int meet = left;
	swap(&a[key], &a[left]);

	return meet;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = PartSort(a, begin, end);
	QuickSort(a, 0, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

快排优化之小区间优化

image-20220925212225308.png

如果我们能把最后几层给进行优化,是其不进行递归的话,可以使得快速排序有更高的效率!

我们可以选择直接插入排序,直接插入排序在面对接近排序或小数据量的时候有很好的效果!

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, begin - end + 1);//插入排序!
		//a+begin是因为不知道是在左区间还是右边内,begin-end+1是为了算个数!
	}
	else
	{
		int keyi = PartSort(a, begin, end);
		QuickSort(a, 0, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

挖坑法

挖坑法.gifimage-20220926091732720.png

int PartSort2(int* a, int left, int right)//单趟排序!
{
	int mid = GetMidIndex(a, left, right);
	swap(&a[mid], &a[left]);
	int key = a[left];
	int hole = left;//用来保存坑位!
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			--right;
		}
		a[hole] = a[right];
		hole = right;
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[hole] = a[left];
		hole = left;
	}
	int meeti = left;
	a[left] = key;

	return meeti;

}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, begin - end + 1);
	}
	else
	{
		int keyi = PartSort2(a, begin, end);
		 QuickSort(a, 0, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

前后指针法

前后指针.gif

cur ——作用是找小!

prev的两种状态

1.紧跟着 cur 2. 在比key大的位置的前面!(prev和cur之间都是比key还要大的!)

image-20220926125214997.png

int PartSort3(int* a, int left, int right)
{
	int mid = GetMidIndex(a, left, right);
	swap(&a[mid], &a[left]);
	int keyi = left;
	int prev = left;
    int cur = left+1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && cur != prev)
		{
			prev++;
			swap(&a[cur], &a[prev]);
		}
		cur++;
	}
    swap(&a[keyi],&a[prev]);
    return prev;
}

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	if (end - begin <= 8)
	{
		InsertSort(a + begin, end - begin  + 1);
	}
	else
	{
		int keyi = PartSort3(a, begin, end);
		QuickSort(a, 0, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
}

快速排序的非递归算法!

递归的本质是栈!我们要使用非递归本质也是模仿栈的原理!

image-20220926234506551.png

从该图我们可以看出来每次进入下一层的递归本质就是区间范围的改变!所以我们可以使用数据结构中的栈来模仿这改变的顺序!

数据结构中的栈存储的就是范围的改变!

//关于栈请读者自行实现!
void QuickSortNonR(int* a, int begin, int end)
{
	ST qk;
	StackInit(&qk);
	stackPush(&qk, begin);
	stackPush(&qk, end);
    //将开始的左右范围放在栈中!
	while (!StackEmpty(&qk))//只有栈中没有值了就可以停止了!
	{
		int right = StackTop(&qk);//因为栈是后进先出所以要先接收right
		StackPop(&qk);
		int left = StackTop(&qk);
		StackPop(&qk);
        //取出左右区间范围
		if (left >= right)//这个就相当于递归中的return!
		{
			continue;
		}
		int keyi = PartSort3(a, left, right);//在这个取出来的范围进行单趟排序!得到keyi值
        
        //将区间分为3个部分
        //[left keyi-1] keyi [keyi+1 right]
        //我们要先拿出左区间,再拿出右区间,所以先把右区间放进去,再放左区间
        //因为栈是后进先出的!
        
		stackPush(&qk, keyi + 1);//先放左边
		stackPush(&qk, right);//在放右边
        //将右区间放进去  先放右区间的左值 再放右区间的右边值!
        //这样下一次循环 right接收到的就是右值 left接收到的就是左值
        
		stackPush(&qk, left);//先放左边
		stackPush(&qk, keyi - 1);//在放右边
        //同理!
	}

	StackDestroy(&qk);
}

快排总结

  1. 时间复杂度:O(N*logN)
  2. 空间复杂度:O(logN)

可以用二叉树的前序遍历来理解快速排序,二叉树的前序遍历就是先遍历根,在遍历左数,然后遍历右数

快速排序也是类似,先找出本次的keyi 然后排左区间,然后排右区间!

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

image-20220928110916716.pngimage-20220928111423090.png

归并排序的时间复杂度!

归并排序的本质就是一颗二叉树!

所以层数为logN层,每一层的数据为N

所以其时间复杂度为==O(nlogn)==

空间复杂度为O(N)——因为要借助第三方的数组

归并排序和二叉树的后序遍历很相似,就会先左边有序,然后右边有序,最后进行归并!

void _MergeSort(int* a, int begin, int end, int* temp)
{
	//这个过程类似一个后续遍历
	int mid = (begin + end) /2; //如果使用链表的话,每次想要找到mid就很麻烦!
	if (begin >= end)
	{
		return;
	}
	_MergeSort(a, begin, mid, temp);
	_MergeSort(a, mid + 1, end, temp);
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	//进行归并
	while (begin1 <= end1 && begin2 <= end2)//有一个结束就全部结束
	{
		if (a[begin1] <= a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}
	}
   //因为不知道是那个先结束所以用两个循环
	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}
	while (begin2<=end2)
	{
		temp[i++] = a[begin2++];
	}
	memcpy(a + begin, temp + begin, (end - begin + 1)*sizeof(int));
   //memcpy要求传的是字节数!
	//拷贝会数组,归并那部分就是拷贝会那部分!
}

void MergeSort(int* a,int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	if (temp == NULL)
	{
		perror("malloc fail");
	}
	_MergeSort(a,0,size-1, temp);
	free(temp);
	temp = NULL;
}

image-20220929140117774.png

归并排序.gif

归并排序的非递归

归并排序的非递归麻烦在它是一个后序的逻辑!当我们分到最后的时候,归并完毕,我们该如何去寻找上一层的区间进行归并

这就很麻烦了!

所以我们可以考虑不要用栈和队列而是改成循环!

像是斐波那契数列也是一种后序,也可以改成循环!

image-20220929233351473.png

思路:两两归一,

void MergeSortNonR(int* a, int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	if (temp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap < size)
	{
		for (int j = 0; j < size; j += 2 * gap)
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
			int i = j;

			while (begin1 <= end1 && begin2 <= end2)//有一个结束就全部结束
			{
				if (a[begin1] <= a[begin2])
				{
					temp[i++] = a[begin1++];
				}
				else
				{
					temp[i++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[i++] = a[begin2++];
			}
		}

		memcpy(a, temp, sizeof(int) * size);//整体拷贝存在弊端
		gap *= 2;
	}
}

以上写法面临一些问题,就是面对奇数个数或在在gap改变过程中产生的奇数区间的时候会发生越界访问!

image-20220930190358696.png

image-20220930191136993.png

针对三种情况我们可以进行针对性的调整】

	
void MergeSortNonR(int* a, int size)
{
	int* temp = (int*)malloc(sizeof(int) * size);
	if (temp == NULL)
	{
		perror("malloc fail");
	}
	int gap = 1;
	while (gap < size)
	{
		for (int j = 0; j < size; j += 2 * gap)
		{
			int begin1 = j, end1 = j + gap - 1;
			int begin2 = j + gap, end2 = j + 2 * gap - 1;
			int i = j;

			if (end1 >= size)//第一种情况,第一组部分越界
			{
				break;
			}
			if (begin2 >= size)//第二种情况,第二组全部越界
			{
				break;
			}
			if (end2 >= size)//第三种情况,第二组部分越界,前面两种情况都无法在进行归并,因为第二组都在界外
				//但是第三种情况第二组只是部分初阶,可以通过调整从而继续进行归并
			{
				end2 = size - 1;
			}
			while (begin1 <= end1 && begin2 <= end2)//有一个结束就全部结束
			{
				if (a[begin1] <= a[begin2])
				{
					temp[i++] = a[begin1++];
				}
				else
				{
					temp[i++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				temp[i++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				temp[i++] = a[begin2++];
			}
			memcpy(a + j, temp + j, sizeof(int) * (end2 - j + 1));
		}
       // memcpy(a, temp, sizeof(int) * size);
		gap *= 2;
	}
}

但是这时候整体拷贝的弊端就出现了!

image-20220930192220612.png

归并排序总结

  1. 时间复杂度:O(N*logN)
  2. 空间复杂度:O(N)
  3. 稳定性:稳定

归并排序的最大缺点在于它的这个空间复杂度!所以归并排序的思考更多的是解决在磁盘中的==外排序问题==

外排序——不在内存中进行排序!

原文链接

扫描二维码推送至手机访问。

版权声明:本文来源于网络,仅供学习,如侵权请联系站长删除。

本文链接:https://news.layui.org.cn/post/1000.html

分享给朋友:

“数据结构【C语言版】五千字长文手把手带你手撕快速排序,归并排序!” 的相关文章

Python基础(九) | time random collections itertools标准库详解

⭐本专栏旨在对Python的基础语法进行详解,精炼地总结语法中的重点,详解难点,面向零基础及入门的学习者,通过专栏的学习可以熟练掌握python编程,同时为后续的数据分析,机器学习及深度学习的代码能力打下坚实的基础。 ????本文已收录于Python基础系列专栏: Python基础系列教程 欢迎订阅,持续更新。 Python自身提供了比较丰富的生态,拿来即用,可极大的提高开发效率 9...

分布式存储系统之Ceph集群存储池操作

  前文我们了解了ceph的存储池、PG、CRUSH、客户端IO的简要工作过程、Ceph客户端计算PG_ID的步骤的相关话题,回顾请参考https://www.cnblogs.com/qiuhom-1874/p/16733806.html;今天我们来聊一聊在ceph上操作存储池相关命令的用法和说明;   在ceph上操作存储池不外乎就是查看列出、创建、重命名和删除等操作,常用相关的工具都是“cep...

一次服务器被入侵的处理过程分享

下文中的,给文件和目录加锁,是指给文件和目录增加了一些属性,只读等。 chattr +ia 目录 一、服务器入侵现象 二、服务器排查和处理 2.1、服务器被入侵的可能原因 2.2、排查和处理步骤 三、本次入侵需要带来启示的点 四、本次服务器被入侵的一些启示 一、服务器入侵现象 近期有一个朋友的服务器(自己做了网站)好像遭遇了入侵,具体现象是: 服务器 CPU 资源长期 1...

【大话云原生】煮饺子与docker、kubernetes之间的关系

文章开始之前,我给大家推荐一个人工智能学习网站,首先说我之前是完全不涉及人工智能领域的,但是我尽然看懂了,以后老哥我就要参与人工智能了。如果你也想学习,点击跳转到网站 云原生的概念最近非常火爆,企业落地云原生的愿望也越发强烈。看过很多关于云原生的文章,要么云山雾罩,要么曲高和寡。 所以笔者就有了写《大话云原生》系列文章的想法,期望用最通俗、简单的语言说明白云原生生态系统内的组成及应用关系。那么,...

Ruoyi字典源码学习

此文章属于ruoyi项目实战系列 使用目的 什么是字典数据:具体的值(0,1,"Y","N"),对应具体的业务逻辑("男","女","是","否")。 字典数据不应该只写死在代码中,还应存入数据库,通过管理系统来增删改查。 源码分析 ruoyi项目在低于3.7.0的版本中,前端字典功能实现比较简单,每个index.vue页面都请求dict的api,获取数据再加工显示即可。3.7.0之后的版本使...

手把手带你使用单个标签+CSS实现复杂的棋盘布局

前端(vue)入门到精通课程:进入学习API 文档、设计、调试、自动化测试一体化协作工具:点击使用 最近,有群友问我,他们的一个作业,尽量使用少的标签去实现这样一个象棋布局: 他用了 60 多个标签,而他的同学,只用了 6 个,问我有没有办法尽可能的做到利用更少的标签去完成这个布局效果。 其实,对于一个页面的布局而言,标签越少不一定是好事,我们在考虑 DOM 的消耗的同时,也需要关注代码的可读性...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。