当前位置: 首页 > news >正文

数据结构排序算法---八大排序复杂度及代码实现

文章目录

  • 一、冒泡排序
    • 代码实现
  • 二、直接插入排序
    • 代码实现
  • 三、希尔排序
    • 代码实现
  • 四、选择排序
    • 代码实现
  • 五、堆排序
    • 代码实现
  • 六、快速排序
    • 代码实现
  • 七、归并排序
    • 代码实现
  • 八、计数排序
    • 代码实现


稳定性:相同的数据排序后,相对位置是否发生改变

一、冒泡排序

时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定

代码实现

void Swap(int* a, int* b)
{int tmp;tmp = *a;*a = *b;*b = tmp;
}
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){int exchange = 0;for (size_t i = 1; i < n-j; i++)if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);exchange = 1;}if (exchange == 0){break;}}
}

二、直接插入排序

时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定

代码实现

void InsertSort(int* a, int n)
{for (int i = 0; i < n; i++){int end = i;int tmp = a[end + 1];while (end>=0){if (tmp < a[end])a[end + 1] = a[end];elsebreak;--end;}a[end + 1] = tmp;} 
}

三、希尔排序

时间复杂度:O(N^1.3)
空间复杂度:O(1)
稳定性:不稳定

代码实现

void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}elsebreak;}a[end + gap] = tmp;}}
}

四、选择排序

时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:不稳定

代码实现

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin < end){int max = begin, min = begin;for (int i = begin+1; i <= end; i++){if (a[i] > a[max])max = i;if (a[i] < a[min])min = i;}Swap(&a[begin], &a[min]);if (max == begin)max = min;Swap(&a[end], &a[max]);--end;++begin;}
}

五、堆排序

时间复杂度:O(N*logN)
空间复杂度:O(1)
稳定性:不稳定

代码实现

void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}void HeapSort(int* a, int n)
{for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}

六、快速排序

时间复杂度:O(N*logN)
空间复杂度:O(logN)
稳定性:不稳定

代码实现

//三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right])return midi;else if (a[right] < a[left])return left;elsereturn right;}else{if (a[left] < a[right])return left;else if (a[right] < a[midi])return midi;elsereturn right;}
}
//hoare
int PartSort1(int* a, int left,int right)
{int keyP = left;//GetMidi(a,left,right);while (left < right){while (a[right] >= a[keyP] && left < right)--right;while (a[left] <= a[keyP] && left < right)++left;Swap(&a[left], &a[right]);}Swap(&a[keyP], &a[left]);return left;
}
//挖坑法
int PartSort2(int* a, int left, int right)
{int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyP = a[left];//int keyP = left;int hole = left;while (left < right){while (a[right] >= keyP && left < right)--right;a[hole] = a[right];hole = right;while (a[left] <= keyP && left < right)++left;a[hole] = a[left];hole = left;}a[hole] = keyP;return hole;
}
//前后指针
int PartSort3(int* a, int left, int right)
{int prev = left;int cur = prev + 1;int keyP = left;while (cur <= right){if (a[cur] < a[keyP] && ++prev != cur){Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyP]);return prev;
}void QuickSort(int* a, int begin, int end)
{if (begin >= end)return;int key = PartSort1(a, begin, end);QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);
}void QuickSort1(int* a, int begin, int end)
{if (begin >= end)return;//小区间优化,小区间不在递归分割排序,降低递归次数if ((end - begin + 1) > 10){int key = PartSort1(a, begin, end);QuickSort1(a, begin, key - 1);QuickSort1(a, key + 1, end);}else{InsertSort(a + begin, end - begin + 1);}
}void QuickSortNonR(int* a, int begin, int end)//非递归
{Stack st;StackInit(&st);StackPush(&st, end);StackPush(&st, begin);while (!StackEmpty(&st)){int left = StackTop(&st);StackPop(&st);int right = StackTop(&st);StackPop(&st);int key = PartSort3(a, left, right);if (key + 1 < right){StackPush(&st, right);StackPush(&st, key + 1);}if (begin < key - 1){StackPush(&st, key - 1);StackPush(&st, begin);}}StackDestory(&st);
}

其中包含了,三数取中(基准值),快排的三种实现方法(hoare,挖坑法,前后指针)及非递归方法


七、归并排序

时间复杂度:O(N*logN)
空间复杂度:O(N)
稳定性:稳定

代码实现

void PartMergeSort(int* a, int* tmp, int begin, int end)
{if (end <= begin)return;int mid = (begin + end) / 2;PartMergeSort(a, tmp, begin, mid);PartMergeSort(a, tmp, mid + 1, end);int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int count = begin;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[count++] = a[begin1++];elsetmp[count++] = a[begin2++];}while (begin1 <= end1){tmp[count++] = a[begin1++];}while (begin2 <= end2){tmp[count++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}void MergeSort(int* a, int n)
{int* tmp = malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}PartMergeSort(a, tmp, 0, n - 1);free(tmp);
}void MergeSortNonR(int* a, int n)
{int* tmp = malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail");exit(-1);}int gap = 1;while (gap < n){for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;int count = i;if (begin2 >= n)break;if (end2 >= n)end2 = n - 1;while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2])tmp[count++] = a[begin1++];elsetmp[count++] = a[begin2++];}while (begin1 <= end1){tmp[count++] = a[begin1++];}while (begin2 <= end2){tmp[count++] = a[begin2++];}memcpy(a + i, tmp + i, (end2-i+1) * sizeof(int));}	gap *= 2;}
}

