408复试day2(7大排序算法)

这篇具有很好参考价值的文章主要介绍了408复试day2(7大排序算法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

数据结构

7大排序算法总结:
首先排序分为内排序和外排序:
内排序是指待排序的记录放置在内存,而外排序是指排序的过程中需要对内存进行访问。其中稳定的排序有“插冒归”,即插入排序、冒泡排序、归并排序。
1.冒泡排序
算法原理:
①初始时有序区为空,即全部记录为无序区;
②在无序区中从后往前依次比较相邻记录,如果是逆序,则交换
③每趟排序时,无序区关键字最小的记录被逐渐交换到有序区的第一位,即加入到有序区
④如果一趟排序时没有发生过交换,则提前结束
代码实现:

void BubbleSort(ElemType L[],int n){
	int i,j;
	bool exchange;//记录是否发生交换的标志
	ElemType tem;
	for(i=0;i<n-1;i++){//最多进行n-1趟冒泡排序
		exchange=false;
		for(j=n-1;j>i;j--){//一趟冒泡排序
			if(L[j]<L[j-1]){//前大后小,即逆序就交换
				tem=L[j];
				L[j]=L[j-1];
				L[j-1]=tem;
				//交换过之后就改变exchange的值
				exchange=true;
			}
			if(exchange==false){
				return;
			}
		}
	}
}

冒泡排序的算法评价:
1>待排序序列为正序:比较次数n-1,交换次数为0;
2>待排序序列为逆序:比较次数为 n(n-1)/2,交换次数为 n(n-1)/2
2.快速排序
每趟排序使一个元素放入其最终位置,这一个元素称为枢轴,通常选排序的第一个元素。
枢轴把整个序列划分为两个子序列,利用递归分别对子序列重复上述相同过程,直至子序列长度为0或1为止。
划分方法:
选待排序列的第一个元素作为枢轴x
设置变量:
low指向序列的前端
high指向序列的后端
high和low依次从序列的两端交替向序列中央扫描,将小于x的元素移到枢轴的左边,将大于或等于x的元素移到枢轴的右边
代码实现

void QuickSort(ElemType L[],int s,int e){
	int low=s,high=e;//本次划分范围
	ElemType x = L[s];//序列第一个元素作为枢轴
	whlie(low<high){//内循环①从右到左查找比枢轴小的元素
		while(low<high&&L[high]>=x){
			high--;
		}
		L[low]=L[high];//将小数放在左侧小数序列中,内循环②从左到右查找比枢轴大或相等的元素
		while(low<high&&L[low]<x){
			low++;
		}
		L[high]=L[low];//将大数放在右侧大数序列中
	}//循坏结束时low、high重合
	L[low]=x;//确定枢轴的最终存放位置
	if(s<low-1) QuickSort(L,s,low-1);//对左侧小数序列进行递归划分
	if(high+1<e) QuickSort();//对右侧大数序列进行递归划分
}

算法性能分析:
时间复杂度:最好情况,每次都选到的是中间值作为枢轴O(nlog 2 _2 2n);最坏情况,每次总是选到最小或最大元素作枢轴O(n2)
空间复杂度:需要栈空间实现递归
3.归并排序
归并排序将两个或多个有序序列合并为一个新的有序序列的过程,最简单的归并排序就是将两个有序序列合并为一个有序序列的过程,称为二路归并排序。
注意:只含有一个记录的序列显然是有序序列,将一个长度为n的无序序列看成是由n个长度为1的有序子序列组成。
把有些子序列中相邻的子序列两两归并,得到n/2个长度为2的有序子序列。
再把这些子序列两两归并,如此重复,直至形成一个长度为n的有序序列。
算法性能分析:
时间复杂度:O(nlog 2 _2 2n),每一趟归并的时间复杂度为O(n),总共需要进行log 2 _2 2n趟
4.直接插入排序
序列分为有序区和无序区。每次取无序区的第一个元素按其关键字大小插入到有序区的适当位置。
初始时,指定待排序的第一个元素构成有序区。其余元素构成无序区。
每趟排序时,待插入元素为无序区的第一个元素。
从后向前比较,当前元素如大于待插入元素,则向后移动。
每次插入后,有序区增加一个元素,无序区减少一个元素
无序区为空时,排序结束。
性能分析:
基本操作:比较和移动的次数,决定了排序的时间性能。
待排序列为“正序”时,比较和移动的次数最少;
待排序列为“逆序”时,比较和移动的次数最多。
5.简单选择排序
序列分为有序区和无序区。每次从无序区选出关键字最小的元素与无序区的第一个元素交换,此时有序区多一个元素。
要点:
初始时,有序区为空,全部元素位于无序区
每趟排序时,选择无序区关键字最小的元素与无序区的第一个元素交换
每次选择并交换后,有序区增加一个元素,无序区减少一个元素
当无序区剩下最后一个元素时,排序即可结束。
6.希尔排序
本质上是在插入排序算法的基础上进行的改进,就是先将待排序列分割成若干子序列分别进行插入排序,待整个序列中的记录“基本有序“时,再对全体记录进行一次直接插入排序
首先选择一个增量序列t1,t2……tk.令tk=1
按增量序列个数k,对序列进行k趟排序
每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m的子序列,分别对各子表进行直接插入排序。仅增量因子为1时,整个序列作为一个表来处理,表长度即为整个序列的长度。
7.堆排序
即要满足堆积的性质,即子结点的键值一定大于或小于其父结点(根节点),其中每个结点的值大于等于其左右孩子结点的值,称为大根堆(大顶堆),反之,若每个结点的值都小于等于其左右孩子结点的值,称为小根堆(小顶堆)。
原理:
1.将初始待排关键字序列(R1,R2…………Rn)构建成大顶堆,此堆为初始的无序区;
2.将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2…………Rn-1)和新的有序区(Rn),且满足R[1,2,……n-1]<=R[n].
3.由于交换后新的堆顶R[1]可能会违反堆的性质,因此需要对当前无序区调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区和新的有序区。不断重复此过程直到有序区的元素个数为n-1,则排序完。文章来源地址https://www.toymoban.com/news/detail-617032.html

