★ 数据结构 ★ 排序

Ciallo~(∠・ω< )⌒☆ ~ 今天,我将和大家一起学习数据结构中的各种排序~

​❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️

澄岚主页:椎名澄嵐-CSDN博客

数据结构专栏:https://blog.csdn.net/2302_80328146/category_12764674.html?spm=1001.2014.3001.5482

​❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️


目录

零  测试排序的性能

壹  冒泡排序

贰  插入排序

叁  堆排序

肆  希尔排序

伍  选择排序

陆  快速排序

 6.1 hoare版本

6.2 挖坑法

6.3 前后指针法

6.4 非递归快排

 柒  归并排序

7.1 递归版本 

7.2 非递归版本

捌  计数排序

 玖  总结

~ 完 ~


零  测试排序的性能

// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];		a5[i] = a1[i];a6[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);
}


壹  冒泡排序

  • 冒泡排序是一种非常容易理解的排序
  • 时间复杂度:O(N ^ 2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

// O(N^2) 最坏
// O(N)   最好
void BubbleSort(int* a, int n)
{for (int j = 0; j < n; j++){// 单趟int flag = 0;for (int i = 0; i < n - j; i++){if (a[i - 1] > a[i]){Swap(&a[i - 1], &a[i]);flag = 1;}}if (flag == 0)break;}
}


贰  插入排序

插入排序就是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。

  • 元素集合越接近有序,直接插入排序算法的时间效率越高
  • 时间复杂度:O(N ^ 2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

// 时间复杂度:O(N^2)  什么情况最坏:逆序
// 最好:顺序有序,O(N)
// 插入排序
void Insertsort(int* a, int n)
{// 最后一次 a[n-1] 进到 [0, n - 2] 区间中// end为 n-2for (int i = 0; i < n - 1; i++){// 单趟int end = i;int tmp = a[end + 1];// [0, end]有序 把end+1位置的值插入while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}// end最后一次会移到-1,不进循环,不能在else中交换a[end + 1] = tmp;}
}


叁  堆排序

堆排序即利用堆的思想来进行排序,总共分为两个步骤:

  1. 建堆 升序:建大堆 降序:建小堆
  2. 利用堆删除思想来进行排序

void HeapSort(int* a, int n)
{// 向下调整建堆 O(N)for (int i = (n-2)/2; i >= 0; i--){AdjustDown(a, n, i);}// O(N * logN)int end = n - 1;while (end > 0){Swap(&a[0], &a[end]);AdjustDown(a, end, 0);--end;}
}void AdjustDown(int* a, int n, int parent)
{// 先假设左孩子小int child = parent * 2 + 1;while (child < n)  // 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;}}
}


肆  希尔排序

希尔排序的基本思想:先选定一个整数,把待排序文件中所有记录分成gap组,所有距离为gap的记录分在同一组内,并对每一组内的记录进行排序。

希尔排序的特点:

  • 希尔排序是对直接插入排序的优化
  • 当gap > 1时都是预排序,目的是让数组更接近于有序。
  • 当gap == 1时插入排序,数组已经接近有序的了,这样就会很快。
  • 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定,大约为O(N ^ 1.3)
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1; // 保证最后一次gap是1// 有gap组for (int j = 0; j < gap; j++){// 每组排序// 若 i >= n - gap 则最后一次tmp会越界for (size_t i = 0; i < n - gap; i += gap){// 单趟int end = i;int tmp = a[end + gap];while (end >= 0){if (tmp < a[end]){a[end + gap] = a[end];end -= gap;}else{break;}}a[end + gap] = tmp;}}}
}
// 写法2:多组并行
void ShellSort(int* a, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1; // 保证最后一次gap是1for (size_t 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;}else{break;}}a[end + gap] = tmp;}}
}


伍  选择排序

每一次从待排序的数据元素中选出最小和最大的个元素,存放在序列的起始位置和末位置,直到全部待排序的数据元素排完 。

直接选择排序的特性总结:

  • 好理解,但效率不好。很少使用。
  • 时间复杂度:O(N ^ 2)
  • 空间复杂度:O(1)
  • 稳定性:不稳定
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin, maxi = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}Swap(&a[mini], &a[begin]);if (begin == maxi){maxi = mini;}Swap(&a[maxi], &a[end]);begin++;end--;}
}


