排序: 插入\希尔\选择\归并\冒泡\快速\堆排序实现
1.排序的概念及应用
1.1概念
排序:所谓排序,就是一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
1.2运用
购物筛选排序:
1.3常见排序算法 
2.实现常见的排序算法
int a[ = {5,3,9,6,2,4,7,1,8};
2.1插入排序
基本思想:直接插入排序是一种简单的插入排序法,其基本思想是:把待排序的记录按其相关键码值逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列。我们可以理解成玩扑克牌
2.1.1直接插入排序
当插入第i个元素时,前面的arr[0],arr[1],arr[2].....,arr[i-1]已经排好序,此时用arr[i]的排序码与arr[i-1],arr[i-2]....的排序码顺序相比较,找到插入位置即将arr[i]插入,原来位置上的与元素挨个向后移动。
代码实现:
void InsertSort(int* arr, int n)
{for (int i = 0; i < n-1; i++){int end = i;int tmp = arr[end + 1];while (end>=0){if (arr[end] > tmp) {arr[end + 1] = arr[end];end--;}else{break;}}arr[end+1] = tmp;}
}
直接插入排序的特性总结:
1.元素集合越接近有序,直接插入排序算法的效率越高
2.时间复杂度:O(N^2)
3.空间复杂度:O(1)
2.1.2希尔排序
希尔排序的特性总结:
1.希尔排序是对直接插入排序的优化
2.当gap>1时都是预排序,目的时让数组更接近有序。当gap==1时,数组已经接近有序的了,这样就会很快。这样总体而言,可以达到优化的效果。
代码实现:
/希尔排序
void shellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3+1;//3 1 0 要保证最后一次为1for (int i = 0; i < n - gap; i++){int end = i;//n-gap-1int tmp = arr[end + gap];//n-1while (end>=0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}
2.1.2.1希尔排序的时间复杂度计算
希尔排序的时间复杂度估算:
外层循环:外层循环的时间复杂度可以直接给出为:O(log2 n) 或者 O(log3 n) ,即 O(log n)
内层循环:
假设一共有n个数据,合计gap组,则每组为n/gap个数据;在每组中,插入移动的次数最坏的情况下为1+2+3+4+.....+(n/gap-1),一共是gap组,因此:
总计最坏情况下移动总数为:gap*[1+2+3+...+n/gap-1]
gap取值有(以除3为例):n/3 n/9 n/27.....2 1
2.2选择排序
选择排序的基本思想:每一次从待排序的数据元素中选出最小或者最大的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。
2.2.1直接选择排序
1.在元素集合arr[i]--arr[n-1]中选择最大和最小的数据元素
2.若它不是这个组元素中的最后一个元素或者第一个元素,则将它与这组元素中的最后一个和第一个元素进行交换
3.在剩余的arr[i]--arr[n-1] arr[i+1]--arr[n-2]集合中,重复上面的步骤直到集合只剩一个元素
//选择排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin<end){int mini = begin;int maxi = begin;for (int i = begin; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}}
直接选择排序非常好理解,但是效率不高,实际中很少用
时间复杂度:O(N^2)
空间复杂度:O(1)
2.2堆排序
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 堆排序
void AdjustDwon(int* arr, int parent, int n)
{int child = 2 * parent + 1;//左孩子//大堆找最大//小堆找最小while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int* arr, int n)
{//1.先建堆//升序建大堆//降序建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(arr, i, n);}//交换根结点和最后一个有效数据的位置(没交换一次少一个数据)然后向下调整int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//向下调整AdjustDwon(arr, 0, end);end--;}
}
2.3交换排序
交换排序基本思想:
2.3.1冒泡排序
前⾯在算法题中我们已经接触过冒泡排序的思路了,冒泡排序是⼀种最基础的交换排序之所以叫做冒泡排序,因为每⼀个元素都可以像⼩⽓泡⼀样,根据⾃⾝⼤⼩⼀点⼀点向数组的⼀侧移动。
//冒泡排序
//时间复杂度:0(N^2)
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}
冒泡排序的特性总结:
时间复杂度为:O(N^2)
空间复杂度为:O(1)
2.3.2快速排序
快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它的基本思想是分而治之,通过一趟排序将待排记录分割成独立的两部分,其中一部分的所有记录均比另一部分的所有记录要小,然后再按此方法对这两部分分别进行快速排序,整个排序过程可以递归进行,以至整个数据变成有序序列。
快速排序实现的主框架:
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值midint key = _QuickSort(arr, left, right);//左子序列:[left,mid-1]QuickSort(arr, left, key - 1);//右子序列:[mid+1,right]QuickSort(arr, key + 1, right);
}
将区间中的元素划分的 _QuickSort方法主要有一下几种实现方式:
2.3.2.1hoare版本
算法思路:
1.创建左右指针,确定基准值
2.从右向左找比基准值小的数据,从左向右找比基准值大的数据,左右指针数据交换,进入下次循环。当left>right时,即right走到left的左侧,而left扫描过的数据均不大于key,因此right此时指向的数据一定不大于key。
left和right指向的数据与key相等时也要交换,相等的值参与交换确实有一些损耗。实际还有各种复杂的场景,假设数组中的数据大量重复时,无法进行有效的数据分割。
代码实现:
//hoare法
int _QuickSort(int* arr, int left, int right)
{int key = left;left++;while (left<=right)//使效率更高{//right从右到左找比基准值小的while (left<=right&&arr[right]>arr[key]){right--;}//left从左到右找比基准值大的while (left<=right&&arr[left]<arr[key]){left++;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}//跳出循环,交换right和基准值Swap(&arr[key], &arr[right]);//返回基准值return right;
}
2.3.2.2挖坑法
//挖坑法
int _QuickSort1(int* arr, int left, int right)
{int mid = arr[left];int hole = left;int key = arr[hole];while (left<right){while (left < right && arr[right] > key){right--;}//填坑arr[hole] = arr[right];hole = right;while (left<right&&arr[left]<key){left++;}//填坑arr[hole] = arr[left];hole = left;}arr[hole] = key;//返回基准值return hole;
}
2.3.2.3lomuto前后指针
创建前后指针,从左往右找比基准值小的进行交换,使得小的都排在基准值的左边。
//lomuto法
int _QuickSort2(int* arr, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while (cur<=right){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[key], &arr[prev]);//返回基准值return prev;
}
快速排序的特性:
时间复杂度:O(n*logn)
空间复杂度:O(logn)
2.3.2.4非递归版本
非递归版本的快速排序需要借助数据结构:栈
//非递归
//栈结构
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInite(&st);//入栈STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)) {//取栈顶--取两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//找基准值int prev = begin;int cur = begin + 1;int key = begin;while (cur<=end){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[key]);key = prev;//根据基准值划分左右区间//left:[begin,key-1]//right:[key+1,end]if (key+1<end){STPush(&st, end);STPush(&st, key + 1);}if (begin<key-1){STPush(&st, key - 1);STPush(&st, begin);}}STDestroy(&st);
}
2.4归并排序
归并排序算法思想:归并排序(MERGE-SORT是建⽴在归并操作上的⼀种有效的排序算法,算法是采⽤分治法(Divide and Conquer的⼀个⾮常典型的应⽤。将已有序的⼦序列合并,得到完全有序的序列;即先使每个 ⼦序列有序,再使⼦序列段间有序若将两个有序表合并成⼀个有序表称为⼆路归并。归并排序核⼼步骤:
void _mergeSort(int* arr, int left, int right,int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;//[left,mid] [mid+1,right]_mergeSort(arr, left, mid, tmp);_mergeSort(arr, mid + 1, right, tmp);//合并//[left,mid] [mid+1,right]int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;while (begin1<=end1&&begin2<=end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//要么begin1越界,要么begin2越界while (begin1<=end1){tmp[index++] = arr[begin1++];}while (begin2<=end2){tmp[index++] = arr[begin2++];}//把tmp中的数据拷贝会arr中for (int i = left; i <=right; i++){arr[i] = tmp[i];}
}
//归并排序
void mergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_mergeSort(arr, 0, n - 1, tmp);free(tmp);
}
归并排序特性总结:
时间复杂度:O(n*logn)
空间复杂度: O(n)
2.5计数排序
//计数排序
void CountSort(int* arr, int n)
{int max = arr[0];int min = arr[0];//找到最大值和最小值求范围for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}int range = max - min + 1;//开辟数组大小int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}//初始化置为0memset(count, 0, range * sizeof(int));//统计数组中每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//取count中的数据往arr中放int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}
2.6测试代码:排序性能对比
//测试排序性能
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);int* a7 = (int*)malloc(sizeof(int) * N);int* a8 = (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];a7[i] = a1[i];a8[i] = a1[i];}int begin7 = clock();BubbleSort(a7, N);int end7 = clock();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);//QuickSortNonR(a5, 0, N - 1);int end5 = clock();int begin6 = clock();mergeSort(a6, N);int end6 = clock();int begin8 = clock();CountSort(a8, N);int end8 = 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);printf("BubbleSort:%d\n", end7 - begin7);printf("CountSort:%d\n", end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}
相关文章:

