排序算法（基础）大全

一、排序算法的作用：

排序算法的主要作用是将一组数据按照特定的顺序进行排列，使得数据更加有序和有组织。

1. 查找效率：通过将数据进行排序，可以提高查找算法的效率。在有序的数据中，可以使用更加高效的查找算法，如二分查找、插值查找等，减少了查找的时间复杂度。

2. 统计分析：在排序过程中，可以对数据进行各种统计分析，如计算各种统计量、查找中位数、众数等。有序的数据更加便于进行统计分析和数据挖掘。

3. 数据压缩和编码：排序算法可以将数据重新排列，进而提供更好的数据压缩和编码方式，减少存储空间和传输带宽。

4. 数据归并和合并：在某些应用中，需要将多个有序的数据集合进行归并或合并，排序算法提供了这样的功能。例如，在合并两个有序的数组时，可以使用归并排序算法。

5. 数据的可视化和展示：有序的数据更容易进行可视化展示，可以更加直观地表达数据的分布和关系。

6. 数据库和文件系统中的索引：数据库和文件系统中的索引结构通常需要对数据进行排序，以提高查询和检索的效率。

总之，排序算法能够对数据进行有序排列，提高数据的组织性和可读性，提高查找和统计等操作的效率，是计算机科学和实际应用中的基础算法之一。

二、基础排序算法： 

（1）选择排序：

故名思义，选择排序算法就是有选择地进行排序。其算法思想是：
1、将数组分成【已排序区】和【待排序区】
2、每一轮从【待排序区】中选择一个最小的元素放到【已排序区】
3、直到【待排序区】没有元素为止

其算法的时间复杂度无论好坏都为O(n^2)

稳定性：不稳定

其过程如图：

关键代码实现： 
#define swap(a,b){\ //交换a,b__typeof(a) __c=(a);\  //将a赋值给__c,同时，__c的类型与a的类型一样(a)=(b);\ //将b赋值给a(b)=__c;\ //将__c赋值给b
}
void selection_sort(int *arr,int l,int n){ //选择排序for(int i=l;i<n-1;i++){ //从下标0开始int ind=i; //假设下标为ind的数组元素最小for(int j=i+1;j<n;j++){if(arr[ind]>arr[j])ind=j; //如果有比下标ind更小的，则更新下标ind}swap(arr[i],arr[ind]); //将两个元素交换}return;
}
（2）插入排序：

故名思义，插入排序就是不断进行插入调整的排序。其算法思想是：
1、将数组分成【已排序区】和【待排序区】
2、将【待排序区】后面第一个元素，向前插入到【已排序区】并进行调整
3、直到【待排序区】没有元素为止
其算法的时间复杂度最好的情况下为O(n),最坏的情况下或平均情况下为O(n^2)

稳定性：稳定

其过程如图：

关键代码实现：
#define swap(a,b){\ //交换a,b__typeof(a) __c=(a);\(a)=(b);\(b)=__c;\
}
void insert_sort(int *arr,int b,int n){ //插入排序，b=0for(int i=b+1;i<n;i++){ //待排序区从1开始int j=i; //记录已排序区的最大下标while(j>b&&arr[j]<arr[j-1]){ //对新插入到已排序区的元素进行排序swap(arr[j],arr[j-1]);j-=1;}}return;
}
（3）希尔排序：

希尔排序（Shell Sort）是插入排序的一种改进版本，也称为递减增量排序。它通过将原始数组分割成多个子序列，对每个子序列进行插入排序，然后逐步缩小子序列的范围，最终完成排序。

希尔排序的基本算法思想：

  1. 选择一个增量序列，通常选择n/2、n/4、n/8...，直到增量为1。

  2. 对每个增量进行插入排序，将间隔为增量的元素分为一组，对每组进行插入排序。

  3. 缩小增量，重复第2步的操作，直到增量为1，即进行最后一次插入排序。

其算法的时间复杂度最好的情况下是O(nlogn)，最坏的情况下是O(n^2)

稳定性：不稳定

其过程如图：

 关键代码实现：
