【C++】数据结构与算法:常用排序算法

😏★,°:.☆( ̄▽ ̄)/$:.°★ 😏
这篇文章主要介绍常用排序算法。
学其所用,用其所学。——梁启超
欢迎来到我的博客,一起学习,共同进步。
喜欢的朋友可以关注一下,下次更新不迷路🥞

文章目录

    • :smirk:1. 算法介绍
    • :blush:2. C++实现

😏1. 算法介绍

排序算法是计算机科学中常见的一类算法,用于将一组数据按照特定的顺序进行排列。下面介绍几种常见的排序算法:

  1. 冒泡排序(Bubble Sort):
  • 从待排序序列的第一个元素开始,两两比较相邻元素的大小,如果顺序不对则交换位置。
  • 每一轮结束后,最大(或最小)的元素会移动到末尾。
  • 时间复杂度:平均情况和最坏情况下为 O(n^2),最好情况下为 O(n)。
  • 空间复杂度:O(1)。
  1. 插入排序(Insertion Sort):
  • 将未排序序列的第一个元素插入已排序序列的正确位置。
  • 从第二个元素开始,依次与前面的元素比较并插入到正确位置。
  • 时间复杂度:平均情况和最坏情况下为 O(n^2),最好情况下为 O(n)。
  • 空间复杂度:O(1)。
  1. 选择排序(Selection Sort):
  • 每一轮从待排序序列中选择最小(或最大)的元素,与当前位置交换。
  • 每一轮结束后,当前位置之前的元素都是有序的。
  • 时间复杂度:平均情况和最坏情况下为 O(n^2)。
  • 空间复杂度:O(1)。
  1. 快速排序(Quick Sort):
  • 选择一个基准元素,将序列分为比基准小的元素和比基准大的元素。
  • 递归地对划分后的子序列进行快速排序。
  • 时间复杂度:平均情况下为 O(nlogn),最坏情况下为 O(n^2)。
  • 空间复杂度:平均情况下为 O(logn),最坏情况下为 O(n)。
  1. 归并排序(Merge Sort):
  • 将序列递归地拆分成两个子序列,对子序列进行排序,然后合并两个有序子序列。
  • 使用分治法思想,将排序问题分解为较小的子问题。
  • 时间复杂度:平均情况下为 O(nlogn)。
  • 空间复杂度:O(n)。

😊2. C++实现

#include <iostream>
#include <cstdlib>
#include <ctime>// 冒泡排序 bubbleSort 两两比较
void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {std::swap(arr[j], arr[j+1]);}}}
}// 选择排序 selectionSort 选最小值
void selectionSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {int minIndex = i;for (int j = i+1; j < n; j++) {if (arr[j] < arr[minIndex]) {minIndex = j;}}std::swap(arr[i], arr[minIndex]);}
}// 插入排序 insertionSort 依次成序
void insertionSort(int arr[], int n) {for (int i = 1; i < n; i++) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j];j--;}arr[j + 1] = key;}
}// 归并排序 mergeSort
void merge(int arr[], int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;int* L = new int[n1];int* R = new int[n2];for (int i = 0; i < n1; i++) {L[i] = arr[left + i];}for (int j = 0; j < n2; j++) {R[j] = arr[mid + 1 + j];}int i = 0;int j = 0;int k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) {arr[k] = L[i];i++;k++;}while (j < n2) {arr[k] = R[j];j++;k++;}delete[] L;delete[] R;
}void mergeSort(int arr[], int left, int right) {if (left < right) {int mid = left + (right - left) / 2;mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}// 快速排序 quickSort
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] <= pivot) {i++;std::swap(arr[i], arr[j]);}}std::swap(arr[i+1], arr[high]);return i+1;
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi - 1);quickSort(arr, pi + 1, high);}
}// 打印数组
void printArray(int arr[], int size) {for (int i = 0; i < size; i++) {std::cout << arr[i] << " ";}std::cout << std::endl;
}int main() {const int SIZE = 10;// 生成随机整数数组int arr[SIZE];srand(time(0));for (int i = 0; i < SIZE; i++) {arr[i] = rand() % 100; // 生成 0 到 99 的随机数}std::cout << "Original array: ";printArray(arr, SIZE);// 使用冒泡排序进行排序bubbleSort(arr, SIZE);std::cout << "Array after bubble sort: ";printArray(arr, SIZE);// 使用选择排序进行排序selectionSort(arr, SIZE);std::cout << "Array after selection sort: ";printArray(arr, SIZE);// 使用插入排序进行排序insertionSort(arr, SIZE);std::cout << "Array after insertion sort: ";printArray(arr, SIZE);// 使用归并排序进行排序mergeSort(arr, 0, SIZE-1);std::cout << "Array after merge sort: ";printArray(arr, SIZE);// 使用快速排序进行排序quickSort(arr, 0, SIZE-1);std::cout << "Array after quick sort: ";printArray(arr, SIZE);return 0;
}

