下面是自己写的各种排序的程序:
1 #include<iostream>
2 using namespace std;
3
4 void swap(int *num,int i,int j)
5 {
6 int temp=num[i];
7 num[i]=num[j];
8 num[j]=temp;
9 }
10 //插入排序
11 void sort_charu(int *num,int n)
12 {
13 for(int i=1;i<n;i++)
14 {
15 if(num[i]<num[i-1])
16 {
17 int temp=num[i];
18 int j=i-1;
19 while(j>=0 && temp<num[j])
20 {
21 num[j+1]=num[j];
22 j--;
23 }
24 num[j+1]=temp;
25 }
26
27 }
28 }
29 ///////////////////////////////
30 //shell排序
31 void sort_shell(int *num,int n)
32 {
33 int d=n;
34 while(d>1)
35 {
36 d=d/2;
37 for(int i=d;i<n;i=i+1)
38 {
39 if(num[i]<num[i-d])
40 {
41 int temp=num[i];
42 int j=i-d;
43 while(num[j]>temp&&j>=0)
44 {
45 num[j+d]=num[j];
46 j=j-d;
47 }
48 num[j+d]=temp;
49 }
50 }
51 }
52 }
53 ////////////////////////////////////////////////
54 //选择排序
55 void sort_xuanze(int *num,int n)
56 {
57 int i,j;
58 for(i=n-1;i>=0;i--)
59 {
60 int max=num[0];
61 int xiabiao=0;
62 for(j=1;j<=i;j++)
63 {
64 if(max<num[j])
65 {
66 max=num[j];
67 xiabiao=j;
68 }
69 }
70 swap(num,i,xiabiao);
71 }
72 }
73 /////////////////////////////////
74 //堆排序
75 //将num数组中s到n的数据建立成为大顶堆
76 void heapadjust(int *num,int s,int n)
77 {
78 int temp=num[s];
79 for(int i=2*s;i<=n;i=i*2)
80 {
81 if(i<n && num[i+1]>num[i])
82 {
83 i++;
84 }
85 if(temp<num[i])
86 {
87 num[s]=num[i];
88 s=i;
89 }
90 }
91 num[s]=temp;
92 }
93
94 void sort_dui(int *num,int n)
95 {
96 //从最后一个非叶子节点开始组建大顶堆
97 for(int i=n/2;i>0;i--)
98 {
99 heapadjust(num,i,n);
100 }
101 //每次将第一个元素与堆顶元素交换,然后重新调整堆
102 for(int i=n;i>1;i--)
103 {
104 swap(num,i,1);
105 heapadjust(num,1,i-1);
106 }
107 }
108 //冒泡排序
109 void sort_maopao(int *num,int n)
110 {
111 int flag=1;
112 for(int i=n-1;i>0 && flag==1;i--)
113 {
114 flag=0;
115 for(int j=0;j<i;j++)
116 {
117 if(num[j]>num[j+1])
118 {
119 swap(num,j,j+1);
120 flag=1;
121 }
122 }
123
124 }
125 }
126 ///////////////////////////////////
127 //快速排序
128 void sort_quick_diedai(int *num,int start,int end)
129 {
130 int temp=num[start];
131 int i=start;
132 int j=end;
133 if(start<end)
134 {
135 while(i<j)
136 {
137 while(num[j]>=temp&&j>i)
138 {
139 j--;
140 }
141 if(i<j)
142 {
143 num[i]=num[j];
144 i++;
145 }
146 while(num[i]<=temp && i<j)
147 {
148 i++;
149 }
150 if(i<j)
151 {
152 num[j]=num[i];
153 j--;
154 }
155 }
156 num[i]=temp;
157 sort_quick_diedai(num,start,i);
158 sort_quick_diedai(num,i+1,end);
159 }
160 }
161 void sort_quick(int *num,int n)
162 {
163 sort_quick_diedai(num,0,n-1);
164 }
165 ///////////////////////////////////////////////////
166 //归并排序
167 //将num看成两个有序的数组,num[start...mid]和num[mid+1...end],将其合并为一个有序的数组
168 void merge_num(int *num,int start,int mid,int end,int *p)
169 {
170 int i=start;
171 int j=mid+1;
172 int k=0;
173 while(i<=mid &&j<=end)
174 {
175 if(num[i]<=num[j])
176 {
177 p[k++]=num[i++];
178 }
179 if(num[j]<=num[i])
180 {
181 p[k++]=num[j++];
182 }
183 }
184 while(i<=mid)
185 {
186 p[k++]=num[i++];
187 }
188 while(j<=end)
189 {
190 p[k++]=num[j++];
191 }
192 for(int i=0;i<k;i++)
193 {
194 num[start+i]=p[i];
195 }
196
197 }
198 void sort_guibing_digui(int *num,int start,int end,int *p)
199 {
200 if(start<end)
201 {
202 int mid=(start+end)/2;
203 sort_guibing_digui(num,start,mid,p);
204 sort_guibing_digui(num,mid+1,end,p);
205 merge_num(num,start,mid,end,p);
206 }
207 }
208 void sort_guibing(int *num,int n)
209 {
210 int *p=new int[n];
211 sort_guibing_digui(num, 0, n-1,p);
212 delete []p;
213 }
214
215 void print(int *num,int n)
216 {
217 for(int i=0;i<n;i++)
218 {
219 cout<<num[i]<<" ";
220 }
221 cout<<endl;
222 }
223 int main()
224 {
225 int num[10]={0,45,12,4,54,5,1,2,4,6};
226 //sort_charu(num,10);
227 //sort_xuanze(num,10);
228 //sort_maopao(num,10);
229 //sort_quick(num,10);
230 //sort_shell(num,10);
231 //sort_dui(num,9);//由于二叉树的性质所致,堆排序是从编号为1开始排序
232 sort_guibing(num,10);
233 print(num,10);
234 return 0;
235 }