排序: 插入\希尔\选择\归并\冒泡\快速\堆排序实现
1.排序的概念及应用 1.1概念 排序:所谓排序,就是一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 1.2运用 购物筛选排序: 1.3常见排序算法 2.实现常见的排序算法 int a[ {5,3,9,6,2,4,7,1,8}; 2…...

OpenCV图像处理——按最小外接矩形剪切图像处理ROI后映射回原图像
引言 在图像处理过程中,提取感兴趣区域(ROI)并在其上进行处理后,往往需要将处理后的结果映射回原图像。这一步通常涉及以下几个步骤: 找到最小外接矩形:使用 cv::boundingRect 或 cv::minAreaRect 提取感兴…...

Linux中以单容器部署Nginx+ASP.NET Core
强烈推荐在生产环境中使用反向代理服务器转发请求到Kestrel Http服务器,本文将会实践将Nginx --->ASP.NET Core 部署架构容器化的过程。 Nginx->ASP.NET Coe部署架构容器化 在Docker中部署Nginx--->ASP.NETCore 有两种选择, 第一种是在单容器…...

【秋招笔试】8.11大疆秋招(第三套)-三语言题解
🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 编程一对一辅导 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收…...
标题:打造编程学习的知识宝库:高效笔记记录与整理
标题:打造编程学习的知识宝库:高效笔记记录与整理 在编程学习的征途中,有效的笔记记录和整理技巧对于掌握和回顾知识点至关重要。本文将从笔记工具选择、笔记结构设计、以及实践与复习策略三个方面,探讨如何高效地记录并整理编程…...
【Rust光年纪】Rust 官方提供的关键工具概览:代码检查、格式化和依赖管理
提升 Rust 项目质量和安全性:掌握官方工具的核心功能和使用方法 前言 Rust 作为一种系统编程语言,拥有强大的性能和内存安全特性。然而,随着项目规模增长,代码检查、格式化和依赖管理等工作变得更加重要。因此,Rust …...

【Python学习-UI界面】PyQt5 小部件8-QSlider 数值滑动
样式如下: QSlider 类对象为用户提供一个沟槽,可以在其上移动一个手柄。 它是一个经典的小部件,用于控制有界值。 手柄在沟槽上的位置相当于控件的下限和上限之间的整数。 常用方法如下: 序号方法描述1setMinimum设置滑块的最小值2setMax…...

MapReduce入门教程
这可不是目录 入门定义与说明数据分析Map和Reduce阶段的任务<Kn,Vn>分析MapReduce的数据类型其他说明(持续更新) 开发案例(持续更新)自定义的wordcountcsv文件操作序列化操作 入门 定义与说明 数据分析 以下未数据分析示意图 Map和Reduce阶段的任务 Map阶段的任务&a…...

JDBC1 Mysql驱动,连接数据库
JDBC 一、JDBC Java Database Connectivity:Java访问数据库的解决方案 JDBC定义了一套标准接口,即访问数据库的通用API, 不同的数据库厂商根据各自数据库的特点去实现这些接口。 JDBC希望用相同的方式访问不同的数据库,让具体的…...

LeetCode 205 同构字符串
题目 给定两个字符串 s 和 t ,判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的。 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序。不同字符不能映射到同一个字符上,…...

ARM高性能计算(HPC)处理器Neoverse介绍
思考: Neoverse系列中的N、V、E有什么区别? 这三个字母的缩写又是什么? ARM Neoverse架构是ARM专为服务器、数据中心、高性能计算(HPC)和网络基础设施设计的一系列处理器架构。Neoverse架构分为N系列、V系列和E系列,这些系列面向不同的应用场景,各自有不同的设计目标和…...

【每日力扣中医养生】力扣1298. 你能从盒子里获得的最大糖果数
1298. 你能从盒子里获得的最大糖果数 文章目录 【每日力扣&中医养生】力扣1298. 你能从盒子里获得的最大糖果数题目描述示例解析示例 1示例 2 算法思路算法步骤代码实现复杂度分析总结 【每日力扣&中医养生】力扣1298. 你能从盒子里获得的最大糖果数 《黄帝内经》的阴…...

大数据-81 Spark 安装配置环境 集群环境配置 超详细 三台云服务器
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...
C#创建一个自定义控件类
如果你希望在 TextBox 内部嵌入一个按钮,并且这个按钮用于打开文件选择对话框,可以创建一个自定义控件来实现这一功能。下面是一个示例,展示如何在 Windows 窗体应用程序中创建一个自定义控件,其中 Button 嵌入到 TextBox 内部。 …...

springboot牙科就诊管理系统--论文源码调试讲解
2 相关技术 2.1 MySQL数据库 本设计用到的数据库就是MySQL数据库[3],之所以用到这个数据库的原因很多。首先,从满足功能需求上面来讲,MySQL是符合的;其次,从学习程度来讲,MySQL相比其他数据库不管是从安装…...

CUDA+tensorflow+python+vscode在GPU下环境安装及问题汇总与解答
2024.8.14 因为要做深度学习,需要安装tensorflowgpu的环境,每次都搞不好整的很生气,本次将安装过程中参考的一些大佬的博客和安装过程中遇到的问题及解决方案总结一下,希望以后不要在这件事情上浪费时间。安装环境其实也没有想象中…...

24/8/14算法笔记 复习_逻辑回归sigmoid
import numpy as np import matplotlib.pyplot as pltdef sigmoid(x):return 1/(1np.exp(-x))x np.linspace(-5,5,100) y sigmoid(x)plt.plot(x,y,colorgreen) #损失函数 from sklearn import datasets from sklearn.linear_model import LogisticRegression from mpl_toolki…...
MySQL忘记/无root密码,强制修改root密码
MySQL忘记/无root密码,强制修改root密码_mysql无root密码登录后设置密码-CSDN博客 sudo vi /etc/mysql/my.cnf 添加如下内容: [mysqld] skip-grant-tablessudo service mysql restart mysql -u root -p use mysql; update mysql.user set authentica…...
探索 MongoDB 的 $currentDate:解决 TTL 时间不同步问题的利器
在我们日常的开发工作中,时间管理是一个非常重要的环节。尤其是在处理数据库中的数据时,时间戳的准确性和一致性至关重要。今天,我们要聊聊 MongoDB 中的一个神奇操作符——$currentDate,它是如何帮助我们解决 TTL(Tim…...
defineModel
前言 随着 Vue3.4 版本的发布,defineModel 也正式转正了。它可以简化父子组件之间的双向绑定,是目前官方推荐的双向绑定实现方式。 defineModel 使用 在开发的过程中,如果有需要通过子组件进行状态更新的话,v-model是一个绕不开…...

Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

剑指offer20_链表中环的入口节点
链表中环的入口节点 给定一个链表,若其中包含环,则输出环的入口节点。 若其中不包含环,则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

解读《网络安全法》最新修订,把握网络安全新趋势
《网络安全法》自2017年施行以来,在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂,网络攻击、数据泄露等事件频发,现行法律已难以完全适应新的风险挑战。 2025年3月28日,国家网信办会同相关部门起草了《网络安全…...

华为OD机试-最短木板长度-二分法(A卷,100分)
此题是一个最大化最小值的典型例题, 因为搜索范围是有界的,上界最大木板长度补充的全部木料长度,下界最小木板长度; 即left0,right10^6; 我们可以设置一个候选值x(mid),将木板的长度全部都补充到x,如果成功…...
git: early EOF
macOS报错: Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...

UE5 音效系统
一.音效管理 音乐一般都是WAV,创建一个背景音乐类SoudClass,一个音效类SoundClass。所有的音乐都分为这两个类。再创建一个总音乐类,将上述两个作为它的子类。 接着我们创建一个音乐混合类SoundMix,将上述三个类翻入其中,通过它管理每个音乐…...