九大排序算法(c语言版)

这篇具有很好参考价值的文章主要介绍了九大排序算法(c语言版)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

过年这几天晚上在家码代码学了一点。

代码中排序的数字均由rand()函数随机生成。

一、冒泡排序(2.8)

一个经典的不能再经典的排序算法。

优化前:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define N 100
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++)
        arr[i]=rand()%N;
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n------------------\n");
}
void bubleSort(int arr[],int length){
    for(int i=0;i<length-1;i++){
        for(int j=0;j<length-1-i;j++){
        	if(arr[j+1]<arr[j]){
	            int temp=arr[j+1];
	            arr[j+1]=arr[j];
	            arr[j]=temp;
		    }	
        }
    }
}
int main(){
    srand((unsigned int)time(NULL));
    int arr[N];
    intiArr(arr,N);
    showArr(arr,N);
    bubleSort(arr,N);
    showArr(arr,N);
    system("pause");
}

两个for循环搞定。

优化后:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void intiArr(int arr[],int length){
	for(int i;i<length;i++){
		arr[i]=rand()%20;
	}
}
void showArr(int arr[],int length){
	for(int i=0;i<length;i++){
		printf("%d ",arr[i]);
	}
	printf("\n---------------------\n");
}
bubSort(int arr[],int length){
	int flag=1;
	while(length--&flag){
		flag=0;
		for(int i=0;i<length;i++){
			if(arr[i+1]<arr[i]{
				flag=1;
				int temp=0;
				temp=arr[i+1];
				arr[i+1]=arr[i];
				arr[i]=temp;
			}
		}
	}
}
int main(void){
	srand((unsigned int)time(NULL));
	intiArr(arr,MAXSIZE);
	showArr(arr,MAXSIZE);
	bubSort(arr,MAXSIZE);
	showArr(arr,MAXSIZE);
	system("pause");
	return 0;
}

加入了一个flag变量,用于减少多余的比较和交换,大大提高代码运行效率,减少循环次数。

二、插入排序(2.9)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++){
        arr[i]=rand()%20;
    }
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n-----------------\n");
}
void insertSort(int arr[],int length){
    for(int i=1;i<length;i++){
        for(int j=i;j>=1&&arr[j]<arr[j-1];j--){
            int temp=0;
            temp=arr[j];
            arr[j]=arr[j-1];
            arr[j-1]=temp;
        }
    }
}
int main(){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    intiArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    insertSort(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
}

冒泡增强版,就是拿后面的数字和前面的相比,小的放前面。

三、选择排序(2.10)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void initArr(int arr[],int length){
    for(int i=0;i<length;i++){
        arr[i]=rand()%20;
    }
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n-----------------\n");
}
void selectSort(int arr[],int length){
    for(int i=0;i<length;i++){
        int k=i;
        for(int j=i+1;j<length;j++){
            if(arr[j]<arr[k])
                k=j;
        }
        int temp=arr[i];
        arr[i]=arr[k];
        arr[k]=temp;
    }
}
int main(void){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    initArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    selectSort(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
}

需要定义i,j,k三个变量,i,k从0出发,j从1出发,j往后排查有没有比i更小的数字,然后寄存在k里,经过这一轮循环,i与k交换位置,i++。

四、希尔排序(2.11)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++){
        arr[i]=rand()%20;
    }
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n-----------------\n");
}
void shellArr(int arr[],int length){
    int h=1;
    int t=length/3;
    while(h<t)
        h=h*3+1;
    while(h>=1){
        for(int i=h;i<length;i++){
            for(int j=i;j>=h&&arr[j]<arr[j-h];j-=h){
                int temp=arr[j];
                arr[j]=arr[j-h];
                arr[j-h]=temp;
            }
        }
        h/=3;
    }
}
int main(){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    intiArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    shellArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
}

设置步长为h,数字之间跨越比较,有点类似那个约瑟夫环,处理起多的数据比插入排序要好。

