首页 > 代码库 > 5种常见排序算法原理&C语言实现
5种常见排序算法原理&C语言实现
一、冒泡排序(以下各法均以从小到大排序为例,定义len为数组array的长度)
- 原理:比较相邻元素的大小,对于每次循环,按排序的规则把最值移向数组的一端,同时循环次数依次减少。
- C代码实现
- 写法一:
//从数组头部开始,某一个元素与其后面的每个元素作比较
for(i=0;i<len-1;i++) for(j=i+1;j<len;j++) { if(array[i]>array[j]) { t=array[i];array[i]=array[j];array[j]=t; } } - 写法二:
//从数组的头部开始,相邻元素之间作比较
for(i=0;i<len-1;i++) for(j=0;j<len-1-i;j++) { if(array[j]>array[j+1]) { t=array[j];array[j]=array[j+1];array[j+1]=t; } }
- 写法三:
//从数组的结尾返回,相邻元素之间作比较
for(i=0;i<len;i++) for(j=len-1;j>i;j--) { if(array[j-1]>array[j]) { t=array[j];array[j]=array[j-1];array[j-1]=t; } }
二、选择排序
1.原理:先在未排序序列找出最值,将其与序列起始位置的元素互换(即将最值存放到起始位置),然后再从剩余未排序序列中找到该最值,将其放在已排序序列的末尾。以此类推,直到整个序列排完序。
2.C代码实现
for(i=0;i<len-1;i++) { k=i; for(j=i+1;j<len;j++) { if(array[k]>array[j]) { k=j; } } if(i!=k) { t=array[i];array[i]=array[k];array[k]=t; } }
三、插入排序(此处为直接插入排序,另外还有二分插入、链表插入等排序)
1.原理:将数据分为有序数列和无序数列两部分,一开始有序数列只有数列的第一个元素。对于无序数列的每个元素,要插入到有序数列中,方法是与有序数列中的末尾元素开始作比较,确定这个待插入元素小于第n个元素且大于或等于第n-1个元素,则将其插入到两个元素之间。以此类推,直到无序数列元素个数为0。
2.C代码实现
for(i=0;i<len;i++) { j=i-1; k=array[i]; while(j>-1&&k<array[j]) { array[j+1]=array[j]; j--; } array[j+1]=k; }
四、快速排序
2.C代码实现
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> void quicksort(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; quicksort(ary,left,i-1); quicksort(ary,i+1,right); } int main() { int i,len=7,array[100]={4,8,7,7,445,78,87}; printf("%d\n",len); quicksort(array,0,len-1); for(i=0;i<len;i++) printf("%d ",array[i]); return 0; }
五、归并排序
1.原理:归并排序采用递归实现,总体上有两个步骤(分解与合并):将待排序序列R[0...n-1]看成是n个长度为1的有序序列,将相邻的两个元素有序归并,得到n/2个长度为2的有序序列;将这些有序序列再次归并,得到n/4个长度为4的有序序列;如此反复进行下去,最后得到一个长度为n的有序序列。
合并的具体步骤:比较arr[i]和arr[j],若arr[i]<arr[j],则将arr[j]复制到新的数组new_arr[k],并让i,j都加上1;否则,将arr[j]复制到new_arr[k],并让i,j都加上1。如此循环下去,直到其中一个数组被复制完,再让另一个数组剩余的元素直接拼接到的new_arr的后面。
2.C代码实现
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> void merge_sort2(int arr1[],int new_arr1[],int left1,int right1,int mid1) { int i=left1,j=mid1+1,k=left1; while(i!=mid1+1&&j!=right1+1)//合并 { if(arr1[i]>arr1[j]) new_arr1[k++]=arr1[j++]; else new_arr1[k++]=arr1[i++]; } while(i!=mid1+1) new_arr1[k++]=arr1[i++]; while(j!=right1+1) new_arr1[k++]=arr1[j++]; for(i=left1;i<=right1;i++) arr1[i]=new_arr1[i]; } void merge_sort1(int arr1[],int new_arr1[],int left1,int right1) { int mid1; if(left1<right1) { mid1=(left1+right1)/2; merge_sort1(arr1,new_arr1,left1,mid1);//分解 merge_sort1(arr1,new_arr1,mid1+1,right1); merge_sort2(arr1,new_arr1,left1,right1,mid1); } } int main() { int i,arr[7]={4,8,7,7,445,78,87},new_arr[7]; merge_sort1(arr,new_arr,0,6); for(i=0;i<7;i++) printf("%d ",arr[i]); printf("\n"); return 0; }
5种常见排序算法原理&C语言实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。