iis服务器助手广告广告
返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C语言面试常见考点排序总结
  • 839
分享到

C语言面试常见考点排序总结

2024-04-02 19:04:59 839人浏览 独家记忆
摘要

排序算法有两块比较重要的知识点 内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指

排序算法有两块比较重要的知识点

  • 内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指空间复杂度是O(1)的排序算法。其中冒泡排序,插入排序、选择排序都属于原地排序算法
  • 稳定性:针对排序算法,我们还有一个衡量指标是稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后,相等元素之间原有的先后顺序不变。

例如我们有一组数据 2 9 3 4 8 3 按照从小到大的排序是 2 3 3 4 8 9,经过某种排序算法之后,如果两个3的前后顺序没有改变,就称为稳定的排序算法,否则就是不稳定的排序算法

算法名称 时间复杂度 是否稳定排序 是否原地排序
冒泡排序 O(N^2)
插入排序 O(N^2)
选择排序 O(N^2)
归并排序 O(nlogn)
快速排序 O(nlogn)
堆排序 O(nlogn)

冒泡排序

  • 平均复杂度是O(N^2)
  • 最好情况是O(1) 本身就是排好序的
  • 最坏就是倒序O(N^2)
  • 空间复杂度是O(1)

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复 n 次,就完成了 n 个数据的排序工作。


