十种基本排序（总结）

编程入门行业动态更新时间:2024-10-07 13:25:07

十种基本排序（总结）

排序算法总结：

1.冒泡排序：

	最经典的排序算法，因为算法太过基础就不再介绍；附一个冒泡排序的优化算法：

#include<stdio.h>
#include<stdlib.h>
void bubble(int  arr[],int len)//第一种
{if(arr==NULL||len==0){printf("bublle error\n");exit(1);}int pos=len-1;
for(int i=0;i<len-1;i++)
{int temp;int j;for( j=0;j<pos;j++){if(arr[j]>arr[j+1]){temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;pos=j;}}if(pos==j-1){break;	}}
}
void bubble2(int  arr[],int len)//第二种
{if(arr==NULL||len==0){printf("bublle error\n");return ;}
//	int pos=len-1;
for(int i=0;i<len-1;i++)
{int flag=0;
//	int temp;for( int j=0;j<len-1-i;j++){if(arr[j]>arr[j+1]){arr[j]=arr[j+1]^arr[j];arr[j+1]=arr[j+1]^arr[j];arr[j]=arr[j+1]^arr[j];flag=j+1;}}if(flag==0)break;i=len-flag-1;}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}
for(int i=0;i<len;i++)
{printf("%d ",arr[i]);
}
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}
bubble2(arr,n);
tra(arr,n);
return 0;	
}

其中第二种是优化的冒泡排序算法，第一种。。。大家可以当做对照。
所谓优化也就是对上次交换的位置进行记录，也就是可能出现后半段数据已经有序，就没必要将j再跑一遍后面的数据。只需要将j更新到flag的位置的前一位即可。也就是i=len-flag-1，也就是j可以更新为的范围更新为flag-1;(这一部分比较绕，大家可以仔细思考一下)而如果flag没有被赋值那么说明数据已经全部有序，不需要对数据再进行排序。

2.插入排序：

也是基本算法之一，就是将数据按照顺序从小到大挨个往数组里面第一层循环表示遍历次数，以及已经有序的数据数，第二层循环进行在有序的数据插入。
此处附代码：

#include<stdio.h>
#include<stdlib.h>
void Insert(int arr[],int len)
{
for(int i=0;i<len-1;i++)
{
int maxx=arr[i+1];
for(int j=i;j>=0;j--)
{if(arr[j]>maxx){arr[j+1]=arr[j];}else{arr[j+1]=maxx;break;}
}
}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}Insert(arr,n);tra(arr,n);return 0;	
}

由于代码就是基本插入排序，就不再赘述。

3.希尔排序：

希尔排序是建立在插入排序上的一种排序算法。原来的插入算法是每隔一个数据进行比较。而希尔排序是将间隔增大，以及设置不同的起始点。也就是固定地间隔不同起始点进行插排。由于间隔较多以及间隔大小的减少就可以将数据最后实现完整的排序。
另附代码：

#include<stdio.h>
#include<stdlib.h>
void Insert(int arr[],int len,int space,int st)
{
for(int i=st;i<len-space;i+=space)
{
int maxx=arr[i+space];
for(int j=i;j>=st;j-=space)
{if(arr[j]>maxx){arr[j+space]=arr[j];}else{arr[j+space]=maxx;break;}
}
}}
void ShellSort(int arr,int len)
{
int temp=len/2;
while(temp)
{
for(int i=0;i<temp;i++)
{
Insert(arr,len,temp,i);
}temp/=2;
}}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}ShellSort(arr,n);tra(arr,n);return 0;	
}

本代码的间隔设置为二分思想间隔，也就是每次除二。
其实希尔排序的核心就是设置适合的增量，让排序更加有效。

4.选择排序：

选择排序思想就是：首先一层循环来遍历整个数组并且表示需要遍历的次数，然后就是将数据从0到len-i进行遍历，把最大数据对应的下标记录下来最后将该数据和arr[len-i]进行交换。
此处附代码：


#include<stdio.h>
#include<stdlib.h>
void Select(int arr[],int len)
{int index=0;for(int i=1;i<=len-1;i++){index=0;for(int j=1;j<len-i;j++){if(arr[j]>arr[index]){index=j;	}}if(arr[len-i]<arr[index]){arr[len-i]=arr[len-i]^arr[index];	arr[index]=arr[len-i]^arr[index];	arr[len-i]=arr[len-i]^arr[index];	}}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}Select(arr,n);tra(arr,n);return 0;	
}

