使用C语言实现12种排序方法

2023-08-04 01:32:04 65

1.冒泡排序

思路：比较相邻的两个数字，如果前一个数字大，那么就交换两个数字，直到有序。

时间复杂度O(n^2)，稳定性：这是一种稳定的算法。

代码实现：

voidbubble_sort(intarr[],size_tlen){
size_ti,j;
for(i=0;iarr[j]){//如果前一个比后一个大
swap(&arr[j-1],&arr[j]);//交换两个数据
hasSwap=true;
}
}
if(!hasSwap){
break;
}
}
}

2.插入排序

思路：把一个数字插入一个有序的序列中，使之仍然保持有序，如对于需要我们进行排序的数组，我们可以使它的前i个数字有序，然后再插入i+1个数字，插入到合适的位置使之仍然保持有序，直到所有的数字有序。

时间复杂度：O(n^2)稳定性：稳定的算法

代码实现：

voidinsert_sort(intarr[],intlen){
inti,j;
for(i=1;i=0&&arr[j]>key;j--){//找到插入的位置
arr[j+1]=arr[j];//把需要插入的元素后面的元素往后移
}
arr[j+1]=key;//插入该元素
}
}

3.折半插入排序

思路：本质上是插入排序，但是通过半分查找法找到插入的位置，让效率稍微快一点。

时间复杂度：O(n^2)，稳定性：稳定的算法。

代码实现：

voidhalf_insert_sort(intarr[],intlen){
inti,j;
for(i=1;i=left;j--){//把后面的元素往后移
arr[j+1]=arr[j];
}
arr[j+1]=key;//插入元素
}
}

4.希尔排序

思路：先取一个正整数d1

时间复杂度：O(n^1.3),算法效率上大大提高。稳定性：不稳定的算法。

代码实现：

voidshell_sort(intarr[],intlen){//本质上也是一种插入排序，避免了大量数据的移动，在每一组排序过后，每个数据已经到了大致的位置。
inti,j;
intstep=0;
for(step=len/2;step>=1;step=step/2){//分组分为step组,对每组的元素进行插入排序
for(i=step;i=0&&arr[j]>key;j=j-step){
arr[j+step]=arr[j];
}
arr[j+step]=key;
}
}
}

5.选择排序

思路：通过循环找到最大值所在的位置，然后把最大值和最后一个元素进行交换，通过循环直到所有的数据有序。时间复杂度：O(n^2)稳定性：不稳定的算法

代码实现：

