【数据结构与算法】常见的排序算法

文章目录

  • 排序的概念
  • 冒泡排序(Bubble Sort)
  • 插入排序(Insert Sort)
  • 选择排序(Select Sort)
  • 希尔排序(Shell Sort)
    • 写法一
    • 写法二
  • 快速排序(Quick Sort)
    • hoare版本(左右指针法)
    • 挖坑法
      • 递归法
      • 非递归法
    • 前后指针法
  • 堆排序
  • 归并排序


排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

冒泡排序(Bubble Sort)

优点:简单,易实现,稳定且不需要额外空间
缺点:效率低
升序思路:
两两比较,相邻的两个元素比较,第一个元素比第二个大就交换。此时最大的元素在最右边,再循环这个动作(最后一个元素不进入循环),直到循环截止,该数组为有序。

动图演示如下:
在这里插入图片描述
核心代码如下:

Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; j++)
	{
		for (int i = 0; i < n - j-1; i++)
		{
			if (a[i + 1] < a[i])
			{
				Swap(&a[i + 1], &a[i]);
			}
		}
	}
}

冒泡排序的特性总结:

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:最坏情况是O(N^2), 最好情况是O(N)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

插入排序(Insert Sort)

优点:效率略高于冒泡和选择排序,稳定
缺点:效率不高

升序思路:把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列
步骤:
1.从第一个元素开始(默认第一个元素为有序)
2.取下一个元素,从已有的有序元素中从左往右扫描
3.如果该元素大于新插进来的元素,则将该元素移动到下一个位置
4.重复步骤3,直到有序元素中找到小于或等于新元素的元素
5.将新元素插入到该元素后面
6.若有序元素全都大于新元素,则将新元素插入到第一位,即下标为0的位置

动图演示如下:
在这里插入图片描述
核心代码:

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 (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			//比该元素小就退出循环
			else
			{
				break;
			}
		}
		//把tmp元素插入到end后面一个(即插入到小的数后面一个)
		a[end + 1] = tmp;
	}
}

直接插入排序的特性总结:

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

选择排序(Select Sort)

优点:表现最稳定,时间复杂度永远O(N^2),不需要额外空间
缺点:稳定上讲,不稳定,效率低

基本思想:每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。

动图演示如下:
在这里插入图片描述
但我觉得这样稍微有一丢丢慢,可以优化一下,我们可以一次选两个值,一个最小值,一个最大值,分别将其放到序列开头和末尾处。

步骤:
1.首先在序列(未排序)中找到最小的值,放到序列起始位置
2.再找序列中最大的值,放到序列末尾处
3.重复以上动作,直到所有元素有序(即begin和end相遇停止)

核心代码:

void SelectSort(int* a, int n)
{
	//记录第一个和最后一个下标
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//保存最大值,最小值下标
		int mini = begin;
		int maxi = begin;
		//找出最大值和最小值的下标
		for (int i = begin; i <= end; i++)
		{
			//找到最小值,将mini最小值下标更新为i位置
			if (a[i] < a[mini])
			{
				mini = i;
			}
			//找到最大值,将maxi最大值下标更新为i位置
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		//此时最小值为序列开头处
		Swap(&a[mini], &a[begin]);
		//考虑到万一最大值在begin位置被mini换走,所以增加判断
		if (begin == maxi)
		{
			maxi = mini;
		}
		//此时最大值在序列末尾处
		Swap(&a[maxi], &a[end]);
		//begin往前后,不断更新
		++begin;
		//end往前走,不断更新
		--end;
	}
}

直接选择排序的特性总结:

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:最好情况和最坏情况都是O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

希尔排序(Shell Sort)

优点:效率高于三种简单排序,不需要额外空间
缺点:不稳定

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

步骤:
1.选择一个增量序列,通常为初始增量为数组长度的一半,然后逐步减小增量直至为1。
2.根据选定的增量对数组进行分组,每个分组包含间隔为增量的元素。
3.对每个分组进行插入排序,即将每个元素插入到正确的位置上,使得每个分组内的元素有序。
4.逐步减小增量,重复上述步骤,直到增量为1时完成最后一次插入排序。
5.最终得到一个有序数组。

