C++面试基础知识:排序算法 C++实现

在这里插入图片描述

上周实习面试,手撕代码快排没写出来,非常丢人,把面试官都给逗笑了。
基础不牢,地动山摇,基础的算法还是要牢记于心的。

插入排序

分为有序区和无序区,每次从无序区中选出一个,放到有序区域中。
实现:

void InsertionSort(vector<int> &nums, int left, int right){for(int i=left+1; i<=right; i++){int key = nums[i];int j = i-1;while(j >= left && nums[j] > key){nums[j+1] = nums[j];j--;}nums[j+1] = key;}
}

快速排序

选择一个基准元素,小于基准的放前面,大于基准的放后面,一边下来基准的位置就已经确定了,然后再对递归对两边区域进行快排。

#include <iostream>
#include <vector>
#include <chrono>void QuickSort(vector<int> &nums,int left, int right){if(left >= right) return;int pivot = nums[left];int i = left, j = right;while( i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSort(nums, left, i);QuickSort(nums, i+1, right);
}

快速排序的思想是分治法,每次将待排序区域划分为两部分,平均划分 O ( l o g n ) O(logn) O(logn)次,平均时间复杂度是 O ( n l o g n ) O(nlogn) O(nlogn),且前面的常数比较小,大部分情况相比于时间复杂度恒等于 O ( n l o g n ) O(nlogn) O(nlogn)的归并排序更快。
最坏情况时间复杂度是 O ( n 2 ) O(n^2) O(n2),当每次选取的pivot恰好是最大值或最小值时,分完后两侧一边是0个,一边是n-1个,这种情况快排退化成冒泡排序。

优化

为了避免出现最差情况,可以从待排序区域中取多个数,从这其中取中间数。

void QuickSortV1(vector<int> &nums, int left, int right){if(left >= right) return;if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;while(i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSortV1(nums, left, i);QuickSortV1(nums, i+1, right);
}
  • 对于待排序区间小于10的时候,选择使用插入排序,这样可以避免由于快速排序的递归成本,插入排序反而比快速排序快。
void InsertionSort(vector<int> &nums, int left, int right){for(int i=left+1; i<=right; i++){int key = nums[i];int j = i-1;while(j >= left && nums[j] > key){nums[j+1] = nums[j];j--;}nums[j+1] = key;}
}void QuickSortV2(vector<int> &nums, int left, int right){if(right - left < 10){InsertionSort(nums, left, right);return;}if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;while(i < j){while(i < j && nums[j] >= pivot) j--;while(i < j && nums[i] < pivot) i++;if(i < j){swap(nums[i], nums[j]);}}QuickSortV2(nums, left, i);QuickSortV2(nums, i+1, right);
}
  • 如果待排序的数组中存在较多的重复数字,还可以确定好pivot的位置后,遍历一遍将所有与pivot相同的数字放到一起,然后再进入递归,这样在具有较多重复时可以很好的提速。
void QuickSortV3(vector<int> &nums, int left, int right){if(right - left < 10){InsertionSort(nums, left, right);return;}if(nums[right] < nums[left]){swap(nums[left], nums[right]);}if(nums[(left+right)/2] < nums[right]){swap(nums[right], nums[(left+right)/2]);}if(nums[left] < nums[(left+right)/2]){swap(nums[left], nums[(left+right)/2]);}int pivot = nums[left];int i = left, j = right;int equal_right = 0;while(i < j){while(i < j && nums[i] < pivot) i++;while(i < j && nums[j] >= pivot){if(nums[j] == pivot){swap(nums[j], nums[right-equal_right]);equal_right++;}j--;}if(i < j){swap(nums[i], nums[j]);}}for(int k=0; k<equal_right; k++){swap(nums[i+k], nums[right-k]);}QuickSortV3(nums, left, i-1);QuickSortV3(nums, i+equal_right, right);
}

对比:

void randInit(vector<int> &nums){for(int i=0; i<nums.size(); i++){nums[i] = rand()%10000;}
}int main(){vector<int> nums(10000);randInit(nums);auto start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSort(nums, 0, nums.size()-1);}auto end = chrono::steady_clock::now();auto diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV1(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV2(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;start = chrono::steady_clock::now();for(int i=0;i<20;i++){QuickSortV3(nums, 0, nums.size()-1);}end = chrono::steady_clock::now();diff = end - start;cout << chrono::duration <double, milli> (diff).count()/20.0 << " ms" << endl;return 0;
}

在最差情况,每次都是选取到的最小值作为pivot,二者速度差了上百倍。

归并排序

也是分治思想,将待排序区域分为多个区域单独排序,再进行合并。不止可以分为两个区域,还可以分为多个区域,称为多路归并。
归并排序实现:

#include <iostream>
#include <vector>using namespace std;void merge_sort(vector<int> &num1, int left, int right){if(left >= right) return;int mid = left + (right - left) / 2;merge_sort(num1, left, mid);merge_sort(num1, mid + 1, right);int i = left, j = mid + 1, k = 0;vector<int> temp(right - left+1);while(i <= mid && j <= right){if(num1[i] <num1[j]){temp[k++] = num1[i++];}else{temp[k++] = num1[j++];}}while(i <= mid){temp[k++] = num1[i++];}while(j <= right){temp[k++] = num1[j++];}for(int i = 0; i < right - left+1; i++){num1[left + i] = temp[i];}
}int main(){vector<int> num1 = {3, 2, 1, 5, 4};vector<int> result;merge_sort(num1, 0, num1.size() - 1);for(auto i : num1){cout << i << " ";}cout << endl;return 0;
}

优化

  • 可以使用多线程进行优化,每个线程负责一个待排序区域
  • 通过改为非递归等方法,可以只需要一个temp就可以了,减小内存占用

堆排序

时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn),空间复杂度 O ( 1 ) O(1) O(1),不稳定算法。
维持一个大顶堆/小顶堆。一开始先进行建堆,建好堆后将堆的根和最后一个叶子节点进行交换,这时一个最大值的位置就已经固定了,接下来接着调整堆,调整好后再重复以上操作。

