数据结构与算法-排序

在这里插入图片描述
🌞入冬 时寒 添衣 勿病 要开心

排序

  • 🎈1.排序的基本概念
  • 🎈2.排序的分类
    • 🔭2.1插入排序
      • 🔎2.1.1直接插入排序
      • 🔎2.1.2折半插入排序
      • 🔎2.1.3希尔排序
    • 🔭2.2交换排序
      • 🔎2.2.1冒泡排序
      • 🔎2.2.2改进的冒泡排序
      • 🔎2.2.3快速排序
    • 🔭2.3选择排序
      • 🔎2.3.1简单选择排序
      • 🔎2.3.2树形选择排序
      • 🔎2.3.3堆排序
    • 🔭2.4归并排序
    • 🔭2.5基数排序

🎈1.排序的基本概念

排序是计算机程序设计中的重要操作,它将一组数据元素的任意序列,排列成按关键字有序的序列。其确切的定义如下:
设有n个数据元素的序列为{R1,R2,R3,...Rn},其关键字序列为{k1,k2,k3,...kn},排列就是确定1,2,3...n的一种排列p1,p2,p3,...pn,使表中元素相应的关键字满足非递减的关系kp1<=kp2<=kp3<=...kpn,使得序列{R1,R2,...Rn}成为一个按关键字有序的序列Rp1<=Rp2<=Rp3<=...Rpn,这种操作称为排序。
如果待排序的表中,存在多个关键字相同的数据元素,经排序后这些相同的关键字的元素之间的相对次序保持不变,则称这种排序方法是稳定的。若具有相同关键字的数据元素之间的相对次序发生变化,则称这种排序方法是不稳定的。

🎈2.排序的分类

由于待排序数据元素的数量不同,使排序的过程涉及不同的存储器,可将排序分为内部排序和外部排序两大类。
内部排序:待排序数据元素全部存储在计算机内存中进行的排序过程。
外部排序:待排序的数据元素的数量较大,以致内存不能一次容纳全部数据元素,需要借助外存才能完成排序的过程。

🔎数据组织(采用顺序表的存储结构)

#define _CRT_SECURE_NO_WARNINGS 1
#define MaxSize 100
typedef int KeyType;//关键字类型定义为整型
typedef int InfoType;//
typedef struct
{
	KeyType key;//关键字项
	InfoType otherinfo;//其他数据项
}ElemType;
typedef struct
{
	ElemType r[MaxSize];
	int length;
}SqList;

🔭2.1插入排序

🔎2.1.1直接插入排序

假设待排元素存放在数组r[1...n]中,排序过程中的某一时刻,r划分分成两个子区间r[1..i-1]r[i..n](起始时i=2),其中前一个子区间r[1..i-1]为已排好序的有序子表,后一个子区间r[i..n]为当前为排好序的无序子表。直接插入排序的一趟操作是将当前无序子表的第一个元素r[i]插入到有序子表r[1..i-1]中适当位置上,使r[i..i]变为新的有序子表。依次类推,直到全部元素插入完成为止。

void InsertSort(SqList& L)
{
	int i, j;
	for (i = 2; i <= L.length; i++)
	{
		L.r[0] = L.r[i];//复制哨兵
		for (j = i - 1; L.r[0].key < L.r[j].key; j--)
		{
			L.r[j + 1] = L.r[j];//将关键字大于r[i].key的元素后移
		}
		L.r[j + 1] = L.r[0];//在j+1处插入元素r[i]
	}
}

✅例题:
在这里插入图片描述
🔎算法分析
最好情况:正序时插入排序关键字比较次数为:n-1
最坏情况:反序时插入排序关键字的比较次数为:(n+2)(n-1)/2
空间复杂度:直接插入排序算法只使用两个变量i和j两个辅助变量,与问题的规模无关,所以直接插入排序的空间复杂度为O(1).
稳定性:直接插入排序是一种稳定的排序方法。

🔎2.1.2折半插入排序