陆  快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

快速排序的特性总结:

  • 1. 快速排序整体的综合性能和使用场景都是比较好的。
  • 2. 时间复杂度:O(N*logN)。

 6.1 hoare版本

void QuickSort(int* a, int left, int right)
{if (left >= right)return;// 小区间优化if ((right - left + 1) < 10){InsertSort(a + left, right - left + 1);}int keyi = QuickSortHoare(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}int QuickSortHoare(int* a, int left, int right)
{// 三数取中int midi = GetMid(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left, end = right;while (begin < end){while (begin < end && a[end] >= a[keyi]){--end;}while (begin < end && a[begin] <= a[keyi]){++begin;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[begin]);return begin;
}
int GetMid(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[left] < a[midi]){if (a[midi] < a[right]){return midi;}// midi最大else if (a[left] < a[right]){return right;}else{return left;}}else // a[left] > a[midi]{if (a[midi] > a[right]){return midi;}// midi最小else if (a[left] < a[right]){return left;}else{return right;}}
}

6.2 挖坑法

6.3 前后指针法

int QuickSortPointer(int* a, int left, int right)
{// 三数取中int midi = GetMid(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur)Swap(&a[prev], &a[cur]);++cur;}Swap(&a[prev], &a[keyi]);return prev;
}

6.4 非递归快排

int QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = QuickSortPointer(a, begin, end);// [begin, keyi - 1] keyi [keyi + 1, end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}


 柒  归并排序

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

归并排序的特性总结:

  • 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  • 时间复杂度:O(N*logN)
  • 空间复杂度:O(N)
  • 稳定性:稳定

7.1 递归版本 

void MergeSort(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}_MergeSort(a, tmp, 0, n - 1);free(tmp);tmp = NULL;
}void _MergeSort(int* a, int* tmp, int begin, int end)
{if (begin >= end)return;int mid = (begin + end) / 2;// [begin, mid] [mid + 1, end]有序就可以归并了_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid + 1, end);// 归并int begin1 = begin, end1 = mid;int begin2 = mid + 1, end2 = end;int i = begin;while (begin1 <= end1 && begin2 <= end2){// 谁小谁++if (a[begin1] < a[begin2]){tmp[i++] = a[begin1++];}else{tmp[i++] = a[begin2++];}}// 另一个没走完的while (begin1 <= end1){tmp[i++] = a[begin1++];}while (begin2 <= end2){tmp[i++] = a[begin2++];}memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}

7.2 非递归版本

void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");return;}// 每组归并个数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;printf("[%d, %d][%d, %d]  ", begin1, end1, begin2, end2);// 第二组都越界,不用归并if (begin2 >= n)break;// begin2没越界,end2越界,修正end2if (end2 >= n)end2 = n - 1;int j = i;while (begin1 <= end1 && begin2 <= end2){// 谁小谁++if (a[begin1] < a[begin2]){tmp[j++] = a[begin1++];}else{tmp[j++] = a[begin2++];}}// 另一个没走完的while (begin1 <= end1){tmp[j++] = a[begin1++];}while (begin2 <= end2){tmp[j++] = a[begin2++];}memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));}gap *= 2;printf("\n");}free(tmp);tmp = NULL;
}


捌  计数排序

计数排序又称为鸽巢原理,是对哈希直接定址法的变形应用

  • 统计相同元素出现次数
  • 根据统计的结果将序列回收到原来的序列中

计数排序的特性:

  • 计数排序在数据范围集中时,效率很高,但是适用范围及场景有限。
  • 时间复杂度:O(N + range)
  • 空间复杂度:O(range)
// 时间复杂度:O(N + range)
// 空间复杂度:O(range)
// 整数,范围集中
void CountSort(int* a, int n)
{// 选出max和minint min = a[0], max = a[0];for (int i = 1; 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*)calloc(range, sizeof(int));if (count == NULL){perror("calloc fail!");return;}// 统计次数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;}}
}


 玖  总结