#define swap(a,b){\ //交换a,b__typeof(a) __c=(a);\ //将__c的类型在编译时，转换为与a相同的类型并赋值(a)=(b);\ //赋值交换(b)=__c;\ //赋值交换
}
void insert_sort(int *arr,int b,int n,int step){ //插入排序，b为起始下标，n为最大下标int ind=b; //记录要开始进行插入排序的点for(int i=b+step;i<n;i+=step){ //每次对间隔为step的元素排序if(arr[i]<arr[ind])ind=i;    //记录数组下标大而数据小的元素}while(ind>b){ swap(arr[ind],arr[ind-step]); //交换元素ind-=step; //每次对间隔为step的元素进行排序}for(int i=b+2*step;i<n;i+=step){int j=i;while(arr[j]<arr[j-step]){swap(arr[j],arr[j-step]);j-=step;}}return;
}
void shell_sort(int *arr,int b,int n){int k=2,bc=(n-b),step;do{step=bc/k==0?1:(bc/k);for(int i=b,I=b+step;i<I;i++){insert_sort(arr,i,n,step);}k*=2;}while(step!=1);return;
}
（4）快速排序： 

快速排序是通过选择一个基准元素，将数组分成两个子数组，一组小于基准元素，另一组大于基准元素。然后对两个子数组分别递归地进行快速排序，最终将整个数组排序。

快速排序的基本算法思想：
1. 选择一个基准元素，通常选择数组的第一个或最后一个元素。
2. 定义两个指针，一个指向数组的第一个元素，一个指向数组的最后一个元素。
3. 移动左指针，直到找到一个大于等于基准元素的元素。
4. 移动右指针，直到找到一个小于等于基准元素的元素。
5. 交换左指针和右指针所指向的元素。
6. 重复步骤3-5，直到左指针和右指针相遇。
7. 将基准元素与左指针所指向的元素互换位置。
8. 进行递归，对基准元素左边的子数组和右边的子数组进行快速排序。

其算法的时间复杂度最好的情况为O(nlogn)，最坏的情况为O(n^2)。

其稳定性：不稳定

其过程如图：

关键代码实现： 
#define swap(a,b){\__typeof(a) __c=(a);\(a)=(b);\(b)=__c;\
}
void quick_sort(int *arr,int l,int r){if(r-l<=2){if(r-l<=1)return;if(arr[l]>arr[l+1])swap(arr[l],arr[l+1]);return;}int x=l,y=r-1,z=arr[l];while(x<y){while(x<y&&z<=arr[y])--y;if(x<y)arr[x++]=arr[y];while(x<y&&arr[x]<=z)++x;if(x<y)arr[y]=arr[x];}arr[x]=z;quick_sort(arr,l,x);quick_sort(arr,x+1,r);return;
}
int main(){
（5）归并排序：

归并排序（Merge sort）是一种经典的排序算法，它采用分治法的思想将问题分解为更小的子问题，并且通过递归的方式解决这些子问题。然后将子问题的解合并起来，最终得到原问题的解。

归并排序的基本算法思想：

1. 每次将数组不断地二分为两个子数组，直到每个子数组只剩下一个元素。
2. 然后将两个子数组逐个合并起来，形成一个有序的新数组。

3.合并的方式是比较两个子数组的第一个元素，将较小的元素放入新数组中，并移动指针，继续比较下一个元素。
4. 重复上述步骤，直到将所有的子数组都合并起来，得到最终的有序数组。

归并排序的时间复杂度：最好的情况下：O(nlogn)；最坏的情况下：O(nlogn)。

这是一种稳定的排序算法，适用于各种数据类型。但是归并排序需要额外的存储空间来存储临时数组，空间复杂度为O(n)。

其过程如图：

原数组：[5，4，2，7，1，6，8，3]

关键代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define SMALL 1000000
__attribute__((constructor))
void __init_Rand__(){srand(time(0));
}
bool check(int *arr,int l,int r){for(int i=l+1;i<r;i++){if(arr[i]<arr[i-1])return false;}return true;
}
#define swap(a,b){\__typeof(a) __c=(a);\(a)=(b);\(b)=__c;\
}
#define TEST(func,arr,n){\printf("TEST:%s",#func);\int *temp=(int *)malloc(sizeof(int)*n);\memcpy(temp,arr,sizeof(int)*n);\long long b=clock();\func(temp,0,n);\long long e=clock();\if(check(temp,0,n)){\printf("\tOK");\}else{\printf("\tNO");\}\printf("\t%lldms\n",(e-b)*1000/CLOCKS_PER_SEC);\free(temp);\
}
int *getRandData(int n){int *arr=(int *)malloc(sizeof(int)*n);for(int i=0;i<n;i++){arr[i]=rand()%100+1;}return arr;
}
int *buff; //额外存储空间
void merge_sort(int *arr,int l,int r){ r为数组长度，l为开始位置，初始为0if(r-l<=1)return; //如果只有一个元素，返回结果int mid=(l+r)/2; //每次都将数组二分merge_sort(arr,l,mid); //递归二分前半段的数组merge_sort(arr,mid,r); //递归二分后半段的数组int p1=l,p2=mid,k=0;//p1记录第一个数组元素下标，p2记录中间元素下标，k记录当前位置，便于排序while(p1<mid||p2<r){ //前半段数组范围、后半段数组范围if(p2==r||(p1<mid&&arr[p1]<=arr[p2])){ buff[k++]=arr[p1++];}else{buff[k++]=arr[p2++];}}for(int i=l;i<r;i++)arr[i]=buff[i-l];return;
}
int main(){int *arr=getRandData(SMALL);buff=(int *)malloc(sizeof(int)*SMALL);TEST(merge_sort,arr,SMALL);free(buff);return 0;
}
（6）基数排序：