选择排序也较为简单此处不再赘述。

5.计数排序：

计数排序思想是：就是首先确定数据的最大值和最小值。然后在借助一个辅助数组。开辟max-min+1的空间。然后将数据再遍历一遍，并将arr[i]-min作为下标将辅助数组的数值加一。最后再遍历一遍辅助数组，并再套一个循环，将辅助数组减为0为止。每当有一个数就将i+minn放入原数组。从而完成排序
另附代码一份：

#include<string.h>
#include<stdio.h>
#include<stdlib.h>
void Cnt(int arr[],int len)
{if(arr==NULL||len==0){return ;	}int minn=arr[0];int maxx=arr[0];for(int i=0;i<len;i++){if(arr[i]<minn){minn=arr[i];	}if(arr[i]>maxx){maxx=arr[i];	}}int *arr_cnt=(int *)malloc(sizeof(int)*(maxx-minn+1));memset(arr_cnt,0,sizeof(int)*(maxx-minn+1));for(int i=0;i<len;i++){arr_cnt[arr[i]-minn]++;	}int j=0;int i=0;for(i=0;i<maxx-minn+1;i++){while(arr_cnt[i]){arr[j]=i+minn;j++;arr_cnt[i]--;}}free(arr_cnt);arr_cnt=NULL;}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}Cnt(arr,n);tra(arr,n);return 0;	
}

6.快排

快排是一种非常有效的排序算法时间复杂度。核心思想是将数据进行区间分割也就是类似于二分。将一个数设为评判值然后将所有大于它本身的数据放在右边，小于它本身的数值放在左边（该数据就放在了最终有序数组中应该存放的位置）。最后逐渐缩小区间，然后让小区间有序，最后整体都是有序的数据。
另附代码：