class Sort{
public:
	void Maopao_Sort(vector<int> &arr){
		//1.判断溢出条件
		if(arr.size() <2) return;
		int length =arr.size(); 
		for(int i =0;i < length;i++){
			for(int j=0; j < length -i -1 ;j++){
				if(arr[j] >arr[j+1]){
					int temp = arr[j];
					arr[j]= arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
	}		
};

插入排序

插入排序思想的由来,其实就是按照在一个有序的数组中插入一个元素的思想,找到合适的位置进行插入并迁移后面的元素

首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。


class Sort{
public:
	void Insert_Sort(vector<int> &arr){
		//1.判断溢出条件
		if(arr.size() < 2) return;
		int length =arr.size();
		int j =0;//初始的已排序区间的下标 
		for(int i =1;i < length ;i++){ //从未排序的区间里面取元素
			int temp =arr[i];
			j =i-1;    //不断更新已排序区间
			while(j >= 0 && temp <a[j]){
				//如果小的话就往后移动,找到合适的插入位置 
				arr[j+1]=arr[j];
				j--; 
			} 
			arr[j+1]=temp;  //插入元素 
		} 
	}
};

选择排序

选择排序算法的实现思路有点类似插入排序,也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾


class Sort{
public:
	void Select_Sort(vector<int> &arr ,int length){
		for(int i =0;i < length -1;i++){
			int min_number =arr[i];
			int flag = i;
			for(int j =i;j <length ;j++){
				if(min_number > arr[j]){
					min_number = arr[j];
					flag =j;
				}
			}
			//交换数字
			arr[flag] =arr[i];
			arr[i]=min_number; 
		}
	}
}; 

归并排序

归并排序是由下而上,采用分治的思想,把数据先拆分在合并,并把合并后的数据存入临时数组中,保证原先的数据位置不发生变化,是一种稳定的排序但不是原地排序,时间复杂度是O(nlogn),空间复杂度是O(N)


class Sort{
public:
	//归并排序 
	void MergeSort(vector<int> & arr){
		if(arr.size() < 2){
			return ;
		} 
		//拆分函数 
		Merge_Process(arr,0,arr.size())-1);
	}
	//先拆分,这是拆分函数 
	void Merge_Process(vector<int> &arr,int start,int end){
		//递归拆分,首先需要递归的终止条件
		if(end -start == 0) return;
		int mid =((end -start)/2) +start;
		Merge_Process(arr,start,mid);
		Merge_Process(arr,mid+1,end);
		//在合并
		Merge(arr,start,mid,end); 
	} 
	//合并函数
	void Merge(vector<int> &arr,int start,int mid, int end){
		vector<int> temp(end-start+1,0);//初始化一个临时数组
		int tempIndex =0; //辅助空间索引
		int leftIndex =start;
		int rightIndex =mid+1;
		while(leftIndex <= mid && rightIndex <= end){
			if(leftIndex <rightIndex){
				temp[tempIndex++] =arr[leftIndex++]; 
			}else{
				temp[tempIndex++] =arr[rightIndex++];
			}	 
		}
		while(leftIndex <= mid){
			temp[tempIndex++]=arr[leftIndex++];
		} 
		while(rightIndex <= end){
			temp[tempIndex++]=arr[rightIndex++];
		}
		for(int i =0;i< temp.size();i++){
			arr[start+i]=temp[i];
		}
	}
}; 

快速排序

快速排序是先分区,在处理子问题,通过找到区间后取得任意一个分区点,小的放分区点左边,大的放分区点右边,时间复杂度是O(nlong),空间复杂度是O(1),是原地排序但不是稳定排序

快排优化的话,有:三数取中法,和随机法,都是为了防止要排序的数组中有重复元素,这块我演示的是随机法


class Sort{
public:
	void quickSort(vector<int> &arr,int begin, int low){
		if(begin <end){
			//产生一个随机值 
			int index =rand()%(end-begin+1)+begin;
			//然后把产生的这个随机值,替换到数组的首位 
			swap(arr[begin],arr[index]); 
			int i =begin;
			int j =end;
			int base =arr[i];//基准位
			while(i <j){
				while(i<j&& arr[j] >= base){
					j--;
				}
				num[i]=num[j];
				while(i<j && arr[i] < base){
					i++;
				}
				num[j]=num[i];
			}
			//回归基准位 
			num[i]=base;
			//递归开始处理子问题 
			quickSort(arr,begin,i-1);
			quickSort(arr,i+1,end); 
			 
		}
	}
}; 

以上就是C语言面试常见考点排序总结的详细内容,更多关于C语言 排序的资料请关注编程网其它相关文章!

--结束END--

本文标题: C语言面试常见考点排序总结

本文链接: https://www.lsjlt.com/news/158087.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

本篇文章演示代码以及资料文档资料下载

下载Word文档到电脑,方便收藏和打印~

下载Word文档
猜你喜欢
  • C语言面试常见考点排序总结
    排序算法有两块比较重要的知识点 内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指...
    99+
    2024-04-02
  • C语言常见排序算法归并排序
    目录前言 一、归并排序1.1 基本思想1.2 算法思想1.3 程序设计思想1.4 程序实现1.5 归并排序的特性总结前言 本期为大家带来的是常见排序算法中的归并排序,博主在...
    99+
    2024-04-02
  • 大厂面试常考:快速排序冒泡排序算法
    目录一、概念二、基本思想三、算法步骤四、具体示例五、快排代码基本排序方式详图: 一、概念 快速排序,顾名思义就是一种以效率快为特色的排序算法,快速排序(Quicksort)是对冒泡...
    99+
    2024-04-02
  • C语言常见的面试题有哪些
    这篇文章主要讲解了“C语言常见的面试题有哪些”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“C语言常见的面试题有哪些”吧!第1题:c语言有哪些核心的特征可移植性很强。模块化能力很强。灵活性很高...
    99+
    2023-06-04
  • C语言常见排序算法之交换排序(冒泡排序,快速排序)
    目录前言1.交换排序——冒泡排序1.1 算法思想1.2 动图演示1.3 冒泡最好的情况 2. 交换排序——快速排序...
    99+
    2024-04-02
  • 考前必读:Go语言考试常见问题解答
    考前必读:Go语言考试常见问题解答 Go语言作为一门快速发展的编程语言,其在企业级应用开发中已经逐渐得到广泛应用。对于想要提升自己的技能水平或参加相关考试的同学来说,熟练掌握Go语言是...
    99+
    2024-04-02
  • C语言数据结构中堆排序的分析总结
    目录一、本章重点 二、堆2.1堆的介绍(三点)2.2向上调整2.3向下调整2.4建堆(两种方式)三、堆排序一、本章重点  堆向上调整向下调整堆排序 二、堆 2.1...
    99+
    2024-04-02
  • C语言数据结构与算法之排序总结(一)
    目录一、前言二、基本概念1.排序2.排序方法的稳定性3.内部和外部排序三、插入类排序1.直接插入排序2.折半插入排序3.希尔排序四、交换类排序1.冒泡排序2.快速排序五、总结比较一、...
    99+
    2024-04-02
  • C语言数据结构与算法之排序总结(二)
    目录一、前言二、选择类排序1.简单选择排序2.树形选择排序3.堆选择排序三、归并排序四、分配类排序1.多关键字排序2.链式基数排序五、总结归纳一、前言 之前的排序总结(一)对插入类和...
    99+
    2024-04-02
  • JavaScript中六种面试常考继承方式总结
    目录原型链继承盗用构造函数组合继承原型式继承寄生式继承寄生式组合继承js的几种继承方式在我们面试的时候经常会被问到,所以深入理解js几种继承方式以及它们的优缺点是非常有必要的。 原型...
    99+
    2023-02-13
    JavaScript继承方式 JavaScript继承
  • C语言常见排序算法之插入排序(直接插入排序,希尔排序)
    目录前言一、直接插入排序1.1 基本思想1.2 算法思想1.3 程序实现1.4 直接插入排序的总结二、希尔排序2.1 算法思想2.2 程序实现2.3 希尔排序的特征总结前言...
    99+
    2024-04-02
  • java中几种常见的排序算法总结
    目录本节目标;【插入排序】【优化版】【希尔排序】【选择排序】【堆排序】 【冒泡排序】介绍一个冒泡排序的优化方法; 【快速排序】【归并排序】【正文】【代码简介;】&...
    99+
    2024-04-02
  • javascript 函数是 Python 面试中常见的考点吗?
    JavaScript 函数是 Python 面试中常见的考点吗? JavaScript 和 Python 都是非常流行的编程语言,它们在不同的领域中都有广泛的应用。在编程语言的学习和面试中,函数是非常重要的概念,因此我们需要深入了解 Jav...
    99+
    2023-08-22
    面试 javascript 函数
  • R语言常量知识点总结
    R语言基本的数据类型有数值型, 逻辑型(TRUE, FALSE),文本(字符串)。 支持缺失值,有专门的复数类型。 常量是指直接写在程序中的值。 数值型常量包括整型、单精度、双精度等...
    99+
    2024-04-02
  • React-hooks面试考察知识点汇总小结(推荐)
    目录什么是hooks?解决了什么问题?Hook 简介Hook APIuseState指定初始 state惰性初始化自定义 Hook什么是hooks?解决了什么问题? Hooks 是r...
    99+
    2024-04-02
  • R语言常见面试题整理
    尊敬的读者,这些R语言面试题是专门设计的,以便您应对在R语言相关面试中可能会被问到的问题。 根据我的经验,良好的面试官几乎不打算在你的面试中问任何特定的问题,通常都是以如下的问题为开...
    99+
    2024-04-02
  • 深入学习C语言中常见的八大排序
    目录冒泡排序1.算法描述2.动图展示3.图解展示4.代码实现5.冒泡排序的优化6.复杂度分析插入排序1.算法描述2.动图展示3.图解展示4.代码实现5.复杂度分析希尔排序1.算法描述...
    99+
    2024-04-02
  • Redis中一些最常见的面试问题总结
    前言 经过长达一周的奔波和面试,电话面试,回首今天终于成功的入职了,总共面试了大概10家公司,包括阿里,京东,IBM等等,京东技术过了,学历因为非统招就被pass了,阿里面了2次电话面试就没下文了,估计是我...
    99+
    2024-04-02
  • 面试常见问题之C语言与C++的区别问题
    目录C和C++的区别关键字static在C和C++区别1.定义局部静态变量2.限定访问区域答案结构体在C语言和C++的区别C中malloc和C++的new区别C++引用和C的指针有何...
    99+
    2024-04-02
  • C语言数组全面总结梳理
    目录一,一维数组1.创建和初始化2.使用下标访问3.在内存中的存储二,二维数组 1.创建和初始化2.使用下标访问3.在内存中的存储三,越界问题数组(array)是由一系列类...
    99+
    2024-04-02
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作