编译运行:

g++ -o main main.cpp && ./main

在这里插入图片描述

以上。

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

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

相关文章

单片机、嵌入式的大神都平时浏览什么网站?

我平时也喜欢收藏些有关嵌入式的学习网站&#xff0c;压箱底的记录翻出来总结下 1、综合网站 哔哩哔哩 (゜-゜)つロ 干杯~-bilibili//B站是一个有很多好资料的网站 https://github.com/nhivp/Awesome-Embedded //github开源项目网站&#xff0c;这个是我找到嵌入式综合相关的…

PS的一些智能对象是怎么用的?用于包装设计该怎么使用?

大家都对一些效果图不太理解&#xff0c;我现在就献丑给大家讲一下&#xff0c;教程都是网友盛传的&#xff0c;我自己学习并且有所体会。 一般做的非常好的PS效果图都是外国人自己做的&#xff0c;所以大多数效果图都是英文&#xff0c;细心的网友会发现&#xff0c;中文的是一…

chatGPT能力培训,客户最关注的99个方向

前言&#xff1a; chatGPT的主要应用&#xff0c;包括文本生成、图像生成和图文关联三大核心方向&#xff1a; 用户的在实际的工作和学习过程中&#xff0c;最关心的内容&#xff0c;可以按照上述类别进行划分&#xff0c;我们总结了&#xff0c;相关的插头GPT能力培训的相关主…

基于OFDM通信系统的低复杂度的资源分配算法matlab性能仿真