堆就是一棵完全二叉树,每一次都是满的,最后一层可以不是满的但是必须是从左往右紧密排列的:
在这里插入图片描述
堆分为大顶堆和小顶堆,大顶堆即父节点大于左右子节点,小顶堆即父节点小于左右子节点。
堆的存储方式最适合用数组存储,从左向右层序遍历的结果存在数组中。第i个数的父节点为 ⌊ i 2 ⌋ \left \lfloor \frac{i}{2} \right \rfloor 2i
不过需要注意从0开始存储的和从1开始存储的情况,计算父节点方式不一样,从0开始存储的情况,计算方式为 ⌊ i 2 ⌋ − 1 \left \lfloor \frac{i}{2} \right \rfloor -1 2i1
建堆的方式为从最后一个叶子节点开始,依次检查是不是大顶堆/小顶堆,如果是,接着向右排查,如果不是将该节点与子节点中较大的进行交换并判断交换后该节点是否为堆,如果不是,接着交换,直到该节点符合堆的要求为止。

实现:

#include <iostream>
#include <vector>using namespace std;void CreateHeap(vector<int> &nums, int i, int n){int left = 2*i+1;int right = 2*i+2;int max = i;if(left < n && nums[left] > nums[max]){max = left;}if(right < n && nums[right] > nums[max]){max = right;}if(max != i){swap(nums[i], nums[max]);CreateHeap(nums, max, n);}
}void HeapSort(vector<int> &nums){int n = nums.size();for(int i=n/2-1; i>=0; i--){CreateHeap(nums, i, n);}for(int i=n-1; i>=0; i--){swap(nums[0], nums[i]);CreateHeap(nums, 0, i);}
}int main()
{vector<int> nums = {3, 2, 1, 5, 4};HeapSort(nums);for(auto i : nums){cout << i << " ";}cout << endl;return 0;
}

