|
|
Posted on 2010-08-26 20:43 lzh525 阅读(512) 评论(0) 编辑 收藏 引用 所属分类: 数据结构及算法问题
1 #include<iostream>
2#include<malloc.h>
3using namespace std;
4
5bool cmp(int &a,int &b)//sort函数的比较函数，若将"<"改为">"则为降序排列
6   {
7 return a<b;
8 }
9
10int comp(const void*a,const void*b)//C语言qsort的升序排序函数，将return语句的a,b互换则为降序排序
11{
12 return *(int*)a-*(int*)b;
13}
14
15void sel_sort(int *s,int n)//选择排序，分为有序，无序两部分。每次迭代中选择无序部分的最小元素，并移动到有序部分的尾部
16{
17 int i,j;
18 int min;
19 for(i=0;i<n;i++)
20  {
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
29void insert_sort(int *s,int n)//插入排序，分为有序，无序两部分。每次迭代中无序部分的下一个元素被插入到有序部分的何时位置。
30{
31 int i,j;
32 for(i=1;i<n;i++)
33 {
34 j=i;
35 while((j>0)&&(s[j]<s[j-1]))
36 {
37 swap(s[j],s[j-1]);
38 j--;
39 }
40 }
41}
42
43void quick_sort(int *s,int left,int right)//快速排序
44{
45 int r=right,l=left,p=s[right];
46 while(l<r)
47 {
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
61int main()
62{
63 int i,n;
64 int *a;
65 while(cin>>n)
66 {
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 {
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}
|