基数排序是一种非比较型的排序算法，它将数据按照位数进行分组，分别对每个位数进行排序，直到最高位数排序完毕。基数排序可以用于对非负整数进行排序。

基数排序的基本算法思想如下：

1. 将待排序的数据从最低位开始，按照个位数进行分组。
2. 对每个分组进行计数排序，将数据按照个位数的大小进行排序。
3. 将所有分组的数据按照排序结果进行合并。
4. 重复步骤1-3，按照十位数、百位数等依次进行排序，直到最高位数排序完毕。

基数排序的时间复杂度：最好的情况下：O(k*n)；最坏的情况下：O(k*n)。其中k是最大数的位数，n是待排序数据的个数。

基数排序的空间复杂度是O(n+k)。

基数排序的优点是稳定性好，适用于数据量较大且每个数位数较小的情况。然而，基数排序的缺点是需要占用大量的额外空间，且对于负数无法直接排序。

基数排序过程如图：

关键代码实现：
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#define K 65536
#define SMALL 1000000
__attribute__((constructor))
void __init_Rand__(){srand(time(0));
}
#define swap(a,b){\__typeof(a) __c=(a);\(a)=(b);\(b)=__c;\
}
bool check(int *arr,int l,int r){for(int i=l+1;i<r;i++){if(arr[i]<arr[i-1])return false;}return true;
}
#define TEST(func,arr,n){\printf("TEST:%s",#func);\int *temp=(int *)malloc(sizeof(int)*n);\memcpy(temp,arr,sizeof(int)*n);\long long b=clock();\func(temp,0,n);\long long e=clock();\if(check(temp,0,n)){\printf("\tOK");\}else{\printf("\tNO");\}\printf("\t%lldms\n",(e-b)*1000/CLOCKS_PER_SEC);\free(temp);\
}
int *getRandData(int n){int *arr=(int *)malloc(sizeof(int)*n);for(int i=0;i<n;i++){arr[i]=rand()%100+1;}return arr;
}
void radix_sort(int *arr,int l,int r){int *cnt=(int *)malloc(sizeof(int)*K);int *temp=(int *)malloc(sizeof(int)*r);memset(cnt,0,sizeof(int)*K);for(int i=0;i<r;i++)cnt[arr[i]%K]+=1;for(int i=1;i<K;i++)cnt[i]+=cnt[i-1];for(int i=r-1;i>=l;i--)temp[--cnt[arr[i]%K]]=arr[i];memcpy(arr,temp,sizeof(int)*r);memset(cnt,0,sizeof(int)*K);for(int i=0;i<r;i++)cnt[arr[i]/K]+=1;for(int i=1;i<K;i++)cnt[i]+=cnt[i-1];for(int i=r-1;i>=l;i--)temp[--cnt[arr[i]/K]]=arr[i];memcpy(arr,temp,sizeof(int)*r);free(temp);free(cnt);return;
}
int main(){int *arr=getRandData(SMALL);TEST(radix_sort,arr,SMALL);free(arr);return 0;
}

文章到此结束！

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

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

相关文章

GraphLLM：基于图的框架，通过大型语言模型处理数据

GraphLLM：基于图的框架，通过大型语言模型处理数据

GraphLLM是一个创新的框架&#xff0c;它允许用户通过一个或多个大型语言模型&#xff08;LLM&#xff09;来处理数据。这个框架不仅提供了一个强大的代理&#xff0c;能够执行网络搜索和运行Python代码&#xff0c;还提供了一套工具来抓取网页数据&#xff0c;并将其重新格式化…
阅读更多...
TransFormer--解码器：概括