扩展问题

  • 复杂度越小,算法越好吗?
    并不一定,第一点,算法复杂度衡量的是操作次数的数量级,如果要完全评价一个算法复杂度,还应该考虑每次操作的时间,所以同等复杂度等级的代码,速度可能不一样快。第二点,对于问题规模较小时,复杂度大的算法不一定比复杂度小的算法慢,例如在问题规模小于10时,插入排序是比快速排序要快的。

  • C++ 的STL库中的sort是怎么实现的?
    STL中的sort实现是内省排序,内省排序是快速排序和堆排序的结合,当递归深度大于 l o g n logn logn时,会切换为堆排序。

  • 什么是完全二叉树,什么是有序二叉树?
    完全二叉树就是类似于堆这种,简而言之就是从左向右层序遍历不存在缺口的二叉树。如果每一层都是满的,那就是满二叉树,所以完全二叉树也可以定义为顺序存储时,每个节点的位置都和满二叉树中节点的存储位置相同的树。
    有序二叉树指的是父子节点关系存在顺序管理,例如如果二叉树中父子节点满足:右子节点> 父节点> 左子节点,那这个树就是二叉查找树,可以用于快速查找数组中是否存在某个元素,查找时间复杂度为 O ( l o g n ) O(logn) O(logn),如果这个树是用链表存储的,那么插入复杂度也是 O ( l o g n ) O(logn) O(logn)

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LabVIEW开发相机与显微镜自动对焦功能

自动对焦是显微成像系统中的关键功能&#xff0c;通常由显微镜的电动调焦模块或特定的镜头系统提供&#xff0c;而工业相机则主要用于高分辨率图像的采集&#xff0c;不具备独立的自动对焦功能。以下是自动对焦的工作原理、实现方式及实际应用案例。 1. 自动对焦的工作原理 &a…

一文简单了解Android中的input流程

在 Android 中&#xff0c;输入事件&#xff08;例如触摸、按键&#xff09;从硬件传递到应用程序并最终由应用层消费。整个过程涉及多个系统层次&#xff0c;包括硬件层、Linux 内核、Native 层、Framework 层和应用层。我们将深入解析这一流程&#xff0c;并结合代码逐步了解…

详解基于C#开发Windows API的SendMessage方法的鼠标键盘消息发送

在C#中&#xff0c;SendMessage方法是一个强大的工具&#xff0c;它允许我们与Windows API交互&#xff0c;模拟键盘和鼠标事件。本文将详细介绍如何使用SendMessage方法来发送鼠标和键盘消息。 1. SendMessage方法概述 SendMessage是Windows API中的一个函数&#xff0c;它用…

爱普生SG-8200CJ可编程晶振在通信设备中的应用

在现代通信技术中&#xff0c;时钟源是确保系统运行稳定性的核心组件之一。随着数据传输速度的提高和系统复杂性的增加&#xff0c;通信设备对时钟的精度、稳定性和可靠性提出了更高的要求。爱普生SG-8200CJ可编程晶振&#xff0c;凭借其优异的性能特性&#xff0c;在通信设备领…

ssm100医学生在线学习交流平台+vue(论文+源码)_kaic

摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身的优势&#xff0c;医学生在线学习交流平台当然也不能排除在外&#xff0c;随着医学生在线学习交流平台的不断成熟&#xff0c;它彻底改变了过去传统的管理方式&a…

【数据结构】交换排序——冒泡排序 和 快速排序

交换排序——冒泡排序 和 快速排序 一、冒泡排序二、快速排序2.1 不同版本的快速排序<1>霍尔版本**1> 开闭区间****2> key 的取值****3> 单次循环的筛选条件****4> 为什么要先右边后左边****5> 递归停止条件** <2>挖坑版本<3>前后指针版本 2.…

C++模板特化实战:在使用开源库boost::geometry::index::rtree时,用特化来让其支持自己的数据类型

用自己定义的数据结构作为rtree的key。 // rTree的key struct OverlapKey {using BDPoint boost::geometry::model::point<double, 3, boost::geometry::cs::cartesian>; //双精度的点using MyRTree boost::geometry::index::rtree<OverlapKey, boost::geometry::in…

Redis - 集群(Cluster)

一、基本概念 上述的哨兵模式,提⾼了系统的可⽤性.但是真正⽤来存储数据的还是master和slave节点.所有的数 据都需要存储在单个master和slave节点中. 如果数据量很⼤,接近超出了master/slave所在机器的物理内存,就可能出现严重问题了. 如何获取更⼤的空间?加机器即可!所谓&q…

【专题】计算机网络之网络层

1. 网络层的几个重要概念 1.1 网络层提供的两种服务 (1) 让网络负责可靠交付 计算机网络模仿电信网络&#xff0c;使用面向连接的通信方式。 通信之前先建立虚电路 VC (Virtual Circuit) (即连接)&#xff0c;以保证双方通信所需的一切网络资源。 如果再使用可靠传输的网络…

Jmeter性能测试 -3数据驱动实战

