总结一下常见的排序算法.
1) 合并排序
算法思想很简单,就是把两个已经排序好的序列进行合并，成为一个排序好的序列。例如 已经排好 124567 和 389两个序列,只需要合并这两个序列即可排成有序的序列123456789
不多说了,直接附上源代码!这个排序的实现帮助我更好的理解了递归!哈哈!
首先给出一个非递归的版本!
View Code
1 #include<cstdio> 2 #define maxn 100 3 void merge(int *c,int *d,int l,int m,int r); 4 void mergepass(int *x,int *t,int s,int n); 5 void mergesort(int *a,int n) 6 { 7 int *b=new int [n]; 8 int s=1; 9 while(s<n) 10 { 11 mergepass(a,b,s,n); 12 s+=s; 13 mergepass(b,a,s,n); 14 s+=s; 15 } 16 } 17 void mergepass(int *x,int *y,int s,int n) 18 { 19 int i=0; 20 while(i<=n-2*s) 21 { 22 merge(x,y,i,i+s-1,i+2*s-1); 23 i=i+2*s; 24 } 25 if(i+s<n) 26 merge(x,y,i,i+s-1,n-1); 27 else 28 for(int j=i;j<=n-1;j++) 29 y[j]=x[j]; 30 } 31 void merge(int *c,int *d,int l,int m,int r)//合并c中从l到r的元素并把他们写入d中! 32 { 33 int i=l,j=m+1,k=l; 34 while((i<=m)&&(j<=r)) 35 { 36 if(c[i]<=c[j]) 37 d[k++]=c[i++]; 38 else 39 d[k++]=c[j++]; 40 41 42 } 43 if(i>m) 44 for(int q=j;q<=r;q++) 45 d[k++]=c[q]; 46 else 47 for(int q=i;q<=m;q++) 48 d[k++]=c[q]; 49 50 } 51 int main() 52 { 53 int a[maxn]; 54 int length; 55 scanf("%d",&length); 56 for(int i=0;i<length;i++) 57 scanf("%d",&a[i]); 58 mergesort(a,length); 59 for(int i=0;i<length;i++) 60 printf("%d ",a[i]); 61 return 0; 62 }
然后给出一个递归的版本!
View Code
1 #include<cstdio> 2 int data[1000]; 3 void merge(int data[],int start,int mid,int end) 4 { 5 int *tmpleft,*tmpright; 6 int leftsize,rightsize; 7 int l,r,j; 8 l=0; 9 r=0; 10 j=0;; 11 leftsize=mid-start+1; 12 rightsize=end-mid; 13 tmpleft=new int[leftsize+1]; 14 tmpright=new int[rightsize+1]; 15 while(j<leftsize) 16 { 17 tmpleft[j]=data[start+j]; 18 j++; 19 } 20 j=0; 21 while(j<rightsize) 22 { 23 tmpright[j]=data[mid+1+j]; 24 j++; 25 } 26 j=0; 27 while(l<leftsize&&r<rightsize) 28 { 29 if(tmpleft[l]<tmpright[r]) 30 { 31 data[start+j++]=tmpleft[l++]; 32 } 33 else if(tmpleft[l]>tmpright[r]) 34 { 35 data[start+j++]=tmpright[r++]; 36 } 37 else 38 { 39 data[start+j++]=tmpright[r++]; 40 l++; 41 42 } 43 44 } 45 while(l<leftsize) 46 { 47 data[start+j++]=tmpleft[l++]; 48 } 49 while(r<rightsize) 50 data[start+j++]=tmpright[r++]; 51 delete [] tmpleft; 52 delete [] tmpright; 53 } 54 void merge_sort(int *data,int start,int end) 55 { 56 int mid; 57 if(start<end) 58 { 59 mid=(start+end)/2; 60 merge_sort(data,start,mid); 61 merge_sort(data,mid+1,end); 62 merge(data,start,mid,end); 63 } 64 } 65 int main() 66 { 67 int start; 68 int end; 69 int length; 70 scanf("%d",&length); 71 int i; 72 for(i=0;i<length;i++) 73 scanf("%d",&data[i]); 74 scanf("%d%d",&start,&end); 75 merge_sort(data,start,end); 76 for(i=start;i<=end;i++) 77 printf("%d ",data[i]); 78 return 0; 79 80 }
2)快速排序
基于这样的原理 : 假设设a[p.....r]是一个要排序的数组,我们 分解这个数组,指定一个ｑ使得ａ[p.....q-1]比ａ[ｑ]都要小,a[q+1.....r]比ａ[ｑ]都要大,下标ｑ中划分的时候计算!
通过递归的调用快速排序对a[p....q-1],a[q+1......r]进行排序! 然后是合并,由于是就地排序,所以是不需要合并操作的!
给出我的一个代码!
View Code
1 //将数组ａ[p...r]划分为两个子数组ａ[ｐ....q-1]和 ａ[q+1......r]使的a[p.....q-1]中的每个元素都小于a[p],但是a[q+1.....r]中的每个元素大于a[q] 2 #include<cstdio> 3 #define maxn 100 4 void swap(int &a,int &b) 5 { 6 int temp; 7 temp=a; 8 a=b; 9 b=temp; 10 } 11 int partion(int *a,int p,int r) 12 { 13 int x=a[r]; 14 int i=p-1; 15 int j; 16 for(j=p;j<=r-1;j++) 17 { 18 if(a[j]<=x) 19 { 20 i=i+1; 21 swap(a[i],a[j]); 22 } 23 24 25 } 26 swap(a[i+1],a[r]); 27 return i+1; 28 } 29 void quicksort(int *a,int p,int r) 30 { 31 int q; 32 if(p<r) 33 { 34 q=partion(a,p,r); 35 quicksort(a,p,q-1); 36 quicksort(a,q+1,r); 37 } 38 } 39 int main() 40 { 41 int a[maxn]; 42 printf("the length of array:\n"); 43 int length; 44 scanf("%d",&length); 45 int i; 46 printf("please input the data of the array:\n"); 47 for(i=1;i<=length;i++) 48 scanf("%d",&a[i]); 49 printf("please input the range of the sort:\n"); 50 int left; 51 int right; 52 scanf("%d%d",&left,&right); 53 quicksort(a,left,right); 54 printf("after sorting:\n"); 55 for(i=1;i<=length;i++) 56 printf("%d ",a[i]); 57 printf("\n"); 58 return 0; 59 }
3)堆排序
思路:就是将要排序的元素以最大堆的数据结构存储起来!(按从小到大的形式排序就要用到最大堆!),假设我们输入的元素是 a[1.....n],我们先建立最大堆建好后,根据最大堆的特点,我们知道
a[1]是最大的元素,每次我们把这个元素与最后一个最大堆元素交换,将最大的长度减去1(这时去掉最后一个已经排好顺序的元素),交换后有可能使得根元素违反了最大堆性质的元素,我们就要
维护最大的性质!
附上代码:
View Code
1 #include<cstdio> 2 #define parent(i) (i/2) 3 #define left(i) (i*2) 4 #define right(i) (i*2+1) 5 int heapsize; 6 int a[100]; 7 void swap(int &a,int &b) 8 { 9 int temp; 10 temp=a; 11 a=b; 12 b=temp; 13 14 } 15 /* 保持最大堆性质的函数 */ 16 void max_heap(int *a,int i) 17 { 18 int largest; 19 int l=left(i); 20 int r=right(i); 21 if(l<=heapsize&&a[l]>a[i]) 22 largest=l; 23 24 else 25 largest=i; 26 if(r<=heapsize&&a[r]>a[largest]) 27 largest=r; 28 if (largest!=i) 29 { 30 swap(a[i],a[largest]); 31 max_heap(a,largest); 32 } 33 } 34 /*从最小的叶子节点编到根节点来建立最大堆*/ 35 void build_heap(int *a,int length) 36 { 37 int i; 38 for(i=length/2;i>=1;i--) 39 max_heap(a,i); 40 41 } 42 void heap_sort(int *a) 43 { 44 build_heap(a,heapsize); 45 int i; 46 for(i=heapsize;i>=2;i--) 47 { 48 swap(a[1],a[i]); 49 heapsize-=1; 50 max_heap(a,1); 51 52 } 53 } 54 55 int main() 56 { 57 int length; 58 printf("you want to input the length:\n"); 59 scanf("%d",&length); 60 heapsize=length; 61 int i; 62 printf("you want to input the data of array:\n"); 63 for(i=1;i<=length;i++) 64 scanf("%d",&a[i]); 65 build_heap(a,length); 66 printf("the max heap has built.\n"); 67 for(i=1;i<=length;i++) 68 printf("%d ",a[i]); 69 printf("\n"); 70 printf("sorting:\n"); 71 heap_sort(a); 72 for(i=1;i<=length;i++) 73 printf("%d ",a[i]); 74 printf("\n"); 75 return 0; 76 77 }
4)计数排序
思路：就是要将数据出现的次数记录下来！然后根据出现的次数，选择每个数据在数组中的位置。说的不是很清楚，可以举一个例子说明一下，比如说，有a[1....5]这五个数分别是 0 ，1 ，2 ，4 ，5 这里面最大的数是5，我们可以用一个新的数组记录一下每个数出现的次数！比如这个例子，我们可以用一个数组b[0....5]来记录每个数出现的次数，b[0]=1 b[1]=1,b[2]=1,b[3]=0,b[4]=0,b[5]=1；其中b[i]=n表示i出现了n次，例如b[i]=7,表示ｉ元素有7个,根据每个输入的元素ｘ确定小于ｘ的个数,例如有17个小于ｘ的值,则ｘ应该放入第18个位置
实现的过程可以看下面的代码！
View Code
1 #include<cstdio> 2 #include<cstring> 3 #define maxn 100 4 /* a数组是要排序的数组,b 5 * 数组是放入排序结果后的数组. 6 * ｃ数组用来记录输入数中每个元素的个数 7 * 8 */ 9 void count_sort(int *a,int *b,int max_sum,int a_length) 10 { 11 int *c=new int [max_sum+2]; 12 int i; 13 for(i=0;i<=max_sum;i++) 14 c[i]=0; 15 for(i=1;i<=a_length;i++) 16 c[a[i]]++; 17 for(i=1;i<=max_sum;i++) 18 c[i]=c[i]+c[i-1]; 19 for(i=a_length;i>=1;i--) 20 { 21 b[c[a[i]]]=a[i]; 22 c[a[i]]--; 23 } 24 delete [] c; 25 26 } 27 int main() 28 { 29 int a[maxn]; 30 int b[maxn]; 31 while(1) 32 { 33 memset(a,0,sizeof(a)); 34 memset(b,0,sizeof(b)); 35 printf("please input the number of array and the max data:\n"); 36 int a_length,max_data; 37 int i; 38 scanf("%d%d",&a_length,&max_data); 39 printf("please input the data of array :\n"); 40 for(i=1;i<=a_length;i++) 41 scanf("%d",&a[i]); 42 count_sort(a,b,max_data,a_length); 43 for(i=1;i<=a_length;i++) 44 printf("%d ",b[i]); 45 printf("\n"); 46 47 } 48 return 0; 49 }
先介绍这些吧!其实排序是有很多算法的,以后再总结一些!