TransFormer--解码器：概括

TransFormer--解码器&#xff1a;概括 假设我们想把英语句子I am good&#xff08;原句&#xff09;翻译成法语句子Je vais bien&#xff08;目标句&#xff09;。首先&#xff0c;将原句I am good送入编码器&#xff0c;使编码器 学习原句&#xff0c;并计算特征值。在前文中&…
阅读更多...
3D Gaussian Splatting 代码层理解之Part1

3D Gaussian Splatting 代码层理解之Part1

2023 年初，来自法国蔚蓝海岸大学和 德国马克斯普朗克学会的作者发表了一篇题为“用于实时现场渲染的 3D 高斯泼溅”的论文。该论文提出了实时神经渲染的重大进步，超越了NeRF等以往方法的实用性。高斯泼溅不仅减少了延迟，而且达到或超过了 NeRF 的渲染质量，在神经渲染领域掀…
阅读更多...
K8s学习笔记之了解k8s的网络模型

K8s学习笔记之了解k8s的网络模型

文章目录 docker 网络模型容器与容器之间&#xff0c;容器与宿主机之间如何通信容器访问外部网络外部网络访问容器 k8s 网络模型CNIpod 网络配置流程 k8s 热门网络插件介绍Flannel 来源Calico 来源Cilium 来源 k8s 网络插件的工作模式Flannel 的工作模式Calico 的工作模式BGP 和…
阅读更多...
探索高效的 Prompt 框架：RBTR 提示框架的奥秘与优势

探索高效的 Prompt 框架：RBTR 提示框架的奥秘与优势

前言 在当今数字化的时代&#xff0c;人工智能&#xff08;AI&#xff09;已经成为我们生活和工作中不可或缺的一部分。而 Prompt 作为与 AI 交互的关键工具&#xff0c;其质量直接影响着我们获取信息的准确性和有用性。今天&#xff0c;我们将深入探讨一个通用的 Prompt 框架…
阅读更多...
丹摩征文活动 | 深度学习实战：UNet模型的训练与测试详解

丹摩征文活动 | 深度学习实战：UNet模型的训练与测试详解

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 1、云实例&#xff1a;配置选型与启动1.1 登录注册1.2 配置 SSH 密钥对1.3 创建实例1.4 登录云实例 2、云存储&#xff1a;数据集上传…
阅读更多...
# 10_ Python基础到实战一飞冲天（一）--linux基础（十）

# 10_ Python基础到实战一飞冲天（一）--linux基础（十）

10_ Python基础到实战一飞冲天&#xff08;一&#xff09;–linux基础&#xff08;十&#xff09;–软链接硬链接-tar-gzip-bzip2-apt-软件源 一、其他命令-04-文件软链接的演练实现 1、ubuntu 桌面文件如下图&#xff1a; 2、需求&#xff1a;文件软链接的演练&#xff08;演…
阅读更多...
Python学习27天

Python学习27天

字典 dict{one:1,two:2,three:3} # 遍历1&#xff1a; # 先取出Key for key in dict:# 取出Key对应的valueprint(f"key:{key}---value:{dict[key]}")#遍历2&#xff0c;依次取出value for value in dict.values():print(value)# 遍历3&#xff1a;依次取出key,value …
阅读更多...
【Linux】进程的优先级

【Linux】进程的优先级

进程的优先级 一.概念二.修改优先级的方法三.进程切换的大致原理&#xff1a;四.上下文数据的保存位置&#xff1a; 一.概念 cpu资源分配的先后顺序&#xff0c;就是指进程的优先权&#xff08;priority&#xff09;。 优先权高的进程有优先执行权利。配置进程优先权对多任务环…
阅读更多...
ubuntu无密码用SCP复制文件到windows

ubuntu无密码用SCP复制文件到windows

默认情况下，ubuntu使用scp复制文件到windows需要输入密码: scp *.bin dev001@172.16.251.147:~/Desktop/. 为了解决每次复制文件都要输入密码这个问题，需要按如下操作: 1.创建ssh密钥 ssh-keygen -t ed25519 -C "xxx_xxx_xxx@hotmail.com" 2.使用scp复制公钥到w…
阅读更多...
单片机GPIO中断+定时器 软件串口通信

单片机GPIO中断+定时器 软件串口通信