软件测试资料领取&#xff1a;[内部资源] 想拿年薪40W的软件测试人员&#xff0c;这份资料必须领取~ 软件测试面试刷题工具&#xff1a;软件测试面试刷题【800道面试题答案免费刷】 什么是数据驱动&#xff1f; 从数据文件中读取测试数据&#xff0c;驱动测试过程的一种测试…

INQUIRE:一个包含五百万张自然世界图像,涵盖10,000个不同物种的专为专家级文本到图像检索任务设计的新型基准数据集。

2024-11-05 &#xff0c;由麻省理工学院、伦敦大学学院等联合创建了Inquire数据集&#xff0c;这是一个包含五百万自然世界图像的文本到图像检索基准测试&#xff0c;目的是挑战多模态视觉-语言模型在专家级查询上的表现。这个数据集的创建&#xff0c;不仅填补了现有数据集在专…

DevOps工程技术价值流:加速业务价值流的落地实践与深度赋能

DevOps的兴起&#xff0c;得益于敏捷软件开发的普及与IT基础设施代码化管理的革新。敏捷宣言虽已解决了研发流程中的诸多挑战&#xff0c;但代码开发仅是漫长价值链的一环&#xff0c;开发前后的诸多问题仍亟待解决。与此同时&#xff0c;虚拟化和云计算技术的飞跃&#xff0c;…

4.4 软件设计:UML顺序图

UML顺序图 1、 UML2、 UML顺序图2.1 顺序图组成对象生命线消息 2.2 顺序图和用例登录用例 2.3 顺序图建模顺序图建模参考策略建立顺序图的步骤建立顺序图的示例 3、面对对象的设计原则3.1 特点3.2 层次3.3 注意点类设计需要强内聚&#xff0c;弱耦合可重用性框架 1、 UML 统一…

除了 Mock.js,前端还有更方便的 Mock 数据工具吗?

在前端开发中&#xff0c;模拟数据&#xff08;Mock Data&#xff09;是不可或缺的一部分&#xff0c;它能够帮助开发者在后端接口未完成前进行界面和逻辑的测试。而 Mock.js 是一个广泛使用的库&#xff0c;它通过简洁的语法和强大的功能&#xff0c;让前端开发者可以轻松地创…

继承和多态(上)

目录 一.继承 1.何为继承 2.继承的语法 3.子类访问父类 (1)子类访问父类的成员变量 (2)子类访问的父类方法 二.super关键字 1.super用于调用父类的构造方法 2.super用于调用父类的实例方法 3.super用于访问父类的实例变量 三.子父类构造方法 和代码块的执行优先顺序…

【练习案例】30个 CSS Javascript 加载器动画效果

本文分享一些 Loader CSS、Javascript 示例&#xff0c;这些示例均来源于Codepen网站上&#xff0c;里面有案例的源码与显示效果&#xff0c;您可以用于练习&#xff0c;也可以将您认为有趣的动画&#xff0c;添加到您的项目中&#xff0c;以帮助您创建更加有趣的等待页面加载动…

45.第二阶段x86游戏实战2-hook监控实时抓取游戏lua

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 本次游戏没法给 内容参考于&#xff1a;微尘网络安全 本人写的内容纯属胡编乱造&#xff0c;全都是合成造假&#xff0c;仅仅只是为了娱乐&#xff0c;请不要…

限流算法(令牌通漏桶计数器)

限流算法&#xff08;令牌桶&漏桶&计数器 &#xff09; 什么是限流&#xff1f; 限流是为保护自身系统和下游系统不被高并发流量冲垮&#xff0c;导致系统雪崩等问题 限流在很多场景中用来限制并发请求量&#xff0c;比如说秒杀抢购、双11高并发流量等 在保证系统可…

❤React-React 组件基础(类组件)

❤React-React 组件基础 1、组件化开发介绍 组件化开发思想&#xff1a;分而治之 React的组件按照不同的方式可以分成类组件&#xff1a; 划分方式一&#xff08;按照组件的定义方式&#xff09; 函数组件(Functional Component )和类组件(Class Component)&#xff1b; …

2024/11/13 英语每日一段

The new policy has drawn many critics. Data and privacy experts said the Metropolitan Transit Authority’s new initiative doesn’t address the underlying problem that causes fare evasion, which is related to poverty and access. Instead, the program tries “…