面试考点:冒泡排序、选择排序、插入排序、归并排序、快速排序

云惠网小编 2021年11月23日11:19:03
评论
3154字阅读10分30秒
摘要

深处开发岗,其实排序也是绕不开的环节,其中冒泡排序,选择排序,插入排序,归并排序,快速排序,堆排序也是我在秋招以来频繁问到的技术点排序算法有两块比较重要的知识点内存消耗 :算法的内存消耗可以通过空间复杂度来衡量,排序算法也不例外。不过,针对排序算法的空间复杂度,有一个概念是原地排序。原地排序算法是指空间复杂度是O(1)的排序算法。其中冒泡排序,插入排序、选择排序都属于原地排序算法 稳定性:针对排序算法,我们还有一个衡量指标是稳定性。这个概念是说,如果待排序的序列中存在值相等的元素,经过排序之后.

广告也精彩

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

选择排序

深处开发岗,其实排序也是绕不开的环节,其中冒泡排序,选择排序,插入排序,归并排序,快速排序,堆排序也是我在秋招以来频繁问到的技术点

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

 

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

 

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

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 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 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),是原地排序但不是稳定排序

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

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

冒泡排序

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

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

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

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

插入排序

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

快速排序

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

 

归并排序

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

本文转自 https://blog.csdn.net/Xiao_qsn/article/details/121438558

腾讯云618
云惠网小编
cgb2110-day06 java

cgb2110-day06

文章目录一,模拟用户登录过程--1,需求--2,测试--3,程序优化二,SQL攻击/注入--1,概述--2,解决方案--3,修改代码--4,两种传输器的区别三,练习新的传输器--1...
JAVA 初级程序员常见问题分析 java

JAVA 初级程序员常见问题分析

1、怎么样可以尽快拿到offer?针对心仪的企业、岗位进行调查。可以上招聘网站看看其岗位要求,以及企业的面试题。然后针对性的学习其要求的技术。这样有针对性的准备,投其所好,就可更快...
关于数据库学习的一些知识盲区 java

关于数据库学习的一些知识盲区

一.SQL拼接方法的安全风险 1. SQL注入问题(SQL Inject),使用字符串拼接构造SQL就会引起SQL注入。 2. SQL注入是存在安全风险的 3. 例如:在图书管理系...
腾讯云618

发表评论