排序种类时间复杂度空间复杂度稳定性
直接插入排序O(N ^ 2)O(1)稳定
希尔排序O(N ^ 1.3)O(1)不稳定
选择排序O(N ^ 2)O(1)不稳定
堆排序O(N * logN)O(1)不稳定
冒泡排序O(N ^ 2)O(1)稳定
快速排序O(N * logN)O(logN)不稳定
归并排序O(N * logN)O(N)稳定

 


~ 完 ~

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

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

c语言基础三:运算符和表达式

一、常用的运算符分类 运算符类型 作用 算术运算符 用于处理四则运算 赋值运算符 用于将表达式的值赋给变量 比较运算符 用于表达式的比较&#xff0c;并返回一个真值或假值 逻辑运算符 用于根据表达式的值返回真值或假值 位运算符 用于处理数据的位运算 s…

如何通过金蝶云星空高效集成销售出库单

金蝶云星空数据集成案例分享&#xff1a;销售出库单-&#xff08;分销&京东&唯品&虚拟除外&#xff09;手表汇总 在企业信息化系统中&#xff0c;数据的高效流转和准确对接是业务运作的关键。本文将聚焦于一个具体的系统对接集成案例&#xff0c;即如何将金蝶云星…

【SKFramework框架核心模块】3-4、事件模块

推荐阅读 CSDN主页GitHub开源地址Unity3D插件分享QQ群&#xff1a;398291828小红书小破站 大家好&#xff0c;我是佛系工程师☆恬静的小魔龙☆&#xff0c;不定时更新Unity开发技巧&#xff0c;觉得有用记得一键三连哦。 一、前言 【Unity3D框架】SKFramework框架完全教程《全…

鸿蒙分享:添加模块,修改app名称图标

新建公共模块common 在entry的oh-package.json5添加dependencies&#xff0c;引入common模块 "dependencies": {"common": "file:../common" } 修改app名称&#xff1a; common--src--resources--string.json 新增&#xff1a; {"name&q…

逆向攻防世界CTF系列48-Signin.md

逆向攻防世界CTF系列48-Signin.md 直接定位 输入&#xff0c;然后跟踪96A 一个整数一个余数你会发现这是把输入字符变成两个分开的十六进制存储起来&#xff0c;比如输入字符 ‘1’ &#xff0c;它的整数是49&#xff0c;49除16的整数是3&#xff0c;余数是1&#xff0c;在byt…

最新版Chrome谷歌加载ActiveX控件之金格iWebOffice2015控件

allWebPlugin简介 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有浏览器。它将现有ActiveX控件直接嵌入浏览器&#xff0c;实现插件加载、界面显示、接口调用、事件回调等。支持Chrome、Firefo…

Lakehouse 架构下的元数据“大一统”管理深度解析

在湖仓一体&#xff08;Lakehouse&#xff09;出现之前&#xff0c;数据仓库和数据湖堪称数据领域的两大“顶流”。打个比方&#xff0c;要是把数据仓库比作一座大型图书馆&#xff0c;那其中的数据就如同馆内藏书&#xff0c;需要按照规范放好&#xff0c;借阅者只需依照类别索…

【AI系统】MobileVit 系列

MobileVit 系列 自 Vision Transformer 出现之后&#xff0c;人们发现 Transformer 也可以应用在计算机视觉领域&#xff0c;并且效果还是非常不错的。但是基于 Transformer 的网络模型通常具有数十亿或数百亿个参数&#xff0c;这使得它们的模型文件非常大&#xff0c;不仅占…

投稿指南——论文检索报告如何开具

【SciencePub学术】论文发表被SCI数据库收录之后&#xff0c;作为学术成果上报时&#xff0c;一般需要提供论文检索报告&#xff0c;SCI论文检索报告怎么开&#xff1f;在哪开&#xff1f;要注意什么&#xff1f;这些问题&#xff0c;本期小编给大家解答一下。 Q 开具检索报告…

Jenkins 推送报错 - SSH 密钥失效

目录 问题描述报错原因解决方案 问题描述 jenkins 构建完毕后&#xff0c;将构建好的 jar 包推送至远端服务器时&#xff0c;Deploy 阶段报如下错误&#xff1a; sshpass -p **** scp -o StrictHostKeyCheckingno -P 22 -r /data/jenkins/workspace/TAI/TAI/AllCam-tai-cloud/…

