Posted on 2012-08-01 22:52
小胡子 阅读(502)
评论(0) 编辑 收藏
1 using System;
2 using System.Collections.Generic;
3 using System.Linq;
4 using System.Text;
5 using System.Threading;
6 using System.Diagnostics;
7
8 namespace 排序算法大PK
9 {
10 class Program
11 {
12 static void Main(string[] args)
13 {
14 Console.WriteLine("规则：取20000随机数，比较各自耗时");
15 for (int i = 0; i < 5; i++)
16 {
17 List<int> list = new List<int>();
18 //取20000个随机数到集合中
19 for (int j = 0; j < 20000; j++)
20 {
21 Thread.Sleep(1);
22 list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 1000000));
23 }
24 Console.WriteLine("\n第" + i + "轮PK:");
25 Stopwatch watch = new Stopwatch(); //Stopwatch类可用于准确地测量运行时间
26 watch.Start(); //开始或继续测量某个时间间隔的运行时间
27 var result = list.OrderBy(single => single).ToList();
28 watch.Stop();
29 Console.WriteLine("快速排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
30 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
31 watch.Reset();
32 watch.Start();
33 result = DirectSequence(list);
34 watch.Stop();
35 Console.WriteLine("选择排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
36 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
37 watch.Reset();
38 watch.Start();
39 result = BubbleSort(list);
40 watch.Stop();
41 Console.WriteLine("冒泡排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
42 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
43 watch.Reset();
44 watch.Start();
45 result = HeapSort(list);
46 watch.Stop();
47 Console.WriteLine("堆排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
48 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
49 watch.Reset();
50 watch.Start();
51 result = InsertionSort(list);
52 watch.Stop();
53 Console.WriteLine("插入排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
54 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
55 watch.Reset();
56 watch.Start();
57 result = HillSort(list);
58 watch.Stop();
59 Console.WriteLine("希尔排序耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
60 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
61
62 watch.Reset();
63 watch.Start(); //开始或继续测量某个时间间隔的运行时间
64 result = list.OrderByDescending(single => single).Take(10).ToList();
65 watch.Stop();
66 Console.WriteLine("快速排序取最大的前十个耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
67 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
68 watch.Reset();
69 watch.Start();
70 result = NewHeapSort(list, 10);
71 watch.Stop();
72 Console.WriteLine("堆排序取最大的前十个耗费时间：" + watch.ElapsedMilliseconds + "毫秒");
73 Console.WriteLine("输出前十个数：" + string.Join("，", result.Take(10).ToList()));
74 }
75 Console.Read();
76 }
77
78 #region 冒泡排序
79 private static List<int> BubbleSort(List<int> list)
80 {
81 int temp = 0;
82 for (int i = 0; i < list.Count - 1; i++)
83 {
84 for (int j = list.Count - 1; j > i; j--)
85 {
86 if (list[j] < list[j - 1])
87 {
88 temp = list[j - 1];
89 list[j - 1] = list[j];
90 list[j] = temp;
91 }
92 }
93 }
94 return list;
95 }
96 #endregion
97
98 #region 选择排序
99 static List<int> DirectSequence(List<int> list)
100 {
101 for (int i = 0; i < list.Count - 1; i++)
102 {
103 int min = i; //假设min的下标的值最小
104 for (int j = i + 1; j < list.Count; j++)
105 {
106 //如果min下标的值大于j下标的值,则记录较小值下标j
107 if (list[min] > list[j])
108 {
109 min = j;
110 }
111 }
112 //最后将假想最小值跟真的最小值进行交换
113 var temp = list[min];
114 list[min] = list[i];
115 list[i] = temp;
116 }
117 return list;
118 }
119 #endregion
120
121 #region 堆排序
122 //构建堆
123 static void HeapAdjust(List<int> list, int parent, int length)
124 {
125 //temp保存当前父节点
126 int temp = list[parent];
127
128 //得到左孩子(这可是二叉树的定义，大家看图也可知道)
129 int child = 2 * parent + 1;
130
131 while (child < length)
132 {
133 //如果parent有右孩子，则要判断左孩子是否小于右孩子
134 if (child + 1 < length && list[child] < list[child + 1])
135 child++;
136
137 //父亲节点大于子节点，就不用做交换
138 if (temp >= list[child])
139 break;
140
141 //将较大子节点的值赋给父亲节点
142 list[parent] = list[child];
143
144 //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
145 parent = child;
146
147 //找到该父亲节点较小的左孩子节点
148 child = 2 * parent + 1;
149 }
150 //最后将temp值赋给较大的子节点，以形成两值交换
151 list[parent] = temp;
152 }
153
154 ///<summary>
155 /// 堆排序
156 ///</summary>
157 ///<param name="list"></param>
158 static List<int> HeapSort(List<int> list)
159 {
160 //list.Count/2-1:就是堆中父节点的个数
161 for (int i = list.Count / 2 - 1; i >= 0; i--)
162 {
163 HeapAdjust(list, i, list.Count);
164 }
165
166 //最后输出堆元素
167 for (int i = list.Count - 1; i > 0; i--)
168 {
169 //堆顶与当前堆的第i个元素进行值对调
170 int temp = list[0];
171 list[0] = list[i];
172 list[i] = temp;
173
174 //因为两值交换，可能破坏根堆，所以必须重新构造
175 HeapAdjust(list, 0, i);
176 }
177 return list;
178 }
179 #endregion
180
181 #region 堆排序（取前N大的数）
182 ///<summary>
183 /// 构建堆
184 ///</summary>
185 ///<param name="list">待排序的集合</param>
186 ///<param name="parent">父节点</param>
187 ///<param name="length">输出根堆时剔除最大值使用</param>
188 static void NewHeapAdjust(List<int> list, int parent, int length)
189 {
190 //temp保存当前父节点
191 int temp = list[parent];
192
193 //得到左孩子(这可是二叉树的定义哇)
194 int child = 2 * parent + 1;
195
196 while (child < length)
197 {
198 //如果parent有右孩子，则要判断左孩子是否小于右孩子
199 if (child + 1 < length && list[child] < list[child + 1])
200 child++;
201
202 //父节点大于子节点，不用做交换
203 if (temp >= list[child])
204 break;
205
206 //将较大子节点的值赋给父亲节点
207 list[parent] = list[child];
208
209 //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造
210 parent = child;
211
212 //找到该父节点左孩子节点
213 child = 2 * parent + 1;
214 }
215 //最后将temp值赋给较大的子节点，以形成两值交换
216 list[parent] = temp;
217 }
218
219 ///<summary>
220 /// 堆排序
221 ///</summary>
222 ///<param name="list">待排序的集合</param>
223 ///<param name="top">前K大</param>
224 ///<returns></returns>
225 public static List<int> NewHeapSort(List<int> list, int top)
226 {
227 List<int> topNode = new List<int>();
228
229 //list.Count/2-1:就是堆中非叶子节点的个数
230 for (int i = list.Count / 2 - 1; i >= 0; i--)
231 {
232 NewHeapAdjust(list, i, list.Count);
233 }
234
235 //最后输出堆元素（求前K大）
236 for (int i = list.Count - 1; i >= list.Count - top; i--)
237 {
238 //堆顶与当前堆的第i个元素进行值对调
239 int temp = list[0];
240 list[0] = list[i];
241 list[i] = temp;
242
243 //最大值加入集合
244 topNode.Add(temp);
245
246 //因为顺序被打乱，必须重新构造堆
247 NewHeapAdjust(list, 0, i);
248 }
249 return topNode;
250 }
251 #endregion
252
253 #region 插入排序
254 static List<int> InsertionSort(List<int> list)
255 {
256 for (int i = 1; i < list.Count; i++)
257 {
258 var temp = list[i];
259 int j;
260 for (j = i - 1; j >= 0 && temp < list[j]; j--)
261 {
262 list[j + 1] = list[j];
263 }
264 list[j + 1] = temp;
265 }
266 return list;
267 }
268 #endregion
269
270 #region 希尔排序(“插入排序”的改进版)
271 static List<int> HillSort(List<int> list)
272 {
273 int num = list.Count / 2; //取增量
274 while (num >= 1)
275 {
276 for (int i = num; i < list.Count; i++) //无须序列
277 {
278 var temp = list[i];
279 int j;
280 for (j = i - num; j >= 0 && temp < list[j]; j = j - num) //有序序列
281 {
282 list[j + num] = list[j];
283 }
284 list[j + num] = temp;
285 }
286 num = num / 2;
287 }
288 return list;
289 }
290 #endregion
291
292 }
293 }
294
转自：
http://blog.csdn.net/a125138/article/details/7790463