🔎由于插入第i个元素到r[1]r[i-1]之间时,前i个数据都是有序的,所以可以用折半查找的方法先在r[1]r[i-1]中找到插入位置,再通过移动元素进行插入。具体流程如下:

  1. r[low]r[high](初始时low=1,high=i-1)中采用折半查找方法找到插入位置high+1.
  2. r[high+1]r[i-1]中元素后移一个位置.
  3. r[high+1]=r[i].
void BinsertSort(SqList& L)
{
	int i, j, low, high, mid;
	for (i = 2; i <= L.length; i++)
	{
		L.r[0] = L.r[i];
		low = 1;
		high = i - 1;
		while (low <= high)
		{
			mid = (low + high) >> 1;
			if (L.r[0].key < L.r[mid].key)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (j = i - 1; j >= high + 1; j--)
		{
			L.r[j + 1] = L.r[j];
		}
		L.r[high + 1] = L.r[0];
	}
}

🔎算法分析
时间复杂度:n2
空间复杂度O(1).
稳定性:折半插入排序是一种稳定的排序方法。

🔎2.1.3希尔排序

📖希尔排序又称缩小增量排序。其基本思路如下:

  1. 取定一个小于nn为表中元素的个数)的整数作为第一个增量d1,把表的全部元素分成d1个组,所有相互之间距离为d1的元素放在同一个组中,各组内采用直接插入排序。
  2. 取第2个增量d2(d2<d1),重复上述分组和排序过程。
  3. 依次类推,直到增量dt=1(dt<dt-1<...d2<d1),此时所有元素在同一组中采用直接插入排序。
    :希尔排序每趟排序不一定产生有序区,在最后排序结束前,希尔排序不能保证在每趟中将一个元素放到最终位置上。
void ShellInSort(SqList& L, int d)
{
	int i, j;
	for (i = d + 1; i <= L.length; i++)
	{
		if (L.r[i].key < L.r[i - d].key)
		{
			L.r[0] = L.r[i];
			for (j = i - d; j > 0 && L.r[0].key < L.r[j].key; j -= d)
			{
				L.r[j + d] = L.r[j];
			}
			L.r[j + d] = L.r[0];
		}
	}
}
void ShellSort(SqList& L, int da[], int t)
{
	int i;
	for (i = 0; i < t; i++)
	{
		ShellInSort(L, da[i]);
	}
}

🔎算法分析
时间复杂度:n1.3
空间复杂度O(1).
稳定性:希尔排序是一种不稳定的排序方法。

🔭2.2交换排序

交换排序是一类借助比较和交换来进行排序的方法,其基本思想是两两比较待排序数据元素的关键字,发现两个数据元素的次序相反时就进行交换,直到元素有序为止。交换排序主要有冒泡排序和快速排序

🔎2.2.1冒泡排序

📝冒泡排序又称为起泡排序。其基本思想为:
对于n个待排序的数据元素r[1...n],r[1]r[2]比较,大者放在r[2]中,r[2]r[3]比较,大者放在r[3]中,依次类推,r[n-1]r[n]比较,大者放在r[n],这样经过一趟比较,r[1]r[n]中的最大值放在r[n]中;第二趟,对于n-1个待排序数据元素r[1...n-1],采用上述方法进行比较,r[1]r[n-1]的最大者放在r[n-1]中;依次类推,最后一趟对于两个待排序元素r[1..2],r[1]r[2]进行比较,大者放在r[2]中。上述过程共进行n-1趟完成冒泡排序。

void BubbleSort(SqList& L)
{
	int i, j;
	ElemType temp;
	for (i = L.length; i > 1; i--)
	{
		for (j = 1; j < i; j++)
		{
			if (L.r[j].key > L.r[j + 1].key)
			{
				temp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = temp;
			}
		}
	}
}

🔎算法分析
时间复杂度:n2
空间复杂度O(1).
查找次数n(n-1)/2
稳定性:冒泡排序是一种稳定的排序方法。