动图演示如下:
在这里插入图片描述

写法一

思路图:
gap > 1 时是预排序,目的是让它接近有序
gap == 1 时是直接插入排序,目的是为了让它有序

在这里插入图片描述
核心代码:

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
	    //循环躺数
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				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;
				}
			}
		}
	}
}

写法二

多组并排
核心代码:

void ShellSort(int* a, 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 = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

希尔排序的特性总结:

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

时间复杂度:
在这里插入图片描述
空间复杂度:O(1)

快速排序(Quick Sort)

hoare版本(左右指针法)

步骤:
1.选出一个key,一般选最左边或者最右边的。(男左女右,这里我就选最左边的了)。
2.定义一个begin和一个end,begin从左往右走,end从右往左走。
注:若你选的key在左边,那右边的end就要先走,反之右边,则左边的begin需要先
3.假设end先走,往左走,在行走过程中,若end遇到小于key的值就停下来,这时候begin走,往右走,当begin遇到大于key的值也停下来,然后将begin和end内容交换,然后再end走…反复这样走直到begin和end相遇,将他们相遇的下标内容与key进行交换。
4.这时候key的左边都是小于key的,而key的右边都是大于key的。
5.以key为划分点,将它的左序列和右序列分别进行上面这种排序,直到左右序列都只剩一个数值,或者不存在数值,就停止。
在这里插入图片描述
核心代码:

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;
	int left = begin;
	int right = end;
	int keyi = begin;
	while (left < right)
	{
	    //选的key为左边,所以右边先走,右边找比key小的,&&前面的判断是为了防止left和right越界,或者说互相错过
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
		//右边走完左边走,左边找大,找比key大的值,和上面的循环一样
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
		//交换,目的是要把比key大的值都放key的左边,比key小的值都放key的右边
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	//区间
	//[begin,keyi-1] keyi [keyi+1,end]
	
	//递归
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

挖坑法

递归法

步骤:
1.选出一个数据,一般选最左边或者最右边的,思想与hoare版本类似,选出的数存在变量key中,此时,原来的位置就会形成一个空位坑位,所以叫做挖坑法。
2. 依旧是定义两个变量,一个往左走,一个往右走,和上面方法一样,若你的坑位在左边,右边就先走,否则左边先走。
…思路与hoare一样的
在这里插入图片描述

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

	int keyi = a[begin];
	int hole = begin;
	while (begin < end)
	{
		//右边找小,填到左边的坑
		while (begin < end && a[end] >= keyi)
		{
			--end;
		}
		a[hole] = a[end];
		hole = end;
		//左边找到,填到右边的坑
		while (begin < end && a[begin] <= keyi)
		{
			++begin;
		}
		a[hole] = a[begin];
		hole = begin;
	}
	a[hole] = keyi;
	return keyi;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

非递归法

核心代码:

void QuickSortNonR(int* a, int begin, int end)
{
	ST s;
	STInit(&s);
	STPush(&s, end);
	STPush(&s, begin);

	while (!STEmpty(&s))
	{
		int left = STTop(&s);
		STPop(&s);
		int right = STTop(&s);
		STPop(&s);

		int keyi = PartSort3(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		if (left < keyi - 1)
		{
			STPush(&s, keyi - 1);
			STPush(&s, left);
		}

		if (keyi + 1 < right)
		{
			STPush(&s, right);
			STPush(&s, keyi + 1);
		}
	}
	STDestroy(&s);
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort2(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

前后指针法

步骤:
还是一样的
1.选出一个key,选最左边的或者最右边的
2.首先定义prev指针在序列起始位置,然后定义指针cur在prev的下一个,即prev+1
3.cur遇到比key大的值,++cur
4.cur遇到比key小的值,++prev,交换prev和cur位置的值,再++cur
在这里插入图片描述
核心代码:

int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = prev + 1;
	int keyi = begin;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}
	Swap(&a[keyi], &a[prev]);
	keyi = prev;
	return prev;
}
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort3(a, begin, end);
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}

快速排序的特性总结:

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

堆排序

这个排序我们之前讲过的,这里我就不再复习啦~
需要的老铁请点这里----->堆、堆排序

堆排序的特性总结:

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

归并排序

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

步骤:
1.分解:将待排序的序列分解成若干个子序列,每个子序列包含1个元素。
2.合并:将相邻的子序列两两合并,形成新的有序子序列,直到无法再合并。
3.重复合并步骤直到得到最终的排序结果。

在这里插入图片描述
动态演示如下:

在这里插入图片描述
核心代码:

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

	//[begin,mid] [mid+1,end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin;
	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, sizeof(int) * (end - begin+1));
}
//归并排序
void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		printf("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
}