五、快速排序(2.12)

快速排序是我个人认为这9个排序算法里面最好用的,快速排序之所以是里面唯一一个名字里面敢称快速的,说明发明它的人还是很自信的,它的逻辑不难,处理效率也极高。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++){
        arr[i]=rand()%20;
    }
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n----------------\n");
}
void quickSort(int arr[],int left,int right){
    if(left>=right)return;
    int i=left;
    int j=right;
    int pivot=arr[i];
    while(i<j){
        while(i<j&&arr[j]>=pivot){
            j--;
        }arr[i]=arr[j];
        while(i<j&&arr[i]<=pivot){
            i++;
        }arr[j]=arr[i];
    }
    arr[i]=pivot;
    quickSort(arr,left,i-1);
    quickSort(arr,i+1,right);
}
int main(){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    intiArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    quickSort(arr,0,MAXSIZE-1);
    showArr(arr,MAXSIZE);
    system("pause");
}

中间设置一个轴pivot,让左右两边的数和轴进行比较,确保轴的左边都小于轴,轴的右边都大于轴;找到中位数之后进行递归,函数自己调用自己,向左向右递归扫清那些无序的数。

六、归并排序(2.13)

优化前:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
void intiArr(int arr[],int length){
	for(int i;i<length;i++){
		arr[i]=rand()%20;
	}
}
void showArr(int arr[],int length){
	for(int i=0;i<length;i++){
		printf("%d ",arr[i]);
	}
	printf("\n---------------------\n");
}
void mergeSort(int a[],int alen,int b[],int blen,int* temp){
    int i=0;
    int j=0;
    int k=0;
    while(i<alen&&j<blen)
        temp[k++]=a[i]<b[j]?a[i++]:b[j++];
    while(i<alen)
        temp[k++]=a[i++];
    while(j<blen)
        temp[k++]=b[j++];
}
int main(void){
    int a[5]={1,3,5,7,9};
    int b[3]={2,4,10};
    int temp[8];
    mergeSort(a,5,b,3,temp);
    showArr(temp,8);
}

优化前只能对两组已经排好序的短数组进行重新排序然后合并,遍历a,b数组然后进行相互比较,数值小的那个赋值到temp数组里面,如果a,b数组长度不一样,其中一个遍历完之后,那另一数组中剩余的数字直接赋值进temp数组中,这样合并后的temp数组就是一个有序的长数组。