《ODIN: A Single Model for 2D and 3D Segmentation》CVPR2024

斯坦福和微软&#xff1a; 代码链接&#xff1a;ODIN: A Single Model For 2D and 3D Perception 论文链接&#xff1a;2401.02416 摘要 这篇论文介绍了ODIN&#xff08;Omni-Dimensional INstance segmentation&#xff09;&#xff0c;一个能够同时处理2D RGB图像和3D点云…

三、代码管理-Git

文章目录 前言一、Git1. Git 与 SVN 区别2. Git 入门3. 客户端工具4. 主流Git仓库 二、GitLab1. 介绍2. 适合的场景 二、GitHub1. 介绍2. 适合的场景 三、Gitee1. 介绍2. 适合的场景 四、GitCode1. 介绍2. 适合的场景 五、总结 前言 代码托管‌ Git作为目前最为流行的版本控制…

npm, yarn, pnpm之间的区别

前言 在现代化的开发中&#xff0c;一个人可能同时开发多个项目&#xff0c;安装的项目越来越多&#xff0c;所随之安装的依赖包也越来越臃肿&#xff0c;而且有时候所安装的速度也很慢&#xff0c;甚至会安装失败。 因此我们就需要去了解一下&#xff0c;我们的包管理器&#…

vscode上传本地文件到服务器

vscode上传本地文件到服务器 首先下载插件SFTP&#xff0c;我们通过ftp进行文件传输 VScode打开要传输的文件 使用快捷键 ctrlshiftP 打开搜索窗口&#xff0c;搜索SFTP 点击之后vscode文件夹下会生成对应json文件 我们编辑json信息根据远程的服务器情况填写&#xff0c;比如…

Next.js 实战 (二):搭建 Layouts 基础排版布局

前言 等了许久&#xff0c;Next.js 终于迎来了 v15.x 版本&#xff0c;刚好 Github 上面的旧项目重构完&#xff0c;终于可以放心大胆地去研究 Next.js了。 搭建最新项目可以参考官方文档&#xff1a;Installation 最新的 Next.js 版本&#xff0c;使用的是 React19.x 内测版…

Java的Stirng、StringBuilder、StringJoiner

黑马程序员Java个人笔记 目录 字符串比较 比较 boolean equals boolean equalsIgnoreCase 键盘录入和定义的字符串的比较 StringBuilder 打印 ​编辑 添加元素 反转 获取长度 toString 练习 对称字符串 拼接字符串 StringJoiner 概述 ​编辑 构造方法 只有…

elasticsearch(三)

文章目录 1.数据聚合1.1.聚合的种类1.2.DSL实现聚合1.2.1.Bucket聚合语法1.2.2.聚合结果排序1.2.3.限定聚合范围1.2.4.Metric聚合语法 1.3.RestAPI实现聚合1.3.1.API语法1.3.2.业务需求1.3.3.业务实现 2.自动补全2.1.拼音分词器2.2.自定义分词器2.3.自动补全查询2.4.实现酒店搜…

Python_Flask03

这篇文章主要介绍的是数据库的增删改查操作&#xff0c;无多余好说的。 from flask import Flask from flask_sqlalchemy import SQLAlchemy from sqlalchemy import text from flask_migrate import Migrateapp Flask(__name__)# 本地基础信息的主机名 HOSTNAME "127.0…

Hive分区值的插入

对于Hive分区表&#xff0c;在我们插入数据的时候需要指定对应的分区值&#xff0c;而这里就会涉及很多种情况。比如静态分区插入、动态分区插入、提供的分区值和分区字段类型不一致&#xff0c;或者提供的分区值是NULL的情况&#xff0c;下面我们依次来展现下不同情况下的表现…

安达发|工业镜头APS高级排产的关键约束

工业镜头生产具有其特定的复杂性&#xff0c;如技术要求高、生产周期长、工序多等特点。在应用APS系统进行高级排产时&#xff0c;需要考虑以下关键约束&#xff1a; 1. 技术与质量约束 - 精度要求&#xff1a;工业镜头对精度的要求极高&#xff0c;这直接影响到排产计划中机加…