#include<stdio.h>
#include<stdlib.h>
void quick(int arr[],int left,int right)//挖坑填补法
{int i=left;int j=right;int key=arr[i];if(i>=j)return ;while(i<j){while(i<j&&arr[j]>key){j--;	}if(i<j){arr[i]=arr[j];//	arr[i]=arr[i]^arr[j];//	arr[j]=arr[i]^arr[j];//	arr[i]=arr[i]^arr[j];}while(i<j&&arr[i]<key){i++;	}if(i<j){arr[j]=arr[i];//	arr[i]=arr[i]^arr[j];//	arr[j]=arr[i]^arr[j];//	arr[i]=arr[i]^arr[j];}}arr[i]=key;quick(arr,left,i-1);quick(arr,i+1,right);}
void quick2(int arr[],int left,int right)//区间分割由与少用了一层循环所以效率更高
{int index=left-1;int i=left;int j=right;if(i>=j){return ;}int key=arr[j];while(i<j){if(arr[i]<key){int temp=arr[index+1];arr[index+1]=arr[i];	arr[i]==temp;	//	arr[index+1]=arr[i]^arr[index+1];	index++;}i++;}int temp=arr[index+1];arr[index+1]=arr[i];	arr[i]=temp;	
quick2(arr,left,index);
quick2(arr,index+2,right);}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}quick2(arr,0,n-1);tra(arr,n);return 0;	
}

上面采用两中方法，由于代码的底层实现循环较为复杂所以原理上讲第二种比第一种更快一点。
第一种方法的思想：利用i和j进行双向查找一个查取最大的数一个查找最小的数。
第二种思想：查找最小的数将剩下的数留在数组里面。

归并排序：

算法思想：其本身和快排的思想类似但是快排是先将某一个数据放到最合理的地方，再将排序区间进行缩小最终达到所有数据都有序。而归并排序就是将数据一直递归缩小区间，当区间很小（1）的时候就将两个区间进行合并最终递归规返回。达到整体都有序。
另附代码：

#include<stdio.h>
#include<stdlib.h>
int min(int a,int b)
{if(a<b)return 1;else{return 0;}
}
void MergeSort(int arr[],int Left,int Right)
{if(Left>=Right)return ;int  mid=(Right+Left)>>1;MergeSort(arr,Left,mid);MergeSort(arr,mid+1,Right);int l=Left;int r=Right;int i=l;int j=mid+1;int arr_temp[r-l+1];int index=0;while(i<=mid&&j<=r){arr_temp[index++]=min(arr[i],arr[j])?arr[i++]:arr[j++];	}while(i<=mid){arr_temp[index++]=arr[i++];	}while(j<=r){arr_temp[index++]=arr[j++];	}int k=l;for(int i=0;i<index;i++){arr[k++]=arr_temp[i];}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}MergeSort(arr,0,n-1);tra(arr,n);return 0;	
}

值得强调的是，归并排序可以用来将多个有序数组归并为同一个有序数组。

堆排序：

这个是时间复杂度很低的排序方法，但也是较难掌握的排序方法。
算法思想：就是利用树的性质，将一个数组视为一棵二叉树进行处理，根据根的大小将其分为大根堆和小跟堆（也就是如果任意一个根的数值都大于其左儿子和右儿子的数值。那么这就是大根堆，反之就是小根堆）。然后将根和数组最后一个数据进行交换，并将最后一个有序数据视为抛弃（因为该数据已经有序）。然后再重新整树，使其重新变成大根堆（或者小根堆）。最后就是将数据按照此流程逐个替换，变成有序数列。
步骤：1.首先建立大根堆（本博文以大根堆为例）
1.1按照从最后一个父亲节点到0的顺序进行遍历调整。
1.2假如A父节点和B子节点交换，那么需要将A父节继续调整下去。
2.其次将根部数据与尾部数据交换，并将数组的大小减一（也就是忽略最后一个数据）
3.最后就是调整树，使其重新变成大根堆。
另附代码：

#include<stdio.h>
#include<stdlib.h>
void swap(int arr[],int a,int b)
{int temp=arr[a];arr[a]=arr[b];arr[b]=temp;
}
void change(int arr[],int len,int index)//调整函数一与adjust函数功能相同
{int ls=index*2+1;int rs=index*2+2;int temp=index;while(ls<len&&arr[ls]>arr[temp])temp=ls;while(rs<len&&arr[rs]>arr[temp])temp=rs;if(temp!=index){swap(arr,index,temp);change(arr,len,temp);}
}
void adjust(int arr[],int len, int root)//调整函数e二与changet函数功能相同
{
int maxx=0;
int left,right;
for(left=root*2+1;left<len;left=root*2+1)
{right=root*2+2;if(arr[left]>arr[root])maxx=left;
if(right<len&&arr[right]>arr[maxx])
{maxx=right;
}
if(arr[maxx]!=arr[root])
{
swap(arr,maxx,root);
root=maxx;
}
else{break;}
}
}
void HeepSort(int arr[],int len)
{for(int i=len/2-1;i>=0;i--){adjust(arr,len,i);	}for(int i=1;i<len;i++){swap(arr,0,len-i);adjust(arr,len-i,0);}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}HeepSort(arr,n);tra(arr,n);return 0;	
}

堆排序对于数据结构较差的同学可能比较费劲比如这里需要应用到树的几个性质。
1.若一个棵完全二叉树节点顺序按照0~n-1公用n各节点进行排序。那么他的最后一个父节点为n/2-1。
2.一个父亲节点的序号为i的话，那么如果2i+1<n的话那么他有左子节点。如果2i+2<n的话他有右子节点。

桶排序：

桶排序的思想：首先数据的要求就是等长的数据。数据结构表示就是利用类似图中的邻接表表示法。也就是按照最高位的数据进行区分，利用链表将数据挂在对应的的分区上。然后利用冒泡排序进行对链表的数据（注意不需要改变链表结构，交换其中的数据即可）进行排序。最后将数据将数据进行遍历。放入到原数组即可。

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node{int data;struct node *next;
}List;
void BucketSort(int arr[],int len,int size_num)
{if(arr==NULL||len==0){return ;}int maxx=-1;int minn=11;int temp=1;for(int i=1;i<size_num;i++){temp*=10;}for(int i=0;i<len;i++){if(arr[i]/temp>maxx){maxx=arr[i]/temp;	}if(arr[i]/temp<minn){minn=arr[i]/temp;}}printf("%d : %d",maxx,minn);List **Bucket=(List **)malloc(sizeof(List*)*(maxx-minn+1));memset(Bucket,0,sizeof(List*)*(maxx-minn+1));//插入节点for(int i=0;i<len;i++){int num_temp=arr[i]/temp;List *nod=(List *)malloc(sizeof(List));nod->data=arr[i];nod->next=Bucket[num_temp-minn];Bucket[num_temp-minn]=nod->next;}//链表排序for(int i=0;i<=maxx-minn;i++){List *head=Bucket[i];while(head!=NULL)//{List *next=head->next;while(next->next!=NULL)	{if(next->next->data<next->data){int temp_num=next->data;next->data=next->next->data;next->next->data=temp_num;}next=next->next;}head=head->next;}//放回函数int j=0;for(int i=0;i<=maxx-minn;i++){List *curnod=Bucket[i];while(curnod!=NULL){arr[j]=curnod->data;curnod=curnod->next;j++;//}}//释放List *pDel=NULL;for(int i=0;i<=maxx-minn;i++){List *temp=Bucket[i];while(temp){pDel=temp;temp=temp->next;free(pDel);pDel=NULL;}}}
}
void tra(int arr[],int len)
{if(arr==NULL||len==0){printf("tra error\n");return ;}for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");
}
int main()
{int n;scanf("%d",&n);int arr[n];for(int i=0;i<n;i++){scanf("%d",&arr[i]);}BucketSort(arr,n,4);tra(arr,n);return 0;	
}

桶排序的算法一般适用于对小数进行排序。注意此处链表适用于头插法更为简便。

基数排序：

算法思想：就是将数据先按个位进行排序，然后十位，百位…最高位。也是和桶排序类似，将数据利用链表进行存储。不过值得注意的是，这里需要保持数据的有序性所以只能利用尾插法（指的是单向链表）。
步骤：1.首先找到最大的数据有多少位（maxx位）。
2.然后遍历将数据进行从1到maxx进行先除再取模的方法进行分组。
3.将链表进行排序。
4.将数据放回原数组。
5.重复·2 4步骤完成排序。
另附代码：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>typedef struct radix
{int nValue;struct radix *pNext;
}Radix;void Sort(int arr[],int nLength,int nBegin,Radix **pRadix)
{//基数int nBase = 1;while(nBegin > 1){nBase*=10;nBegin--;}//元素入桶Radix *pTemp = NULL;Radix *pNode = NULL;int nIndex;int i;for(i = 0;i<nLength;i++){nIndex = arr[i]/nBase%10;pTemp = (Radix*)malloc(sizeof(Radix));pTemp->nValue = arr[i];pTemp->pNext = NULL;//尾添加if(pRadix[nIndex] == NULL){pRadix[nIndex] = pTemp;}else{pNode = pRadix[nIndex];while(pNode->pNext != NULL){pNode = pNode->pNext;}pNode->pNext = pTemp;}}//放回原数组nBegin = 0;for(i = 0;i<10;i++){pTemp = pRadix[i];while(pTemp){arr[nBegin] = pTemp->nValue;nBegin++;pTemp = pTemp->pNext;}}//释放小链表for(i = 0;i<10;i++){pTemp = pRadix[i];while(pTemp){pNode = pTemp;pTemp = pTemp->pNext;free(pNode);pNode = NULL;}}memset(pRadix,0,sizeof(Radix*)*10);
}void RadixSort(int arr[],int nLength)
{if(arr == NULL || nLength <= 0)return;//最大值int i;int nMax = arr[0];for(i = 1;i<nLength;i++){if(arr[i] > nMax){nMax = arr[i];}}//拆位int nCount = 0;while(nMax){nCount++;nMax/=10;}//按位处理Radix **pRadix = (Radix**)malloc(sizeof(Radix*)*10);memset(pRadix,0,sizeof(Radix*)*10);for(i = 1;i<=nCount;i++){Sort(arr,nLength,i,pRadix);	}//释放free(pRadix);pRadix = NULL;
}void Print(int arr[],int nLength)
{if(arr == NULL || nLength <= 0)return;int i;for(i = 0;i<nLength;i++){printf("%d ",arr[i]);}printf("\n");
}int main()
{int arr[] = {10,12,99,6,2,8,11,9,3,7,89,51,90,1,116};RadixSort(arr,sizeof(arr)/sizeof(arr[0]));Print(arr,sizeof(arr)/sizeof(arr[0]));return 0;
}