首页 > 编程语言 >校招常见七大排序C++版（适合新人，通俗易懂）

校招常见七大排序C++版（适合新人，通俗易懂）

时间：2024-06-21 18:30:09浏览次数：20  
标签：int res 复杂度 通俗易懂 ++ C++ 数组 校招 排序

作者：求一个demo

版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

内容通俗易懂，没有废话，文章最后是面试常问内容

是否稳定最优、最坏、平均时间复杂度最优、最坏、平均空间复杂度
冒泡排序是O(n)、O(n^2)、O(n^2)0、O(n)、O(1)
选择排序否O(n^2)、O(n^2)、O(n^2)O(1)、O(1)、O(1)
插入排序是O(n)、O(n^2)、O(n^2)O(1)、O(1)、O(1)
桶排序是O(n)、O(n^2)、O(n)O(n)、O(n)、O(n)
堆排序否O(nlogn)、O(nlogn)、O(nlogn)O(1)、O(1)、O(1)
快速排序否O(nlogn)、O(n^2)、O(nlogn)O(logn)、O(n)、O(logn)
归并排序是O(nlogn)、O(nlogn)、O(nlogn)O(n)、O(n)、O(n)

 

 

一、冒泡排序

描述：相邻两个进行比较，一轮遍历之后，把最大值放到了最后，接着一直循环查找

1、代码样例

#include <iostream>
#include <vector>

using namespace std;

void selectSort(vector<int>&res,int n) {
	for (int i = n; i > 0;i--) {
		bool ret = true;
		for (int j = 0; j < i - 1;j++) {
			if (res[j]>res[j+1]) {
				swap(res[j],res[j+1]);
				ret = false;
			}
		}
		if (ret == true) {
			return;
		}
	}
}

void selectPrint(vector<int>&res) {
	for (int i = 0; i < res.size();i++) {
		cout << res[i] << " " ;
	}
	cout << endl;
}

int main() {
	vector<int>res = {4,2,5,3,1};
	selectSort(res,res.size());
	selectPrint(res);
	return 0;
}

2、复杂度分析 

首先，讲述一下时间复杂度和空间复杂度区别：

①时间复杂度主要是看算法的执行时间，也就是算法处理数据所需的时间是多少。例如for循环里面嵌套一个for循环，两个for循环都是循环n次，那么时间复杂度就是n*n，也就是O( n^2 )；O(1)表示时间复杂度是常数，是最理想的。

②空间复杂度主要是看算法在执行过程中占用了多少的存储空间，也就是算法所需要的空间资源。例如O(1)表示算法的空间复杂度不随问题规模的变化而变化，即占用固定大小存储空间；O(n)或O(n^2)表示算法的空间复杂度与问题的规模成正比，只是增长幅度不同。

（1）时间复杂度

最优时间复杂度：O( n )，即待排序的元素已经完全有序时，一次遍历即可完成排序。

最坏时间复杂度：O( n^2 )，即待排序的元素逆序排序时。

平均时间复杂度：O( n^2 )，即待排序元素正常乱序的话一般是两个嵌套的for循环进行查找。

（2）空间复杂度

最优空间复杂度：0，即待排序元素已经排好序了，不需要排序了。

最坏空间复杂度：O(n)，即待排序元素逆序排序。

平均空间复杂度：O(1)，即平均下来该算法占用某固定大小的存储空间。

二、选择排序

描述： 数组中从头遍历一遍，找到最大值之后，和数组最后一个值交换位置，然后继续寻找。遍历第二遍，找到除数组最后一个位置的最大值之外的最大值，然后和数组倒数第二个位置交换。依次这样进行，将数组进行从小到大排序。

1、代码样例

#include <iostream>
#include <vector>

using namespace std;