🔎2.2.2改进的冒泡排序

📖从上述算法可知,在某些情况下,第i(2<=i<=n)趟时数据元素已有序,但算法仍然执行后面几趟的比较。事实上,一旦算法中某一趟未出现任何元素交换,说明序列已有序,此时算法可结束。为此,改进的冒泡排序如下:

void BubbleSort(SqList& L)
{
	int i, j;
	int tag;
	ElemType temp;
	for (i = L.length; i > 1; i--)
	{
		tag = 0;
		for (j = 1; j < i; j++)
		{
			if (L.r[j].key > L.r[j + 1].key)
			{
				temp = L.r[j];
				L.r[j] = L.r[j + 1];
				L.r[j + 1] = temp;
				tag = 1;
			}
		}
		if (!tag)//该趟没有数据元素的交换则退出循环
			return;
	}
}

✅例题:
在这里插入图片描述
🔎算法分析
时间复杂度n
空间复杂度O(1).
查找次数n-1
稳定性:改进后的冒泡排序是一种稳定的排序方法。

🔎2.2.3快速排序

📖快速排序,又称分区交换排序,它是冒泡排序的一种改进排序方式。其基本思想是在待排序的n个数据元素中以某个数据元素(通常为第一个元素)作为支点,将其放在适当的位置,数据元素序列被划分成两个部分,其中左半部分数据元素小于等于支点,右半部分数据元素大于等于支点,该过程称为一趟快速排序。依次类推,对左右两部分分别进行快速排序的递归处理,直至数据元素序列按关键字有序为止。快速排序的划分方法如下:设两个指针i和j,开始分别指向表的开始与结束,任一时刻,支点保存于辅助变量temp,即temp=L.r[i].

  1. j>i&&L.r[j].key>=temp.key,则两种位置合适,j1,重复此过程;否则,两者位置不合适,L.r[i]=L.r[j].
  2. i<j&&L.r[i].key<=temp.key,则两者位置合适,i1,重复该过程;否则,两者位置不合适,L.r[j]=L.r[i].
  3. 重复上述过程,直至ij相等。
  4. L.r[i]=temp.
void QuickSort(SqList& L, int s, int t)
{
	int i = s, j = t;
	ElemType temp;
	if (s < t)
	{
		temp = L.r[s];
		while (i != j)
		{
			while (j > i && L.r[j].key >= temp.key)
				j--;
			L.r[i] = L.r[j];
			while (i < j && L.r[i].key <= temp.key)
				i++;
			L.r[j] = L.r[i];
		}
		L.r[i] = temp;
		QuickSort(L, s, i - 1);//左半区递归排序
		QuickSort(L, i + 1, t);//右半区递归排序
	}
}

🔎算法分析
最好情况时间复杂度nlog2n
最坏情况时间复杂度:n2,此时,比较次数为n(n-1)/2
空间复杂度O(log2n).
稳定性:快速排序是一种不稳定的排序方法。

🔭2.3选择排序

选择排序的基本思想是每一趟(n个数据元素序列共进行n-1趟排序),从待排序的数据元素中选出最小(或最大)的数据元素,顺序放在已排好序的子表的最后,直至全部元素有序为止。选择排序适合于从大量元素中选择部分排序元素的情形。例如,从10000个数据元素中选择出关键字大小为前20位的数据元素。

🔎2.3.1简单选择排序

简单选择排序思想是第i(1<=i<=n-1)趟排序开始时,从r[i..n]中选出关键字最小(或最大)的数据元素r[k](i<=k<=n)r[i]进行交换,经过n-1趟排序后,表r[1..n]递增(或递减)有序。

void SelectSort(SqList& L)
{
	int i, j, k;
	ElemType temp;
	for (i = 1; i < L.length; i++)
	{
		k = i;
		for (j = i + 1; j <= L.length; j++)
		{
			if (L.r[j].key < L.r[k].key)
				k = j;
		}
		if (k != i)//交换r[k]和r[i]
		{
			temp = L.r[i];
			L.r[i] = L.r[k];
			L.r[k] = temp;
		}
	}
}