优化后:

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#define MAXSIZE 20
void initArr(int arr[],int length){
    for(int i=0;i<MAXSIZE;i++){
        arr[i]=rand()%20;
    }
    
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n-----------------\n");
}
void merge(int arr[],int low,int mid,int height,int *temp){
    int i=low;
    int j=mid+1;
    int k=low;
    while(i<=mid&&j<=height)
        temp[k++]=arr[i]<arr[j]?arr[i++]:arr[j++];
    while(i<=mid)
        temp[k++]=arr[i++];
    while(j<=height)
        temp[k++]=arr[j++];
    for(int i=low;i<=height;i++)
        arr[i]=temp[i];
}
void merge_sort(int arr[],int low,int height,int *temp){
    if(low>=height)
        return;
    int mid=low+(height-low)/2;
    merge_sort(arr,low,mid,temp);
    merge_sort(arr,mid+1,height,temp);
    merge(arr,low,mid,height,temp);
}
void mergeSort(int arr[],int length){
    int *temp=(int *)malloc(sizeof(int)*length);
    assert(temp);
    merge_sort(arr,0,length-1,temp);
    free(temp);
}
int main(void){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    initArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    mergeSort(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
    return 0;
}

优化过后的算法相比之前复杂了挺多,但是应用范围更广了,可以处理那些不是有序的数组,需要先定义三个变量,先用第二个函数分隔,然后用第一个函数对前中后进行分部处理,注意mid通过low和height定义时,需要定义成

int mid=low+(height-low)/2;

而不能定义为

int mid=(low+height)/2;

因为考虑到越界的问题。

另外这个算法也需要递归和调用其他的函数,先分部再进行比较,不过写完之后使用起来很方便,还是只需要传入一个数组和它的长度作为参数就能实现,逻辑上和优化前的归并排序还是比较相似的,还是进行拆分与合并。

七、堆排序(2.14)

太难了,还没学会〒▽〒

情人节被堆排序干爆了,分外堆和内堆,下次搞懂了再专门写一篇文章细细讲解。

八、计数排序(2.15)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 20
#define N 100
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++)
        arr[i]=rand()%100;
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n----------------\n");
}
int temp[N];
void countSort(int arr[],int length){
    for(int i=0;i<length;i++){
        temp[arr[i]]++;
    }
    for(int i=0,j=0;i<N;i++){
        while(temp[i]--)
            arr[j++]=i;
    }
}
int main(void){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    intiArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    countSort(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
}

这个逻辑也比较简单,就是先统计数据里面都有哪些数,给这些数量非0的数分别开辟几片内存空间,然后从小到大依次按量释放。

九、基数排序(2.16)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define MAXSIZE 100
#define N 1000
void intiArr(int arr[],int length){
    for(int i=0;i<length;i++){
        arr[i]=rand()%N;
    }
}
void showArr(int arr[],int length){
    for(int i=0;i<length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n----------------\n");
}
int Temp[10][N];
void radixSort(int arr[],int length){
    int i,j;
    int pos;
    for(int k=10;k<10000;k*=10){
        for(i=0;i<length;i++){
            j=0;
            pos=(arr[i]%k)/(k/10);
            while(Temp[pos][j])
                j++;
            Temp[pos][j]=arr[i];
        }
        pos=0;
        for(i=0;i<10;i++){
            for(j=0;j<length&&Temp[i][j]!=0;j++){
                arr[pos++]=Temp[i][j];
                Temp[i][j]=0;
            }
        }
    }  
}
int main(){
    srand((unsigned int)time(NULL));
    int arr[MAXSIZE];
    intiArr(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    radixSort(arr,MAXSIZE);
    showArr(arr,MAXSIZE);
    system("pause");
}

举个例子:对以下序列进行基数排序
578,234,86,432,512,618,384
排序过程:
第一轮(在第零轮的基础上按位排在第零轮的基础上按位排在第零轮的基础上按10的零次方位排):432,512,234,384,86,578,618
第二轮(在第一轮的基础上按位排在第一轮的基础上按位排在第一轮的基础上按10的一次方位排):512,618,432,234,578,384,86
第三轮(在第二轮的基础上按位排在第二轮的基础上按位排在第二轮的基础上按10的二次方位排):86,234,384,432,512,578,618
第三轮结束序列自然排好序。86不够3位数,就往前面补零,即86 = 086.

最后安利一下这个宝藏up主,我是跟着他学的,他应该现在也是个大学生,讲的还是比较细的。

【十大经典排序算法(C语言描述)】https://www.bilibili.com/video/BV1nN4y1M7JK?p=10&vd_source=f0b5cc5a36c7293744b45f51763cd943

这是本人在寒假发布的第二篇文章,希望里面的一些代码能对你有一点点的帮助,我们一起进步。

不要欺负萌新哦~

                        ​​​​​​​        ​​​​​​​        ​​​​​​​        九大排序算法(c语言版),排序算法,c语言,算法文章来源地址https://www.toymoban.com/news/detail-838814.html

到了这里,关于九大排序算法(c语言版)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 排序算法——基数排序(C语言)

    什么是基数排序???基数排序是一种和快排、归并、希尔等等不一样的排序...它不需要比较和移动就可以完成整型的排序。它是时间复杂度是O(K*N),空间复杂度是O(K+M ) 基数排序是一种借助多的思想对单逻辑进行排序的方法。 基数排序根据每个位来分配

    2024年02月13日
    浏览(33)
  • 【排序算法】冒泡排序(C语言)

    【排序算法】—— 冒泡排序 ​ 冒泡排序法:(Bubble sort)是一种基础的交换排序,非常简单,一学就懂 ​ 对数组进行遍历,每次对相邻两个进行比较大小,若大的数值在前面则交换位置(升序),完成一趟遍历后数组中最大的数值到了数组的末尾位置,再对前面n-1个数值进

    2024年02月06日
    浏览(54)
  • 【排序算法】快速排序(C语言)

    【排序算法】—— 快速排序 ​ 快速排序的单趟排序是以一个数作为基准值,实现将数组中比基准数小的数放在基准值的左侧,比基准值大的数放在基准值的右侧。 ​ 我们共有3种实现方法。 ​ 霍尔是最初发现快速排序的人,它使用的单趟排序算法被称为霍尔法。 ​ 用ke

    2024年02月16日
    浏览(42)
  • 【排序算法】归并排序(C语言)

    【排序算法】—— 归并排序(C语言) 归并排序(MergeSort) 是建立在归并操作上的一种有效的排序算法,采用分治法排序,分为 分解 、 合并 两个步骤。 分解 :将数组分割成两个数组,再分别将两个数组又细分成2个数组,直到,最后每个数组都是一个元素,这时将该单元

    2024年02月08日
    浏览(34)
  • 【C语言】解析C语言实现排序的算法(冒泡排序、插入排序、选择排序、快速排序、归并排序)

    本博客主要围绕五种常见的排序算法展开讨论,包括选择排序、快速排序、归并排序、冒泡排序和插入排序。针对每种算法,我对其思想、特点、时间复杂度、稳定性以及优缺点进行了详细解释和比较。 冒泡排序算法是一种简单且常用的排序算法。它通过重复地交换相邻的元

    2024年02月13日
    浏览(41)
  • 排序算法-选择/堆排序(C语言)

    每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的 数据元素排完 。 在元素集合 array[i]--array[n-1] 中选择关键码最大 ( 小 ) 的数据元素。 若它不是这组元素中的最后一个 ( 第一个 ) 元素,则将它与这组元素中的最后一个

    2024年02月05日
    浏览(50)
  • 读改变未来的九大算法笔记08_并非万能的算法

    2.1.1.1. Alonzo Church 2.1.1.2. 在计算理论上的突破性工作至今仍是计算机科学许多方面的基础 2.1.1.3. 单独发现了不可判定问题的存在 2.1.1.3.1. 比图灵早几个月发表了自己的成果 2.1.1.3.2. 邱奇的公式更为抽象,且并未详尽地提及由机器执行的计算 5.3.1.1. 如果输入会崩溃,那么

    2024年02月08日
    浏览(33)
  • 【排序算法】C语言实现选择排序与冒泡排序

    这里是阿辉算法与数据结构专栏的第一篇文章,咱们就从排序算法开始讲起,排序算法有很多大致分为两类:基于比较的排序和非比较的排序 基于比较的排序:冒泡、选择、插入、希尔、堆、归并、随机快排 非比较的排序:桶排序 以上的排序算法阿辉都会讲到,今天阿辉主

    2024年02月04日
    浏览(40)
  • C语言分析基础排序算法——交换排序

    目录 交换排序 冒泡排序 快速排序 Hoare版本快速排序 挖坑法快速排序 前后指针法快速排序 快速排序优化 快速排序非递归版 见C语言基础知识指针部分博客C语言指针-CSDN博客 Hoare版本快速排序 Hoare版本快速排序的过程类似于二叉树前序遍历的过程,基本思想是:在需要排序的

    2024年03月14日
    浏览(46)
  • 八大排序算法(C语言版)之插入排序

    八大排序算法: 超链接: 插入排序 选择排序 交换排序 归并排序 非比较排序 排序:所谓排序,就是使一串记录, 按照其中的某个或某些的大小,递增或递减的排列起来的操作。稳定性:假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些

    2024年02月07日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包