void selectSort(vector<int>&res,int n) {
	//i代表待排序数组的个数，下标为0到i-1
	for (int i = n; i > 1; i--) {
		//第一步：找到最大值，并记录它的下标
		int max = res[0];
		int maxindex = 0;
		for (int j = 1; j < i;j++) {
			if (max < res[j]) {
				max = res[j];
				maxindex = j;
			}
		}
		//最大的数放在最后面
		swap(res[maxindex],res[i-1]);
	}
}

void selectPrint(vector<int>&res) {
	for (int i = 0; i < res.size();i++) {
		cout << res[i] << " " ;
	}
	cout << endl;
}

int main() {
	vector<int>res = {4,2,5,3,1};
	selectSort(res,res.size());
	selectPrint(res);
	return 0;
}

2、复杂度分析

（1）时间复杂度

最优时间复杂度：O( n^2 )，即待排序的元素已经完全有序，仍需两个for循环（第一个for循环表示待排序元素个数，第二个for循环找到最大值并记录下标）。

最坏时间复杂度：O( n^2 )，即待排序的元素逆序排序时，仍需两个for循环。

平均时间复杂度：O( n^2 )，即待排序元素正常乱序的话，需要两个for循环。

（2）空间复杂度

最优空间复杂度：O(1)。

最坏空间复杂度：O(1)。

平均空间复杂度：O(1)。

三、插入排序

描述：分为有序区和无序区。有序区起初默认为一个元素，无序区元素和有序区最后一个元素比较，如果小于有序区最后一个元素，再和有序区倒数第二个元素比较，以此类推，最后插入到合适的位置。

1、代码样例

#include <iostream>
#include <vector>

using namespace std;

void selectSort(vector<int>&res,int n) {
	for (int j = 1; j < n;j++) {
		int i = j - 1;
		while (i>=0 && res[i]>res[i+1]) {
			swap(res[i],res[i+1]);
			i--;
		}
	}
}

void selectPrint(vector<int>&res) {
	for (int i = 0; i < res.size();i++) {
		cout << res[i] << " " ;
	}
	cout << endl;
}

int main() {
	vector<int>res = {4,2,5,3,1};
	selectSort(res,res.size());
	selectPrint(res);
	return 0;
}

2、复杂度分析

（1）时间复杂度

最优时间复杂度：O( n )，即待排序的元素已经完全有序时，插入排序只需每次比较一次就可确定当前元素位置。

最坏时间复杂度：O( n^2 )，即待排序的元素逆序排序时，每次插入都需将当前元素逐个与已排序元素进行比较。

平均时间复杂度：O( n^2 )，即待排序元素正常乱序的话，每个元素比较和移动的次数都接近1/2。

（2）空间复杂度

最优空间复杂度：O(1)。

最坏空间复杂度：O(1)。

平均空间复杂度：O(1)。

 四、桶排序

描述（此算法思路以下面四步为例）：

第一步：找到数组a中最大值max。

第二步：申请一个数组b（桶），大小为max+1，即下标为0到max。

第三步：把数组a中元素值与数组b下标对应，并使数组b下标对应的值进行++。

第四步：最后遍历数组b，从小到大存入数组a，进行输出。

1、代码样例

#include <iostream>
#include <vector>

using namespace std;

void selectSort(vector<int>&res) {
	if (res.size() == 0) {
		return;
	}
	int max = res[0];//max用来存放数组最大值
	for (int i = 1; i < res.size();i++) {//找到数组最大值，方便申请桶大小
		if (res[i]>max) {
			max = res[i];
		}
	}
	vector<int>max_res(max+1,0);
	for (int i = 0; i < res.size();i++) {//数组中值存到桶里
		max_res[res[i]]++;
	}
	int index = 0;
	for (int i = 0; i < max_res.size();i++) {
		while (max_res[i]) {
			res[index++] = i;
			max_res[i]--;
		}
	}
}

void selectPrint(vector<int>&res) {
	for (int i = 0; i < res.size();i++) {
		cout << res[i] << " " ;
	}
	cout << endl;
}

