排序算法（基础）大全

一、排序算法的作用：

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

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

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

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

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

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

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

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

二、基础排序算法： 

（1）选择排序：

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

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

稳定性：不稳定

其过程如图：

关键代码实现： 

#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()

稳定性：稳定

其过程如图：

关键代码实现：

#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()

稳定性：不稳定

其过程如图：

 关键代码实现：

#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()。

其稳定性：不稳定

其过程如图：

关键代码实现： 

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

文章到此结束！