当前位置： 首页 > article >正文

排序算法（基础）大全

article 2024/11/17 22:59:23

一、排序算法的作用：

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

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=0
	for(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为开始位置，初始为0
	if(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.kler.cn/a/397876.html

相关文章：

  • GitLab 降级安装出现 500 错误，如何解决？
  • C：原反补码
  • vue3 element el-table实现表格动态增加/删除/编辑表格行，带有校验规则
  • 将已有的MySQL8.0单机架构变成主从复制架构
  • 手机ip地址异常怎么解决
  • 如何在 Ubuntu 上配置 Kotlin 应用环境 ？
  • 网络工程实验四：NAT的配置
  • 【MongoDB】MongoDB的核心-索引原理及索引优化、及查询聚合优化实战案例（超详细）
  • 【基于轻量型架构的WEB开发】课程 13.2.4 拦截器 Java EE企业级应用开发教程 Spring+SpringMVC+MyBatis
  • 机器学习：XGBoost模型（升级版）——高效且强大的树形模型
  • 安全见闻4
  • 《C语言程序设计现代方法》note-5 数组
  • 【开源免费】基于SpringBoot+Vue.JS卫生健康系统（JAVA毕业设计）
  • 【C++】OGRE：面向对象图形渲染库配置与示例
  • 2024山西省网络建设运维第十八届职业院校技能大赛解析答案（5. nginx 和 tomcat 服务）
  • 模型压缩相关技术概念澄清（量化/剪枝/知识蒸馏）
  • Pyhon基础数据结构（列表）【蓝桥杯】
  • 永磁同步电机负载估计--降阶龙贝格观测器
  • openai 论文Scaling Laws for Neural Language Models学习
  • 【项目日记】仿mudou的高并发服务器 --- 整体框架搭建 ，实现时间轮模块
  • 【Rust设计模式之新类型模式】
  • Android加载pdf
  • 鸿蒙HarmonyOS 地图不显示解决方案
  • ssm105基于JAVAEE技术校园车辆管理系统+jsp(论文+源码)_kaic
  • 力扣-Mysql-3278. 寻找数据科学家职位的候选人 II（中等）
  • 交易术语汇总（Technical Trading Dictionary)