int main() {
	vector<int>res = {4,2,5,3,1};
	selectSort(res);
	selectPrint(res);
	return 0;
}

2、复杂度分析 

（1）时间复杂度

最优时间复杂度：O( n )，即待排序元素分布均匀时（k为桶的个数）。

最坏时间复杂度：O( n^2 )，即所有待排序元素都在一个桶中。

平均时间复杂度：O( n)。

（2）空间复杂度

最优空间复杂度：O(n)，需要额外空间来存储桶和桶内元素。

最坏空间复杂度：O(n)。

平均空间复杂度：O(n)。

五、堆排序

描述：

1、代码样例

#include <iostream>
#include <vector>

using namespace std;

void adjustHeap(vector<int>&res,int start,int end) {
	int father = start;
	int leftChild = start * 2 + 1;
	int rightChild = leftChild + 1;
	int maxChild = leftChild;//记录最大孩子的下标
	while (leftChild < end) {
		if (rightChild<end && res[leftChild]<res[rightChild]) {
			maxChild = rightChild;
		}
		if (res[maxChild]>res[father]) {
			swap(res[maxChild] , res[father]);
		}
		else {
			return;
		}
		father = maxChild;
		leftChild = father * 2 + 1;
		rightChild = leftChild + 1;
		maxChild = leftChild;
	}
}

void heapSort(vector<int>&res) {
	//创建最大堆
	for (int i = res.size() / 2 - 1; i >= 0;i--) {
		adjustHeap(res,i,res.size());
	}
	//一开始是0到n-1这个范围找最大值
	int end = res.size() - 1;
	//交换数据
	while (end>=1) {
		swap(res[0],res[end]);
		adjustHeap(res,0,end--);
	}
}

void Print(vector<int>&res) {
	for (int i = 0; i < res.size();i++) {
		cout << res[i] << " " ;
	}
	cout << endl;
}

int main() {
	vector<int>res = {4,2,5,3,1};
	heapSort(res);
	Print(res);
	return 0;
}

2、复杂度分析 

（1）时间复杂度

最优时间复杂度：O( nlogn )，即需要进行堆的建立和调整，建立大小为n的堆时间复杂度为O(n)，因为确保节点值大于或小于子节点的值（对最大堆和最小堆而言），建堆的过程每个节点复杂度为O(logn)，每次从堆顶取出最大（或最小）元素与堆中最后一个元素交换，然后对剩下n-1个元素进行堆调整，每次调整堆的时间复杂度为Q(logn)。

最坏时间复杂度：O( nlogn )。

平均时间复杂度：O( nlogn)。

（2）空间复杂度

最优空间复杂度：O(1)，即堆排序不需要额外申请空间，只在原数组上进行原地调整。

最坏空间复杂度：O(1)。

平均空间复杂度：O(1)。

六、快速排序

1、三色旗思想

介绍快速排序之前，先介绍三色旗思想（快排以三色旗思想为基础，原理相同）

三色旗描述：三色旗问题：数组内值和1进行对比，如果是2就和最后元素交换，如果是1 下标++但不交换，如果是0就和最前面交换。

（1）代码样例
#include <iostream>
#include <vector>

using namespace std;

//中有0，1，2（三色旗问题）三种值的数组，进行排序
void Quick(vector<int>&res,int L,int R) {
	int left = L - 1;
	int right = R + 1;
	int index = 0;
	int temp = 1;
	while (index < right) {
		if (res[index]==temp) {//说明是1
			index++;
		}
		else if (res[index] < temp) {//说明是0
			swap(res[index++],res[++left]);
		}
		else {//说明是2
			swap(res[index],res[--right]);
		}
	}
}

int main() {
	vector<int>res = {0,1,2,0,2,1,0,1};
	Quick(res,0,res.size()-1);
	for (auto it :res) {
		cout << "res: " << it << endl;
	}
	return 0;
}

2、快速排序