单片机GPIO中断定时器 软件串口通信 解决思路代码示例 解决思路 串口波特率9600bps,每个bit约为1000000us/9600104.16us&#xff1b; 定时器第一次定时时间设为52us即半个bit的时间&#xff0c;其目的是偏移半个bit时间&#xff0c;之后的每104us采样并读取1bit数据。使得采样…
阅读更多...
使用Web Components构建模块化Web应用

使用Web Components构建模块化Web应用

&#x1f493; 博客主页&#xff1a;瑕疵的CSDN主页 &#x1f4dd; Gitee主页&#xff1a;瑕疵的gitee主页 ⏩ 文章专栏&#xff1a;《热点资讯》 使用Web Components构建模块化Web应用 使用Web Components构建模块化Web应用 使用Web Components构建模块化Web应用 引言 Web Co…
阅读更多...
每行数据个数在变的二维数组的输出

每行数据个数在变的二维数组的输出

#include<stdio.h> int main() {//定义四个一维数组int arr1[1] { 1 };int arr2[3] { 1,2,3 };int arr3[5] { 1,2,3,4,5 };int arr4[7] { 1,2,3,4,5,6,7 };//把四个一维数组放进一个二维数组int* arr[4] { arr1,arr2,arr3,arr4};//预先计算好每一个数组真实的长度in…
阅读更多...
【SSL证书】腾讯云SSL续签备忘录

【SSL证书】腾讯云SSL续签备忘录

适用于证书过期了&#xff0c;需要替换证书的场景。本备忘录为nginx使用证书场景 步骤&#xff1a;一共7步。 登录腾讯云控制台->申请免费证书->腾讯云审核->下载->登录服务器->替换证书->重启nginx 1.登录控制台 https://console.cloud.tencent.com/ssl…
阅读更多...
AVL树

AVL树

一.AVL树的概念 AVL树是一颗特殊的二叉搜索树。二叉搜索树在有些极端情况下可能会出现单支的情况&#xff0c;这会影响其插入查找的效率。而AVL树是一个高度平衡的二叉搜索树&#xff0c;它要求任何的左右子树的高低差都小于等于1。它可以通过去控制左右子树的高度差来控制二叉…
阅读更多...
鸿蒙开发-网络数据访问、应用本地数据保存

鸿蒙开发-网络数据访问、应用本地数据保存

HTTP概述 HTTP&#xff0c;全称Hyper Text Transfer Protocol 超文本传输协议。 HTTP请求为短连接。客户端发起请求&#xff0c;服务器返回响应。本次连接即结束。 添加网络权限 在访问网络之前&#xff0c;需要在module.json5中给APP添加网络权限 "module": {&…
阅读更多...
画 五边形 思路

画 五边形 思路

1. 计算圆心 view 中心点 2.规定半径 R < view宽度 / 2 3.计算五边形五个顶点&#xff08;角度A 2π / 5&#xff09; 4. 五点相连 转载&#xff1a; Android自定义控件 芝麻信用分雷达图 - 简书
阅读更多...
网络工程实验三：DHCP的配置

网络工程实验三：DHCP的配置

#实验仅供参考&#xff0c;勿直接粘贴复制&#xff0c;用以学习交流# #对于软件的使用&#xff0c;请移步到实验一观看# 1、实验目的&#xff1a; &#xff08;1&#xff09;掌握DHCP工作原理。 &#xff08;2&#xff09;配置路由器作为DHCP服务器。 &#xff08;3&#x…
阅读更多...
手写体识别Tensorflow实现

手写体识别Tensorflow实现

简介&#xff1a;本文先讲解了手写体识别中涉及到的知识&#xff0c;然后分步讲解了代码的详细思路&#xff0c;完成了手写体识别案例的讲解&#xff0c;希望能给大家带来帮助&#xff0c;也希望大家多多关注我。本文是基于TensorFlow1.14.0的环境下运行的 手写体识别Tensorflo…
阅读更多...
【SpringBoot】公共字段自动填充

【SpringBoot】公共字段自动填充

问题引入 JavaEE开发的时候&#xff0c;新增字段&#xff0c;修改字段大都会涉及到创建时间(createTime)&#xff0c;更改时间(updateTime)&#xff0c;创建人(craeteUser)&#xff0c;更改人(updateUser)&#xff0c;如果每次都要自己去setter()&#xff0c;会比较麻烦&#…
阅读更多...
最新文章

Copyright @ 2022~2023