归并排序的特性总结:

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/611279.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

kaldi学习参考

HMM模型 https://www.cnblogs.com/baixf-xyz/p/16777438.htmlhttps://www.cnblogs.com/baixf-xyz/p/16777438.htmlGMM-HMM 基于GMM-HMM的语音识别系统https://www.cnblogs.com/baixf-xyz/p/16777439.html https://www.cnblogs.com/baixf-xyz/p/16777426.htmlhttps://www.cnbl…

Java入门基础学习笔记13——数据类型

数据类型的分类&#xff1a; 基本数据类型 引用数据类型 基本数据类型&#xff1a;4大类8种类型&#xff1a; 定义整形用int&#xff0c;再大的数用long。 package cn.ensource.variable;public class VariableDemo2 {public static void main(String[] args) {//目标&#x…

Python学习笔记------json

json简介 JSON是一种轻量级的数据交互格式。可以按照JSON指定的格式去组织和封装数据 JSON本质上是一个带有特定格式的字符串 主要功能&#xff1a;json就是一种在各个编程语言中流通的数据格式&#xff0c;负责不同编程语言中的数据传递和交互 为了让不同的语言能够相互通…

luceda ipkiss教程 69:导出器件或者线路的三维模型

ipkiss 3.12版加入write_obj函数&#xff0c;可以直接输出器件的三维模型。 如&#xff0c;输出自定义的mmi的三维模型&#xff1a; 代码如下&#xff1a; from si_fab import all as pdk from ipkiss3 import all as i3class MMI1x2(i3.PCell):"""MMI with …

【C++】学习笔记——优先级队列

文章目录 十、优先级队列1. priority_queue的介绍2. 优先级队列如何使小的数据优先级高3. 仿函数介绍4. priority_queue的模拟实现 补&#xff1a; 反向迭代器未完待续 十、优先级队列 1. priority_queue的介绍 优先级队列 其实也不属于队列&#xff0c;它跟 stack 和 queue …

【MQTT】mosquitto 的 “下载、交叉编译、使用” 详细教程,手把手搭建一个MQTT Broker

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…

ARIMA模型在河流水质预测中的应用_含代码

#水质模型 #时间序列 #python应用 ARIMA 时间序列模型简介 时间序列是研究数据随时间变化而变化的一种算法&#xff0c;是一种预测性分析算法。它的基本出发点就是事物发展都有连续性&#xff0c;按照它本身固有的规律进行。ARIMA(p,d,q)模型全称为差分自回归移动平均模型 (A…

单链表经典oj题(2)

前言 这次将要把剩下的oj题将以图解和自己的理解把它讲解完&#xff0c;希望对大家有所帮助&#xff0c;这次的讲解也是干货 第一题 21. 合并两个有序链表 - 力扣&#xff08;LeetCode&#xff09; ok这次就简单点&#xff0c;大家自己去看题目了 将两个升序链表合并为一个…

【Linux】进程的七大状态详解!

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …

如何查看centos7中Java在哪些路径下