描述：快速排序的思想是将数组分成前后两组，分别进行排序（借助三色旗排序的思想），然后将两个数组进行合并即可

（1）代码样例
#include<iostream>
#include<vector>
using namespace std;

pair<int, int> Quick(vector<int>& vec, int L, int R) {
	int temp = vec[L];
	int i = L - 1;
	int j = R + 1;
	int index = L;
	while (index < j) {
		if (vec[index] > temp) {
			swap(vec[index], vec[--j]);
		}
		else if (vec[index] < temp) {
			swap(vec[index++], vec[++i]);
		}
		else
			index++;
	}
	return make_pair(i, j);
}

void Quick_sort(vector<int>& vec, int L, int R) {
	if (L >= R) return;
	pair<int, int> p = Quick(vec, L, R); // 三色旗思想
	Quick_sort(vec, L, p.first); // 对第一部分进行三色旗
	Quick_sort(vec, p.second, R); // 对第二部分进行三色旗
}

int main() {
	vector<int> vec = { 2, 4, 3, 1, 7, 6, 5, 9 };
	Quick_sort(vec, 0, vec.size() - 1);
	for (auto it : vec) {
		cout << it << " ";
	}
	return 0;
}

2、复杂度分析 

（1）时间复杂度

最优时间复杂度：O( nlogn)，即每次划分时间复杂度为O(n)，总共需要O(logn)次划分。

最坏时间复杂度：O( n^2)，即每次划分只能将数组分为一个元素和其余元素两个部分。

平均时间复杂度：O( nlogn)。

（2）空间复杂度

最优空间复杂度：O(logn)。

最坏空间复杂度：O(n)。

平均空间复杂度：O(logn)。

七、归并排序

描述：将两个有序数组合并成一个有序数组。

第一步：将数组进行分解，当分解成单个元素为一组的时候才是组内有序的。

第二步：将两两有序的数组进行合并，将两个有序数组合并成一个有序数组。重复第二步，直至排序完成。
合并的步骤:先申请两数组合并后那么大小的空间，然后将两个排好序的数组逐一进行比较，往申请空间里面放。

1、代码样例

#include<iostream>
#include<vector>
using namespace std;

void Merg(vector<int>&res,int L,int mid,int R) {
	vector<int>temp(R-L+1);//临时数组，用来存放这次排序完的数组，然后再放入res中
	int i = L;
	int j = mid+1;
	int index = 0;
	while(i<=mid && j<=R) {
		if (res[i]<res[j]) {
			temp[index++] = res[i++];
		}
		else{
			temp[index++] = res[j++];
		}
	}
	//此时两边存在剩余情况
	while (i <= mid) {
		temp[index++] = res[i++];
	}
	while (j <= R) {
		temp[index++] = res[j++];
	}
	index = L;
	for (int i = 0; i < (R - L + 1); i++) {
		res[index++] = temp[i];
	}
}

void Merg_Sort(vector<int>&res,int L,int R) {
	if (L >= R) {
		return;
	}
	int mid = (R - L) / 2 + L;
	Merg_Sort(res,L,mid);
	Merg_Sort(res,mid+1,R);
	Merg(res,L,mid,R);
}

int main() {
	vector<int> vec = { 2, 4, 3, 1, 7, 6, 5, 9 };
	Merg_Sort(vec,0,vec.size()-1);
	for (auto it : vec) {
		cout << it << " ";
	}
	return 0;
}

2、复杂度分析 

（1）时间复杂度

最优时间复杂度：O( nlogn)，即每次合并复杂度为O(n)，递归深度为O(logn)。

最坏时间复杂度：O( nlogn)。

平均时间复杂度：O( nlogn)。

（2）空间复杂度

最优空间复杂度：O(n)。

最坏空间复杂度：O(n)。

平均空间复杂度：O(n)。

标签：int,res,复杂度,通俗易懂,++,C++,数组,校招,排序
From： https://blog.csdn.net/qq_60018273/article/details/139863614

