Posted on 2012-08-01 22:52
小胡子 閱讀(509)
評論(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