|
Posted on 2010-08-26 20:43 lzh525 阅读(512) 评论(0) 编辑 收藏 引用 所属分类: 数据结构及算法问题
1 #include<iostream> 2 #include<malloc.h> 3 using namespace std; 4![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 5 bool cmp(int &a,int &b)//sort函数的比较函数,若将"<"改为">"则为降序排列 6![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
7 return a<b;
8 } 9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 10 int comp(const void*a,const void*b)//C语言qsort的升序排序函数,将return语句的a,b互换则为降序排序 11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
12 return *(int*)a-*(int*)b;
13 } 14![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 15 void sel_sort(int *s,int n)//选择排序,分为有序,无序两部分。每次迭代中选择无序部分的最小元素,并移动到有序部分的尾部![](http://www.cppblog.com/Images/dot.gif) ![](http://www.cppblog.com/Images/dot.gif) 16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 17 int i,j; 18 int min; 19 for(i=0;i<n;i++) 20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 21 min=i; 22 for(j=i+1;j<n;j++) 23 if(s[j]<s[min]) 24 min=j; 25 swap(s[i],s[min]); 26 } 27 } 28![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 29 void insert_sort(int *s,int n)//插入排序,分为有序,无序两部分。每次迭代中无序部分的下一个元素被插入到有序部分的何时位置。 30![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 31 int i,j; 32 for(i=1;i<n;i++) 33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 34 j=i; 35 while((j>0)&&(s[j]<s[j-1])) 36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 37 swap(s[j],s[j-1]); 38 j--; 39 } 40 } 41 } 42![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 43 void quick_sort(int *s,int left,int right)//快速排序 44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 45 int r=right,l=left,p=s[right]; 46 while(l<r) 47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 48 swap(s[l],s[r]); 49 while(l<r&&s[r]>p) 50 r--; 51 while(l<r&&s[l]<=p) 52 l++; 53 } 54 swap(s[left],s[r]); 55 if(left<r-1) 56 quick_sort(s,left,r-1); 57 if(right>r+1) 58 quick_sort(s,r+1,right); 59 } 60![](http://www.cppblog.com/Images/OutliningIndicators/None.gif) 61 int main() 62![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) { 63 int i,n; 64 int *a; 65 while(cin>>n) 66![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 67 //a=(int *)malloc(n*sizeof(int)); 68 a=new int[n]; 69 for(i=0;i<n;i++) 70 cin>>a[i]; 71 sel_sort(a,n); 72 //insert_sort(a,n); 73 //quick_sort(a,0,n-1); 74 //sort(a,a+n,cmp);//c++排序库函数 75 //qsort(a,n,sizeof(int),comp);//c排序库函数 76 for(i=0;i<n;i++) 77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { 78 cout<<a[i]; 79 if(i!=n-1) 80 cout<<","; 81 if(i==n-1) 82 cout<<endl; 83 } 84 } 85 //free(a); 86 delete(a); 87 return 0; 88 }
|