voidselect_sort(intarr[],size_tlen){
size_ti,j;
for(i=0;i
6.鸡尾酒排序
思路：选择排序的一种改进，一次循环直接找到最大值和最小值的位置，把最大值和最后一个元素进行交换，最小值和最前一个元素进行交换，所以最外层的循环只需要执行len/2次即可
时间复杂度：O(n^2)稳定性：不稳定的算法
代码实现：
voidcocktail_sort(intarr[],size_tlen){
size_ti,j;
for(i=0;iarr[j]){//找到最小值下标
min=j;
}
}
if(max!=j-1){
swap(&arr[max],&arr[j-1]);//交换最大值和未进行排序的最后一个元素
}
if(min==j-1){//如果最小值在未进行排序的最后一个位置，那么经过最大值的交换，已经交换到了最大值所在的位置
min=max;//把最小值的坐标进行改变
}
if(min!=i){
swap(&arr[i],&arr[min]);//交换最小值和未进行排序的最前的元素
}
}
}
7.堆排序
思路：把数据进行大堆化，然后依次交换堆顶(最大值)和最后一个元素,在使堆顶重新大堆化，最后循环过后数组便有序。过程：
最大堆调整（MaxHeapify）：将堆的末端子节点作调整，使得子节点永远小于父节点创建最大堆（BuildMaxHeap）：将堆中的所有数据重新排序
堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算时间复杂度：O(nlgn)稳定性：不稳定的算法
实现代码：
voidre_heap(intarr[],size_tindex,size_tlen){
size_tchild=2*index+1;//左节点坐标
intkey=arr[index];//当前节点值
while(childkey){//如果子节点的值比根节点的值大
arr[index]=arr[child];//改变根节点的值
}else{
break;
}
index=child;
child=2*index+1;
}
arr[index]=key;//插入记录好的值
}
voidheap_sort(intarr[],size_tlen){
inti;
for(i=len/2;i>=0;i--){
re_heap(arr,i,len);//对第i个根节点进行大堆化
}
for(i=len-1;i>0;i--){
swap(&arr[0],&arr[i]);//交换第一个和最后一个元素
re_heap(arr,0,i);//对第一个元素进行大堆化
}
}
8.快速排序
思路：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。过程：
(1)首先设定一个分界值，通过该分界值将数组分成左右两部分
(2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。
(3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。时间复杂度：O(nlog2n)稳定性：不稳定的算法
代码实现：
voidquick_sort(intarr[],size_tleft,size_tright){
if(left>=right){//如果只有一个元素，那就是有序的，返回
return;
}
inti=left;
intj=right;
intkey=arr[left];//基准值
while(i=key){//从右边找一个比基准值小的数，
--j;
}
arr[i]=arr[j];//把这个值放到基准值的位置处
while(i1)//元素个数至少两个才进行递归调用，这样可以少一次递归
quick_sort(arr,left,i-1);//对基准值左边的元素进行排序
if(right-i>1)
quick_sort(arr,i+1,right);//对基准值右边的元素进行排序
}
9.归并排序
思路：对于两个有序的子序列，可以把它们合并在一起，变成一个新的完全有序的序列，因此归并排序和快排差不多，都是递归的进行。时间复杂度：O(nlog2n)稳定性：稳定的算法代码实现：
voidmerge(intarr[],intleft,intright){
inti,j,k;
intmid=(left+right)/2;
intlen=mid-left+1;
int*temp=malloc(sizeof(arr[0])*len);
for(i=0;i=right){//如果只有一个元素说明这个序列有序，那就返回
return;
}
intmid=(left+right)/2;//对两个有序的数组进行排序，
merge_sort(arr,left,mid);//对[left,mid]这个区间的元素进行排序
merge_sort(arr,mid+1,right);//对[mid+1,right]这个区间内的元素进行排序
merge(arr,left,right);//这个序列的[left,mid]为有序的序列[mid+1,right]也为有序的序列
}
10.计数排序
思路：这是一种基于比较的算法，我们用一个大数组来存放这些数据，这些数据在这个大数组中的表现形式是以这个大数组的下标存在的，比如57,60,42这三个数字进行排序，那么用一个大数组，这个大数组的arr[57]=1,arr[60]=1,arr[42]=1，然后遍历这个大数组就行了。
时间复杂度：O(n+k),其中这个k为数据的范围，所以计数排序最适合数据比较集中的数组排序。稳定性：稳定的算法
代码实现：
voidcount_sort(intarr[],size_tlen){
intmax=arr[0];//最大值
intmin=arr[0];//最小值
size_ti;
for(i=0;iarr[i]){//找到最小值
min=arr[i];
}
}
intcnt=max-min+1;//范围
int*prr=malloc(cnt*sizeof(int));//申请临时空间
for(i=0;i
11.桶排序
思路：工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。这是一种以消耗大量空间来换取高效率的排序方式，时间复杂度：O(N+C)，其中C=N*(logN-logM)，M为桶的数量。所以对于桶排序，桶的数量越多，其排序效率越高。稳定性：稳定的算法代码实现：首先定义桶这个类型：
typedefstructBucket{
intvect[100];//其实这里使用链表更好，但是我比较懒，就懒得用链表了
intcnt;//当前桶内存放数据的个数
}
Bucket;
voidbucket_sort(intarr[],size_tlen){
intmin=arr[0];
intmax=arr[0];
size_ti;
for(i=0;iarr[i]){//找到最小值
min=arr[i];
}
if(max
12.基数排序
基数排序（radixsort）属于“分配式排序”（distributionsort），又称“桶子法”（bucketsort）或binsort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。
解法：
1.首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中；2.接下来将这些桶子中的数值重新串接起来，接着再进行一次分配，这次是根据十位数来分配；3.接下来将这些桶子中的数值重新串接起来，持续进行以上的动作直至最高位数为止。时间复杂度：设待排序列为n个记录，d个关键码，关键码的取值范围为radix，则进行链式基数排序的时间复杂度为O(d(n+radix))，其中，一趟分配时间复杂度为O(n)，一趟收集时间复杂度为O(radix)，共进行d趟分配和收集。稳定性：稳定的算法；
代码实现：
还是定义桶的类型：
typedefstructBucket{
intvect[100];//同样的可以用链表
intcnt;
}Bucket;

voidbase_sort(intarr[],size_tlen){
size_ti;
Bucketbucket[10]={};//十个桶
intmax=arr[0];
for(i=0;imax){
max=arr[i];
}
}
size_tj,k;
intnum=1;//用来获得相应位数上的数字的关键参数，
//比如要获得个位上的参数时num=1;
//获得十位上的数字时num=10;
//以此类推
do{
for(i=0;i
总结
以上所述是小编给大家介绍的用C语言完整实现12种排序方法，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对毛票票网站的支持！如果你觉得本文对你有帮助，欢迎转载，烦请注明出处，谢谢！
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

使用C语言实现12种排序方法

1.冒泡排序

2.插入排序

3.折半插入排序

4.希尔排序

5.选择排序

6.鸡尾酒排序

7.堆排序

8.快速排序

9.归并排序

10.计数排序

11.桶排序

12.基数排序

热门推荐

随机推荐