其中包含了递归及非递归实现方法


八、计数排序

时间复杂度:O(N+range)
空间复杂度:O(range)

代码实现

void CountSort(int* a, int n)
{int min = a[0], max = a[0];for (size_t i = 0; i < n; i++){if (a[i] < min)min = a[i];if (a[i] > max)max = a[i];}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);printf("\nrange:%d\n", range);if (count == NULL){perror("malloc fail");return;}memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i = 0; i < n; i++){count[a[i] - min]++;}// 排序int j = 0;for (int i = 0; i < range; i++){while (count[i]--){a[j++] = i + min;}}
}

相关文章:

数据结构排序算法---八大排序复杂度及代码实现

文章目录 一、冒泡排序代码实现 二、直接插入排序代码实现 三、希尔排序代码实现 四、选择排序代码实现 五、堆排序代码实现 六、快速排序代码实现 七、归并排序代码实现 八、计数排序代码实现 稳定性&#xff1a;相同的数据排序后&#xff0c;相对位置是否发生改变 一、冒泡排…...

GMS之Launcher中去除默认Search或替换为Chrome Search

将Launcher中搜索框去除 将FeatureFlags.java文件中的QSB_ON_FIRST_SCREEN变量修改为false \system\vendor\mediatek\proprietary\packages\apps\Launcher3\src\com\android\launcher3\config\FeatureFlags.java/*** Defines a set of flags used to control various launche…...

@DateTimeFormat 和 @JsonFormat 的详细研究

关于这两个时间转化注解&#xff0c;先说结论 一、介绍 1、DateTimeFormat DateTimeFormat 并不会根据得到其属性 pattern 把前端传入的数据转换成自己想要的格式&#xff0c;而是将前端的String类型数据封装到Date类型&#xff1b;其次它的 pattern 属性是用来规范前端传入…...

nodejs基于Vue.js健身体育器材用品商城购物网97794

管理员端的功能主要是开放给系统的管理人员使用&#xff0c;能够对用户的信息进行管理&#xff0c;包括对用户、健身器材、器材类型、系统和订单进行查看&#xff0c;修改和删除、新增等&#xff0c;对系统整体运行情况进行了解。用户的功能主要是对个人账号和密码进行更新信息…...

C#WPF框架Microsoft.Toolkit.MvvM应用实例

本文实例演示C#WPF框架Microsoft.Toolkit.MvvM应用 目录 一、MVVM概述 二、MVVMLight概述 三、使用Microsoft.Toolkit.Mvvm框架 一、MVVM概述 MVVM概述MVVM是Model-View-ViewModel的简写,主要目的是为了解耦视图(View)和模型(Model)。...

蓝桥杯每日一题2023.9.27

4408. 李白打酒加强版 - AcWing题库 题目描述 题目分析 对于这题我们发现有三个变量&#xff0c;店&#xff0c;花&#xff0c;酒的数量&#xff0c;对于这种范围我们使用DP来进行分析。 dp[i][j][k]我们表示有i个店&#xff0c;j朵花&#xff0c;k单位酒的集合&#xff0c…...

Redis与分布式-主从复制

接上文 常用中间件-OAuth2 1.主从复制 启动两个redis服务器。 修改第一个服务器地址 修改第二个redis 然后分别启动 redis-server.exe redis.windows.conf) 查看当前服务器的主从状态&#xff0c;打开客户端&#xff1a;输入info replication命令来查看当前的主从状态&am…...

QT pyside2 线程嵌套子线程 实现开始运行和停止运行

文章目录 前言为什么要使用多线程 一、单个线程实现按钮方法的执行二、线程嵌套多个子线程实现按钮方法的执行三、QT GUI常用代码3.1 多线程取出队列任务循环执行&#xff0c;无停止3.2 将某个方法放在线程中执行3.3 QT pyside2 tableWidget 清除日志3.4 退出整个GUI程序(杀死进…...

江西广电会展集团总经理李悦一行莅临拓世科技集团调研参观,科技璀璨AIGC掀新潮

在江西这片充满活力的土地上&#xff0c;数字经济如潮水般涌动&#xff0c;会展文化与科技的完美结合&#xff0c;正如新时代的璀璨繁星照亮夜空&#xff0c;更预示着一场AIGC创新的壮丽篇章即将展开。作为拓世科技集团的老朋友&#xff0c;江西广电多位领导多次莅临拓世科技集…...

【RabbitMQ实战】06 RabbitMQ配置

一、概述 一般情况下&#xff0c;可以使用默认的内建配置来有效地运行RabbitMQ&#xff0c;并且大多数情况下也并不需要修改任何 RabbitMQ的配置。当然&#xff0c;为了更加有效地操控 RabbitMQ&#xff0c;也可以利用调节系统范围内的参数来达到定制化的需求。 RabbitMQ提供…...

CTF 全讲解:[SWPUCTF 2021 新生赛]jicao

文章目录 参考环境题目index.phphighlight_file()include()多次调用&#xff0c;多次执行单次调用&#xff0c;单次执行 $_POST超全局变量HackBarHackBar 插件的获取 $_POST打开 HackBar 插件通过 HackBar 插件发起 POST 请求 GET 请求查询字符串超全局变量 $_GET JSONJSON 数据…...

FL Studio21.1电脑试用体验版音乐制作软件

我一直以来对音乐艺术都很感兴趣。最近我接触到了一款名为 FL Studio 的电脑版音乐制作软件&#xff0c;深感其强大功能和广泛适用性。通过使用这款软件&#xff0c;我不仅深入了解了音乐制作的过程与技巧&#xff0c;也加深了对音乐创作的理解。 FL Studio 最初是一款针对 MI…...

【数据结构】单链表的基本操作(节点建立、插入删除)

1. 单链表的基本操作 1.1. 链表的定义1.2. 链表的创建&#xff08;初始化&#xff09; 1.2.1. 不带头结点的链表1.2.2. 带头结点的链表 1.3. 链表的插入和删除 1.3.1. 按位序插入 1.3.1.1. 带头结点1.3.1.2. 不带头结点 1.3.2. 指定节点的后插操作1.3.3. 指定元素的前插操作1.3…...

DEM格式转换:转换NSDTF-DEM国标数据格式为通用格式,使用ArcGIS工具转换NSDTF-DEM国标.dem文件为通用.tif格式。

DEM格式转换&#xff1a;转换NSDTF-DEM国标数据格式为通用格式&#xff0c;使用ArcGIS工具转换NSDTF-DEM国标.dem文件为通用.tif格式。 *.dem是一种比较常见的DEM数据格式&#xff0c;其有两种文件组织方式&#xff0c;即NSDTF-DEM和USGS-DEM。 &#xff08;1&#xff09;NSDT…...

施耐德电气:勾勒未来工业愿景,赋能中国市场

9月19日&#xff0c;第23届中国国际工业博览会&#xff08;简称“工博会”&#xff09;在上海隆重召开。作为全球能源管理和自动化领域的数字化转型专家&#xff0c;施耐德电气在工博会现场全方位展现了自身对未来工业的全新视野与深刻见解&#xff0c;不仅展示了其贯通企业设计…...

安防监控产品经营商城小程序的作用是什么

安防监控产品覆盖面较大&#xff0c;监控器、门禁、对讲机、烟感等都有很高用途&#xff0c;家庭、办公单位各场景往往用量不少&#xff0c;对商家来说&#xff0c;市场高需求背景下也带来了众多生意&#xff0c;但线下门店的局限性&#xff0c;导致商家想要进一步增长不容易。…...

php中判断指定字符串是否包含指定字符的封装函数

在 PHP 中&#xff0c;你可以使用内置的字符串函数 strpos() 来判断一个字符串是否包含指定的字符或子字符串。以下是一个简单的封装函数&#xff0c;它使用 strpos() 来判断指定字符串是否包含指定字符&#xff0c;并返回一个布尔值。 function stringContains($string, $cha…...

GICI-LIB源码阅读(三)因子图优化模型

原始 Markdown文档、Visio流程图、XMind思维导图见&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 文章目录 三、因子图优化&#xff08;FGO&#xff09;1、因子图模型2、因子图优化状态估计模型3、因子图优化求解4、Ceres 非线性最小二乘库5、GICI-LIB 中…...

5、Docker安装mysql主从复制与redis集群

安装mysql主从复制 主从搭建步骤 1.1 新建主服务器容器实例3307 docker run -p 3307:3306 --name mysql-master #3307映射到3306&#xff0c;容器名为mysql-master -v /app/mysql/mydata/mysql-master/log:/var/log/mysql #容器数据卷 -v /app/mysql/mydata/mysql-master/dat…...

【AI视野·今日NLP 自然语言处理论文速览 第四十三期】Thu, 28 Sep 2023

AI视野今日CS.NLP 自然语言处理论文速览 Thu, 28 Sep 2023 Totally 38 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computation and Language Papers Cross-Modal Multi-Tasking for Speech-to-Text Translation via Hard Parameter Sharing Authors Brian Yan,…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

C++:std::is_convertible

C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

C++课设:简易日历程序(支持传统节假日 + 二十四节气 + 个人纪念日管理)

名人说:路漫漫其修远兮,吾将上下而求索。—— 屈原《离骚》 创作者:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 专栏介绍:《编程项目实战》 目录 一、为什么要开发一个日历程序?1. 深入理解时间算法2. 练习面向对象设计3. 学习数据结构应用二、核心算法深度解析…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...