🔎算法分析
比较次数n(n-1)/2
时间复杂度:n2
空间复杂度O(1).
稳定性:简单选择排序是一种不稳定的排序方法。

🔎2.3.2树形选择排序

树形选择排序,又称锦标赛排序,它是一种按照锦标赛的思路设计的选择排序方法,其每趟排序过程可用n个叶子结点的完全二叉树表示。每趟排序过程是:将nn一般为2的幂)个数据元素的关键字作为叶子结点,相邻的两个叶子结点进行两两比较,然后在其中n/2上取整个较小者(或较大者)之间再进行比较,重复该过程,直至选出最小(或最大)关键字的数据元素为止(此时完成一趟树形选择排序)。选出最小(后面以最小为例)关键字后,将叶子结点中的最小关键字改为“最大值”(如无穷),重复上述过程,直至所有元素有序为止。
在这里插入图片描述
🔎算法分析
时间复杂度O(nlog2n)
空间复杂度O(n).
稳定性:树形选择排序是一种稳定的排序方法。

🔎2.3.3堆排序

堆排列是一种树形选择排序,主要利用堆的特性进行排序。它的特点是在排序过程中,将r[1…n]看成一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点间的内在关系,在当前无序区中选择关键字最小(或最大)的数据元素。
在这里插入图片描述
✅排序思想:堆排序的关键是用筛选法建立堆,首先对待排序的数据元素序列构造出一个堆,此时选出了堆中所有数据元素的最小者(以小顶堆为例)为堆顶,随后将它从堆中移走(通常是将堆顶数据元素和堆中最后一个数据元素进行交换),并将剩余的数据元素再调整成堆,这样又找出了次小的数据元素,依次类推,直到堆中只有一个数据元素为止。

void SiftAdjust(SqList L, int s, int t)
{
	int i = s, j = 2 * i;
	ElemType temp = L.r[i];
	while (j <= t)
	{
		if (j<t && L.r[j].key>L.r[j + 1].key)
			j++;
		if (temp.key > L.r[j].key)
		{
			L.r[i] = L.r[j];
			i = j;
			j = 2 * i;
		}
		else break;
	}
	L.r[i] = temp;
}
void HeadSort(SqList& L)
{
	int i;
	ElemType temp;
	for (i = L.length / 2; i >= 1; i--)
	{
		temp = L.r[1];
		L.r[1] = L.r[i];
		L.r[i] = temp;
		SiftAdjust(L,1, i - 1);
	}
}

🔎算法分析
时间复杂度O(nlog2n)
空间复杂度O(1).
稳定性:堆排序是一种不稳定的排序方法。

🔭2.4归并排序

归并排序是多次将两个及两个以上的有序表合并成一个新的有序表的排序方法。最简单的归并排序是直接将两个有序的子表归并成一个有序表的2-路归并排序方法。
在这里插入图片描述

🔎算法分析
时间复杂度O(nlog2n)
空间复杂度O(n).
稳定性:归并排序是一种稳定的排序方法。

🔭2.5基数排序

设有n个数据元素序列r[1…n],且每个关键字r[i].key由d位数字Kd-1Kd-2…K0组成(或每个数据元素r[i]中含有d个关键字),其中Kd-1为最高位,K0为最低位,每一位的值都在0<=Ki<r,其中r称为基数。基数排序分为如下两种情形:
在这里插入图片描述

在这里插入图片描述
🔎算法分析
时间复杂度O(d(n+r))(r为基数)
空间复杂度O(r).
稳定性:基数排序是一种稳定的排序方法。


✅总结:
在这里插入图片描述

好啦,关于内部排序的知识到这里就先结束啦,后期会继续更新学习数据结构与算法的相关知识,欢迎大家持续关注、点赞和评论!❤️❤️❤️

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

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

相关文章

Python中的并发编程(7)异步编程

