c语言各种排序汇总(不包括优化后的)

2/22/2017来源:ASP.NET技巧人气:957

//冒泡

#define Max  8 void maopao(int *a); void maopao(int *a) { int i,j,flag=1,t; for(i=0;i<Max&&flag;i++) for(j=0;j<Max-i;j++) { flag=0; if(a[j]>a[j+1]) { t=a[j]; a[j]=a[j+1]; a[j+1]=t; flag=1; } } }

//选择排序

#define Max 8 void xuanze(int *a); void xuanze(int *a) { int i,j,min,t; for(i=0;i<Max;i++) { min=i; for(j=i+1;j<Max;j++) { if(a[j]<a[min]) min=j; } if(min!=i) { t=a[min]; a[min]=a[i]; a[i]=t; } } }

//直接插入排序

#define Max 8 void charu(int *a); void charu(int *a)  { int i,j,t; for(i=1;i<Max;i++) { if(a[i]<a[i-1]) { t=a[i]; for(j=i-1;a[j]>t&&j>=0;j--) { a[j+1]=a[j]; } a[j+1]=t; } } } 

//希尔排序

#define Max 8 void charu(int *a); void charu(int *a)  { int i,j,t; int gap=Max; do { gap=gap/3+1; for(i=gap;i<Max;i++) { if(a[i]<a[i-gap]) { t=a[i]; for(j=i-gap;a[j]>t&&j>=0;j-=gap) { a[j+gap]=a[j]; } a[j+gap]=t; } } } while(gap>1) } 

//堆排序

#include<stdio.h> void dui(int *a,int n); void change(int *a,int s,int n); void heapstack(int *a,int s,int n); void heapstack(int *a,int s,int n) { int i; int t; t=a[s]; for(i=2*s;i<=n;i=i*2) { if(i<n&&a[i]<a[i+1]) { i++; } if(t>=a[i]) { break; } a[s]=a[i]; s=i; } a[s]=t; } void change(int *a,int s,int n) { int t; t=a[s]; a[s]=a[n]; a[n]=t; } void dui(int *a,int n) { int i; for(i=n/2;i>0;i--) { heapstack(a,i,n); } for(i=n;i>1;i--) { change(a,1,i); heapstack(a,1,i-1); } } int main() { int a[10]={3,5,14,0,2,6,36,-8,4,1}; int i,j,t,min; min=0; for(j=1;j<10;j++) { if(a[min]>a[j]) min=j; } t=a[0]; a[0]=a[min]; a[min]=t; dui(a,9); for(i=0;i<10;i++) { PRintf("%4d",a[i]); } } //归并排序之递归

#include<stdio.h> void guibing(int *a,int n); void mer(int *listl,int listlsize,int *listr,int listrsize); void mer(int *listl,int listlsize,int *listr,int listrsize) { int i=0,j=0,k=0; int temp[8]; while(i<listlsize&&j<listrsize) { if(listl[i]<listr[j]) { temp[k++]=listl[i++]; } else { temp[k++]=listr[j++]; } } while(i<listlsize) { temp[k++]=listl[i++]; } while(j<listrsize) { temp[k++]=listr[j++]; } for(i=0;i<(listlsize+listrsize);i++) listl[i]=temp[i]; } void guibing(int *a,int n) { int *listl=a; int listlsize=n/2; int *listr=a+n/2; int listrsize=n-listlsize; if(n>1) { guibing(listl,listlsize); guibing(listr,listrsize); mer(listl,listlsize,listr,listrsize); } } int main() { int a[8]={2,7,4,9,3,5,6,1}; int i; guibing(a,8); for(i=0;i<8;i++) printf("%4d",a[i]); }

//对并排序之迭代

#include<stdio.h> #include <stdlib.h> void guibing(int *a,int n); void guibing(int *a,int n) { int left_min,left_max,right_min,right_max; int i,next; int *temp=(int *)(malloc(sizeof(int)*n)); for(i=1;i<n;i=i*2) { for(left_min=0;left_min<n-i;left_min=right_max) { left_max=right_min=left_min+i; right_max=left_max+i; if(right_max>n) right_max=n; next=0; while(left_min<left_max&&right_min<right_max) { if(a[left_min]<a[right_min]) { temp[next++]=a[left_min++]; } else { temp[next++]=a[right_min++]; } } while(left_min<left_max) { a[--right_min]=a[--left_max]; } while(next>0) { a[--right_min]=temp[--next]; } } } free(temp); } int main() { int a[8]={2,7,4,9,3,5,6,1}; int i; guibing(a,8); for(i=0;i<8;i++) { printf("%4d",a[i]); } }

快速排序#include<stdio.h> void speed(int *a,int n); void change(int *a,int low,int high); int mid(int *a,int low,int high); void swap(int *a,int high,int low); void swap(int *a,int high,int low) { int t; t=a[high]; a[high]=a[low]; a[low]=t; } int mid(int *a,int low,int high) { int point=a[low]; while(high>low) { while(high>low&&a[high]>=point) { high--; } swap(a,high,low); while(high>low&&a[low]<=point) { low++; } swap(a,high,low); } return low; } void change(int *a,int low,int high) { int point; if(low<high) { point=mid(a,low,high); change(a,low,point-1); change(a,point+1,high); } } void speed(int *a,int n) { change(a,0,n-1); } int main() { int a[8]={6,7,2,1,0,9,2,25}; int i; speed(a,8); for(i=0;i<8;i++) { printf("%4d",a[i]); } }