自学内容网 自学内容网
自学内容网 > 正文

排序算法（基础）大全

🕗 发布于 2024-11-17 06:25 排序算法  算法  c语言  数据结构  开发语言  

一、排序算法的作用：

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

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;
}

文章到此结束！


原文地址：https://blog.csdn.net/qq_74143684/article/details/142014575

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024