异步编程 Python3.4后新增了asyncio模块&#xff0c;支持异步编程。 异步是在一个线程中通过任务切换的方式让多个任务”同时“进展。asyncio不涉及线程/进程切换&#xff0c;减少了线程/进程创建、上下文切换的开销&#xff0c;更轻量级。 asyncio的核心是事件循环&#xff0…

【设计模式】外观模式

文章目录 前言一、外观模式1.案例2.优缺点3.使用场景4.源码解析 总结 前言 【设计模式】外观模式 一、外观模式 有些人可能炒过股票&#xff0c;但其实大部分人都不太懂&#xff0c;这种没有足够了解证券知识的情况下做股票是很容易亏钱的&#xff0c;刚开始炒股肯定都会想&am…

c语言:把二维数组降至一维|练习题

一、题目 把二维数组降为一围数组 如图&#xff1a; 二、代码截图【带注释】 三、源代码【带注释】 #include <stdio.h> int main() { int arr2[3][3];//设置二维数组 int arr1[10];//设置一维数组 int z0;//一维数组自增量 printf("输入一个二维数…

面试算法78:合并排序链表

题目 输入k个排序的链表&#xff0c;请将它们合并成一个排序的链表。 分析&#xff1a;利用最小堆选取值最小的节点 用k个指针分别指向这k个链表的头节点&#xff0c;每次从这k个节点中选取值最小的节点。然后将指向值最小的节点的指针向后移动一步&#xff0c;再比较k个指…

Net6 Core webApi发布到IIS

Net6 Core Api发布到IIS不同于webapi&#xff0c;依赖框架不同&#xff0c;配置也移至项目内Program.cs 一、发布到指定文件夹和IIS&#xff0c;不过注意IIS应用程序池选择的是 “无托管代码“ 在IIS管理器中点击浏览&#xff0c;访问接口路径报500.19&#xff0c;原因是所依赖…

【并发设计模式】聊聊线程本地存储模式如何实现的线程安全

前面两篇文章&#xff0c;通过两阶段终止的模式进行优雅关闭线程&#xff0c;利用数据不变性的方式保证数据安全&#xff0c;以及基于COW的模式&#xff0c;保证读数据的安全。本篇我们来简述下如果利用线程本地存储的方式保证线程安全。 首先一个大前提就是并发问题&#xff…

Python:将print内容写入文件

简介&#xff1a;print函数是Python中使用频率非常非常高的函数&#xff0c;其包含四个参数&#xff1a;sep、end、file、flush。 历史攻略&#xff1a; Python基础&#xff1a;输入、输出 Python&#xff1a;将控制台输出保存成文件 参数解析&#xff1a; print()函数可以…

07-项目打包 React Hooks

项目打包 项目打包是为了把整个项目都打包成最纯粹的js&#xff0c;让浏览器可以直接执行 打包命令已经在package.json里面定义好了 运行命令&#xff1a;npm run build&#xff0c;执行时间取决于第三方插件的数量以及电脑配置 打包完之后再build文件夹下&#xff0c;这个…

基于JavaSpringboot+Vue实现前后端分离房屋租赁系统

基于JavaSpringbootVue实现前后端分离房屋租赁系统 作者主页 500套成品系统 联系客服任你挑选 Java毕设项目精品实战案例《500套》 欢迎点赞 收藏 ⭐留言 文末获取源码联系方式 文章目录 基于JavaSpringbootVue实现前后端分离房屋租赁系统前言介绍&#xff1a;功能设计&#xf…

JavaWeb——前端之JSVue

接上篇笔记 4. JavaScript 概念 跨平台、面向对象的脚本语言&#xff0c;使网页可交互与Java语法类似&#xff0c;但是不需要变异&#xff0c;直接由浏览器解析1995年Brendan Eich发明&#xff0c;1997年成为ECMA标准&#xff08;ECMA制定了标准化的脚本程序设计语言ECMAScr…

杰发科技AC7840——EEPROM初探

