海水正蓝

面朝大海,春暖花开
posts - 145, comments - 29, trackbacks - 0, articles - 1
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

【转】 排序算法—看谁速度更快

Posted on 2012-08-01 22:52 小胡子 阅读(507) 评论(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(01000000));
 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

只有注册用户登录后才能发表评论。


网站导航: