上海天局信息技术有限责任公司

网站首页 > 天局论坛 > Language > C

几种常见排序算法原理&C语言实现

2019-06-10 15:55:48 上海天局信息技术有限责任公司 已读

https://www.cnblogs.com/gonsedup/p/6674822.html


一、冒泡排序(以下各法均以从小到大排序为例,定义len为数组array的长度)

  1. 原理:比较相邻元素的大小,对于每次循环,按排序的规则把最值移向数组的一端,同时循环次数依次减少。

  2. C代码实现

  • 写法一:复制代码

    void bubble_sort(int arr[],int len)//从数组头部开始,某一个元素与其后面的每个元素作比较 { int i,j,t; for(i=0;i<len-1;i++) for(j=i+1;j<len;j++) { if(arr[i]>arr[j]) { t=arr[i];arr[i]=arr[j];arr[j]=t; } } }

    复制代码

     

  • 写法二:复制代码

    void bubble_sort(int arr[],int len)//从数组的头部开始,相邻元素之间作比较 { int i,j,t; for(i=0;i<len-1;i++) for(j=0;j<len-1-i;j++) { if(arr[j]>arr[j+1]) { t=arr[j];arr[j]=arr[j+1];arr[j+1]=t; } } }

    复制代码

     

  • 写法三:复制代码

    void bubble_sort(int arr[],int len)//从数组的结尾开始返回,相邻元素之间作比较 { int i,j,t; for(i=0;i<len;i++) for(j=len-1;j>i;j--) { if(arr[j-1]>arr[j]) { t=arr[j];arr[j]=arr[j-1];arr[j-1]=t; } } }

    复制代码

     

二、选择排序

1.原理:先在未排序的数组中找出最值,通过交换将其放在数组第一位,然后再从剩余的未排序数组中找到另一个最值,将其放在已排序数组的末尾(第二次找到该最值后将其放在数组第二位)。以此类推,直到整个数组排完序。

2.C代码实现

复制代码

void select_sort(int arr[],int len) { int i,j,t,k; for(i=0;i<len-1;i++) { k=i; for(j=i+1;j<len;j++) { if(arr[k]<arr[j])//找最小值 { k=j; } } if(i!=k) { t=arr[i];arr[i]=arr[k];arr[k]=t; } } }

复制代码

 

三、插入排序(此处为直接插入排序,另外还有二分插入、链表插入等排序)

1.原理:将数据分为有序数列和无序数列两部分,一开始有序数列只有数列的第一个元素。对于无序数列的每个元素,要插入到有序数列中,方法是与有序数列中的末尾元素开始作比较,若前者大于后者则前者位置不变;否则,检索这个待插入元素小于第n个元素且大于或等于第n-1个元素的位置,同时将这个位置后面的元素往后移动(检索一次,移动一次),然后将其插入到这个位置。以此类推,直到无序数列元素个数为0。

2.C代码实现

复制代码

void insert_sort(int arr[],int len) { int i,j,k; for(i=0;i<=len;i++) { j=i-1; k=arr[i]; while(j>-1&&k<arr[j]) { arr[j+1]=arr[j]; j--; } arr[j+1]=k; } }

复制代码

 

四、快速排序

首先选取未排序数组的第一个数作为关键数据,然后,将所有比它小的数都放到它前面,将所有比它大的数都放到它后面,这个过程称为一趟快速排序。然后再对前后这两个数组进行类似排序,直到整个数组排好序。不难看出,这里最好采用到递归。具体算法步骤参见http://developer.51cto.com/art/201403/430986.htm

2.C代码实现

复制代码

void quick_sort(int ary[],int left,int right) { int i=left,j=right,k=ary[left],t;//k储存准基数     if(i>j) return ; while(i!=j) { while(i<j&&ary[j]>=k)//必须是先从右边比较,否则准基数归位时将出错             j--; while(i<j&&ary[i]<=k) i++; if(i<j) { t=ary[i];ary[i]=ary[j];ary[j]=t; } } ary[left]=ary[i]; ary[i]=k; quick_sort(ary,left,i-1); quick_sort(ary,i+1,right); }

复制代码

 

五、归并排序

1.原理:归并排序采用递归实现,总体上有两个步骤(分解与归并):

先将待排序数组R[0...n-1]分解成n个长度为1的有序序列(其实是一个元素),将相邻的两个元素有序归并,得到n/2个长度为2的有序序列;然后将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。

归并的具体步骤:比较arr[i]和arr[j],将较小值复制到新的数组new_arr[k],同时让i,j都加上1。如此循环下去,直到其中一个数组被复制完,再让另一个数组所剩余的元素(已排序)直接拼接到的new_arr的后面。

2.C代码实现

复制代码

void merge_sort2(int arr[],int new_arr[],int left,int right,int mid) { int i=left,j=mid+1,k=left; while(i!=mid+1&&j!=right+1)//归并 { if(arr[i]>arr[j]) new_arr[k++]=arr[j++]; else new_arr[k++]=arr[i++]; } while(i!=mid+1) new_arr[k++]=arr[i++]; while(j!=right+1) new_arr[k++]=arr[j++]; for(i=left;i<=right;i++) arr[i]=new_arr[i]; } void merge_sort1(int arr[],int new_arr[],int left,int right) { int mid; if(left<right) { mid=(left+right)/2; merge_sort1(arr,new_arr,left,mid);//左分解         merge_sort1(arr,new_arr,mid+1,right);//右分解         merge_sort2(arr,new_arr,left,right,mid);//调用子函数归并 } }

复制代码

 


分享到:
Powered by MetInfo 5.3.17 ©2008-2021 www.metinfo.cn