相关文章

  • C++矩阵库：Eigen 3.4.90 中文使用文档 （一）
    写在前面：我在学习Eigen库时，没找到好的中文文档，因此萌发了汉化Eigen官网文档的想法。其中一些翻译可能不是特别准确，欢迎批评指正。感兴趣的同学可以跳转到官网查看原文：Eigen:MainPagehttps://eigen.tuxfamily.org/dox/index.html       Eigen库，是一个开源的C......
  • C/C++ 缓冲区溢出问题总结
    缓冲区溢出（BufferOverflow）是一种常见的安全漏洞，它发生在当程序试图将更多的数据放入一个固定大小的内存区域（即缓冲区）时，超过了该区域所能容纳的数据量。这可能导致未定义的行为，包括数据损坏、程序崩溃，甚至更糟糕的是，攻击者可以利用这种漏洞执行恶意代码。一、缓冲区溢出概述缓冲......
  • C++ 面向对象高级开发 4、参数传递与返回值
    consructor构造函数：被放在private区ctors放在private区classA{public:staticA&getInsance();    setup(){...};private:A();    A(constA&rhs);};A&A::getInstance(){staticAa;    returna;}A::getInsance().s......
  • [Effective Modern C++] 条款18笔记
    条款18中的完整代码：点击查看代码#include<iostream>#include<memory>#include<string>//假设基础的Investment类和Stock类classInvestment{public:virtual~Investment()=default;virtualvoiddisplay()const=0;};//其它类类似，略classSto......
  • [Effective Modern C++] 条款19笔记 - 为什么deleter的类型是std::unique_ptr类型的一
    为什么deleter的类型是std::unique_ptr类型的一部分，而不是std::shared_ptr的一部分？std::unique_ptr<Widget,decltype(loggingDel)>upw(newWidget,loggingDel);std::shared_ptr<Widget>upw(newWidget,loggingDel);这个问题涉及到std::unique_ptr和std::shared_ptr......
  • C++list类的常见函数以及其模拟实现
    文章目录前言一、list内部成员有什么？二、构造函数以及析构函数1.默认构造2.传参构造3.迭代器构造4.深拷贝以及运算符=的重载1.深拷贝2.=的重载5.析构函数三、迭代器的模拟实现1.正向迭代器2.反向迭代器四、常见函数及其实现1.insert函数2.erase函数3.clear函数4.push_......
  • 我一直看不明白：“C++会被java/python等这些语言替代”
    在开始前刚好我有一些资料，是我根据网友给的问题精心整理了一份「C++的资料从专业入门到高级教程」，点个关注在评论区回复“888”之后私信回复“888”，全部无偿共享给大家！！！有些程序，是既可以用c++编写，也可以用java/python编写。如果这类程序以前主要是由c++编写，后来逐渐变成主要......
  • c++重载输出流（＜＜）
    一.重载输出流在C++中，可以重载输出流运算符（<<）来自定义对象的输出方式。重载输出流运算符允许我们以自定义的方式将对象输出到标准输出流或其他输出流中。以下是关于重载输出流运算符（<<）的几个知识点以及相应的示例：重载输出流运算符的语法：重载输出流运算符必须作为一个普......
  • 《C++ Primer》导学系列：第 7 章 - 类
    7.1定义抽象数据类型7.1.1类的基本概念在C++中，类是用户定义的类型，提供了一种将数据和操作这些数据的函数（成员函数）组合在一起的方法。类定义了对象的属性和行为，通过实例化类来创建对象。7.1.2定义类定义类时，需要指定类的名称，并在类体内声明数据成员和成员函数。类定义的......
  • C++的封装（适合新人，通俗易懂）
    作者：求一个demo版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处内容通俗易懂，没有废话，文章最后是面试常问内容1、访问权限介绍封装，那么需要先介绍一下访问权限：public公共权限、protected保护权限和private私有权限。（1）public公共权限简单来说：如果......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99