0.序 7840和7801的模拟EEPROM使用不太一样 1.现象 按照官方Demo&#xff0c;在这样的配置下&#xff0c;我们看到存储是这样的&#xff08;连续三个数字1 2 3&#xff09;。 使用串口工具的多帧发送功能 看不出多少规律 修改代码后 发现如下规律&#xff1a; 前四个字节是…

HarmonyOS page生命周期函数讲解

下面 我们又要看一个比较重要的点了 页面生命周期 页面组件有三个生命周期 onPageShow 页面显示时触发 onPageHide 页面隐藏时触发 onBackPress 页面返回时触发 这里 我们准备两个组件 首先是 index.ets 参考代码如下 import router from ohos.router Entry Component struc…

06-C++ 类和对象-多态

类与对象 多态 1. 简介 一个事物的多种形态&#xff0c;简称多态。 物的多态 同一个人在不同人面前&#xff0c;角色不同 如&#xff1a; 在父母面前在对象面前在朋友面前在同事面前 事的多态 同一种事情&#xff0c;在不同情况下展现不同 如&#xff1a; 吃饭 中国人 筷子 …

NXP实战笔记(一):基于RTD-SDK新建一个S32DS工程

目录 1、概述 2、操作步骤 2.1、新建Application工程 2.2、命名工程、选择芯片型号、选择编译器GCC版本 2.3、配置基本参数 3、文件描述 3.1、文件结构描述 3.2、编译之后 4、下载调试 1、概述 安装了S32DS之后&#xff0c;导入SDK插件&#xff0c;这个步骤不赘述&…

世界经济论坛制定了五项指导原则,实现跨OT环境的网络安全。

内容概述&#xff1a; 世界经济论坛在其题为“解锁工业环境中的网络弹性&#xff1a;五项原则”的报告中列出&#xff1a;原则一&#xff1a;执行全面风险管理OT 环境、原则二&#xff1a;确保OT工程师和安装操作员对OT网络安全负责、原则三&#xff1a;与高层组织领导、战略规…

传感器原理与应用复习--光电式与半导体式传感器

文章目录 上一篇光电传感器光电器件 光纤传感器光纤传感器的工作原理及组成 半导体传感器下一篇 上一篇 光电传感器 光电器件 每个光子的能量为 E h v E hv Ehv h为普朗克常数 6.626 ∗ 1 0 − 34 ( J / s ) 6.626 * 10^{-34}(J/s) 6.626∗10−34(J/s) ν \nu ν 为光…

yolov5 主要流程

1.介绍 本文包含了有关yolov5目标检测的基本流程&#xff0c;包括模型训练与模型部署&#xff0c;旨在帮助小伙伴们建立系统的认知&#x1f496;&#x1f496; YOLO是 "You only look once "的首字母缩写&#xff0c;是一个开源软件工具&#xff0c;它具有实时检测…

【Java开发岗面试】八股文—Java框架(Spring+SpringMVC+MyBatis+SpringBoot)

声明&#xff1a; 背景&#xff1a;本人为24届双非硕校招生&#xff0c;已经完整经历了一次秋招&#xff0c;拿到了三个offer。本专题旨在分享自己的一些Java开发岗面试经验&#xff08;主要是校招&#xff09;&#xff0c;包括我自己总结的八股文、算法、项目介绍、HR面和面试…

IC入门必备!数字IC中后端设计实现全流程解析(1.3万字长文)

吾爱IC社区自2018年2月份开始在公众号上开始分享数字IC后端设计实现相关基础理论和实战项目经验&#xff0c;累计输出文字超1000万字。全部是小编一个个字敲出来的&#xff0c;绝对没有复制粘贴的情况&#xff0c;此处小编自己得给自己鼓鼓掌鼓励下自己。人生不要给自己设限&am…

web前端开发html/css求职简介/个人简介小白网页设计

效果图展示&#xff1a; html界面展示&#xff1a; html/css代码&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns"http://www.w3.…