在 CentOS 7 上&#xff0c;你可以通过几种方式查找安装的 Java 版本及其路径。以下是一些常用的方法&#xff1a; 1. 使用 alternatives 命令 CentOS 使用 alternatives 系统来管理同一命令的多个版本。你可以使用以下命令来查看系统上所有 Java 安装的配置&#xff1a; su…

C++动态内存管理:与C语言动态内存管理的差异之争

当你改错一行代码的时候&#xff1a; 当你想要重构别人的代码时&#xff1a; 目录 前言 一、C/C的内存分布 二、C/C语言中的动态内存管理 三、new与delete的实现原理 总结&#xff1a; 前言 在C中&#xff0c;内存管理是一个至关重要的主题。正确地管理内存可以避免内存泄…

上海AI Lab开源首个可替代GPT-4V的多模态大模型

与开源和闭源模型相比&#xff0c;InternVL 1.5 在 OCR、多模态、数学和多轮对话等 18 个基准测试中的 8 个中取得了最先进的结果。 上海AI Lab 推出的 InternVL 1.5 是一款开源的多模态大语言模型 (MLLM)&#xff0c;旨在弥合开源模型和专有商业模型在多模态理解方面的能力差距…

二、SPI协议

文章目录 总述1.SPI接口2. SPI工作模式3. SPI通信时序4. SPI协议 对比 UART协议&#xff08;上一篇文章刚介绍过uart协议&#xff0c;这里来对比一下&#xff09; 总述 SPI&#xff08;Serial Peripheral Interface&#xff09;是一种高速的、全双工、同步的串行通信总线&…

【影片欣赏】【指环王】【魔戒:国王归来 The Lord of the Rings: The Return of the King】

往期魔戒博客见&#xff1a; 【影片欣赏】【指环王】【魔戒&#xff1a;护戒使者 The Lord of the Rings: The Fellowship of the Ring】 【影片欣赏】【指环王】【魔戒&#xff1a;双塔奇谋 The Lord of the Rings: The Two Towers】 2004年发行&#xff0c;Special Extend…

副业兼职没那么难,视频号带货,1天稳定500,适合新手操作

向大家推荐一个项目&#xff1a;视频号书单号带货玩法。我已经实践了一段时间&#xff0c;并成功售出了1200多单&#xff0c;赚取了2万多元。这个项目表现相当出色&#xff0c;强烈推荐给大家&#xff01; 周周近财&#xff1a;让网络小白少花冤枉钱&#xff0c;赚取第一桶金 …

Linux vscode push报错fatal: Authentication failed

注意啊&#xff0c;Git基于密码的身份验证已经被删除了&#xff0c;所以这个报错发生时无论密码正确与否&#xff0c;以及参考比较旧的改bug教程&#xff0c;都没法提交。进入提示的网址&#xff0c;生成个人访问令牌就好了

200-500人规模工厂网络方案(中小企业网络)

一、方案概述 工厂一般有单独的弱电房&#xff0c;类似这种 里面采用的方案如下&#xff1a; 主要考虑有线、无线、财务、办公、访客等业务&#xff0c;便于维护管理和后续扩容 还需要 Wi-Fi覆盖零死角高速率&#xff0c;工作不卡顿 同时考虑AV反病毒、IPS入侵防御、用户准…

【MySQL数据库开发设计规范】之命名规范

欢迎点开这篇文章&#xff0c;自我介绍一下哈&#xff0c;本人姑苏老陈 &#xff0c;是一名JAVA开发老兵。 本文收录于 《MySQL数据库开发设计规范》专栏中&#xff0c;该专栏主要分享一些关于MySQL数据库开发设计相关的技术规范文章&#xff0c;定期更新&#xff0c;欢迎关注&…

python自动化生成ppt

使用Python和python-pptx创建PPT 在这篇博客中&#xff0c;我们将探讨如何使用Python库python-pptx来创建一个简单的PowerPoint演示文稿&#xff08;PPT&#xff09;。这个库允许我们以编程方式创建幻灯片、添加文本、图片、表格和自定义形状。 安装python-pptx 首先&#x…
最新文章