到了这里,关于408复试day2(7大排序算法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构的练习day2(未完待续)

    数据结构线性结构之单向循环链表的基本操作

    2024年04月24日
    浏览(35)
  • 数据结构——排序算法——归并排序

    在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历

    2024年02月09日
    浏览(41)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(48)
  • 数据结构和算法笔记4:排序算法-归并排序

    归并排序算法完全遵循分治模式。直观上其操作如下: 分解:分解待排序的n个元素的序列成各具n/2个元素的两个子序列。 解决:使用归并排序递归地排序两个子序列。 合并:合并两个已排序的子序列以产生已排序的答案。 我们直接来看例子理解算法的过程,下面是要排序

    2024年01月21日
    浏览(61)
  • 【数据结构与算法】十大经典排序算法-插入排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 插入排序(Insertion Sort)是一种简单直观的排序算法,其基本思想是将一个记录插入到已排好序的有序序列中,直到所有记录

    2024年02月13日
    浏览(80)
  • 【数据结构与算法】十大经典排序算法-冒泡排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌴 掘金 :HelloCode 🌞 知乎 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 冒泡排序(Bubble Sort)是一种简单的排序算法,它通过重复地交换相邻元素的位置来将最大(或最小)的元素逐步“冒泡”到

    2024年02月14日
    浏览(69)
  • 【数据结构与算法】十大经典排序算法-快速排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 快速排序(Quick Sort)是一种高效的排序算法,是对冒泡排序的优化。它采用分治法(Divide and Conquer)的思想,将待排序序列

    2024年02月13日
    浏览(62)
  • 【数据结构与算法】十大经典排序算法-希尔排序

    🌟 个人博客: www.hellocode.top 🏰 Java知识导航: Java-Navigate 🔥 CSDN: HelloCode. 🌞 知乎 :HelloCode 🌴 掘金 :HelloCode ⚡如有问题,欢迎指正,一起学习~~ 希尔排序是一种插入排序的改进版本,旨在解决插入排序在处理大规模数据时的效率问题。通过将数组分为多个子序列并对

    2024年02月12日
    浏览(75)
  • 数据结构——排序算法之快速排序

        个人主页: 日刷百题 系列专栏 : 〖C/C++小游戏〗 〖Linux〗 〖数据结构〗   〖C语言〗 🌎 欢迎各位 → 点赞 👍+ 收藏 ⭐️+ 留言 📝  ​ ​ 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。 基本思想: 任取待排序元素序列中 的某元素作为基准值,按照

    2024年01月21日
    浏览(54)
  • 【数据结构与算法】排序算法(选择排序,冒泡排序,插入排序,希尔排序)

    基本概念这了就不浪费时间解释了,这四种都是很简单的排序方式,本专栏后续文章会出归并排序,计数排序,快速排序,堆排序,桶排序等排序算法,今天这篇文章中给出选择排序,冒泡排序,插入排序和希尔排序的实现; 如果发现文章中有错误,还请大家指出来,我会非

    2024年02月15日
    浏览(81)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包