目录 1.算法运行效果图预览 2.算法运行软件版本 3.部分核心程序 4.算法理论概述 5.算法完整程序工程 1.算法运行效果图预览 2.算法运行软件版本 matlab2022a 3.部分核心程序 .......................................................................%子载波分配[~,po…

MySQL:表的约束和基本查询

表的约束 表的约束——为了让插入的数据符合预期。 表的约束很多&#xff0c;这里主要介绍如下几个&#xff1a; null/not null,default, comment, zerofill&#xff0c;primary key&#xff0c;auto_increment&#xff0c;unique key 。 空属性 两个值&#xff1a;null&am…

C 语言的 ctype.h 头文件

C 语言的 ctype.h 头文件包含了很多字符函数的函数原型, 可以专门用来处理一个字符, 这些函数都以一个字符作为实参. ctype.h 中的字符测试函数如表所示: 这些测试函数返回 0 或 1, 即 false 或 true. ctype.h 中的字符映射函数如表所示: 字符测试函数不会修改原始实参, 只会…

list交并补差集合

list交并补差集合 工具类依赖 <dependency><groupId>org.apache.commons</groupId><artifactId>commons-lang3</artifactId><version>3.8.1</version> </dependency><dependency><groupId>commons-collections&…

内生安全构建数据存储

一、数据安全成为防护核心&#xff0c;存储安全防护不容有失 1、数据作为企业的核心资产亟需重点保护&#xff0c;数据安全已成网络空间防护核心 2、国家高度重视关键信息基础设施的数据安全&#xff0c;存储安全已成为审核重点 二、存储安全是数据安全的关键一环&#xff0c;应…

解决github打不开的方法

解决github打不开的方法 本文参考文章&#xff1a;解决可ping通但无法访问github网站的问题 一、确定域名github.com的ip地址 进入网址 IP/服务器github.com的信息 - 站长工具 (chinaz.com)&#xff0c;查看 ip 地址。 20.205.243.166 github.com二、确定域名github.global.…

【论文研读】MARLlib 的架构分析

【论文研读】MARLlib: A Scalable Multi-agent Reinforcement Learning Library 和尚念经 多智能体强化学习框架研究。 多智能体强化学习库。 多智能体强化学习算法实现。 多智能体强化学习环境的统一化&#xff0c;标准化。 多智能体强化学习算法解析。 多智能体强化学习 算法…

5W2H分析法模版

&#xff08;1&#xff09;WHAT——是什么&#xff0c;目的是什么&#xff0c;做什么工作。 条件是什么&#xff0c;哪一部分工作要做&#xff0c;目的是什么&#xff0c;重点是什么&#xff0c;与什么有关系&#xff0c;功能是什么&#xff0c;规范是什么&#xff0c;工作对象…

【IDEA+Spark Streaming 3.4.1+Dstream监控套接字流统计WordCount保存至MySQL8】

【IDEASpark Streaming 3.4.1Dstream监控套接字流统计WordCount保存至MySQL8】 把DStream写入到MySQL数据库中 Spark 3.4.1MySQL 8.0.30sbt 1.9.2 文章目录 【IDEASpark Streaming 3.4.1Dstream监控套接字流统计WordCount保存至MySQL8】前言一、背景说明二、使用步骤1.引入库2…

时序数据库 TDengine 与 WhaleStudio 完成相互兼容性测试认证

近年来&#xff0c;开源及其价值获得社会各界的广泛认可&#xff0c;无论是国家政策导向还是企业数字化转型&#xff0c;都在加速拥抱开源。对于如操作系统、数据库等基础软件来说&#xff0c;开源更是成为驱动技术创新的有力途径。 在此背景下&#xff0c;近日&#xff0c;涛…

Feign

一、为什么使用Feign 二、Feign和RestTemplate的区别 三、自定义配置 四、Feign日志 1.配置文件方式 2.java代码方式

TS 踩坑之路(四)之 Vue3

一、在使用定义默认值withDefaults和defineProps 组合时&#xff0c;默认值设置报错 代码案例 报错信息 不能将类型“{ isBackBtn: false; }”分配给类型“(props: PropsType) > RouteMsgType”。 对象字面量只能指定已知属性&#xff0c;并且“isBackBtn”不在类型“(pro…

【机器学习】在 MLOps构建项目 ( MLOps2)

My MLOps tutorials: Tutorial 1: A Beginner-Friendly Introduction to MLOps教程 2&#xff1a;使用 MLOps 构建机器学习项目 一、说明 如果你希望将机器学习项目提升到一个新的水平&#xff0c;MLOps 是该过程的重要组成部分。在本文中&#xff0c;我们将以经典手写数字分类…

【车道线】TwinLiteNet 复现过程全纪录

码字不易&#xff0c;喜欢的请点赞收藏&#xff01;&#xff01;&#xff01;&#xff01;&#xff01; 论文全文翻译&#xff1a;【freespace】TwinLiteNet: An Efficient and Lightweight Model for Driveable Area and Lane Segmentation_莫克_Cheney的博客-CSDN博客 目录…

Vue2:组件高级(下)

Vue2&#xff1a;组件高级&#xff08;下&#xff09; Date: May 25, 2023 Sum: 自定义指令、插槽、商品列表、动态组件 目标&#xff1a; 自定义指令 基础概念&#xff1a; 概念&#xff1a; 内置指令&#xff1a;vue 官方提供了 v-for、v-model、v-if 等常用的内置指令。…

机器学习基础08-回归算法矩阵分析(基于波士顿房价(Boston House Price)数据集)

回归算法通常涉及到使用矩阵来表示数据和模型参数。线性回归是最常见的回归算法之一&#xff0c;它可以用矩阵形式来表示。 考虑一个简单的线性回归模型&#xff1a; y m x b y mx b ymxb&#xff0c;其中 y y y 是因变量&#xff0c; x x x 是自变量&#xff0c; m m m 是…

nginx服务

目录 基本介绍 nginx的主要功能 nginx的主要应用场景 nginx常用命令 nginx另外一种安装方式 nginx常用的信号符&#xff1a; nginx配置文件详解 全局配置 event模块 http模块 server模块 location模块&#xff1a; 模块的划分 基本介绍 nginx&#xff1a;高性能、…