算法系列15天速成——第二天 七大经典排序【中】
今天说的是选择排序，包括“直接选择排序”和“堆排序”。
话说上次“冒泡排序”被快排虐了，而且“快排”赢得了内库的重用，众兄弟自然眼红，非要找快排一比高下。
这不今天就来了两兄弟找快排算账。
1.直接选择排序：
先上图：
说实话，直接选择排序最类似于人的本能思想，比如把大小不一的玩具让三岁小毛孩对大小排个序，
那小孩首先会在这么多玩具中找到最小的放在第一位，然后找到次小的放在第二位，以此类推。。。。。。
，小孩子多聪明啊，这么小就知道了直接选择排序。羡慕中........
对的，小孩子给我们上了一课，
第一步： 我们拿80作为参照物（base），在80后面找到一个最小数20,然后将80跟20交换。
第二步: 第一位数已经是最小数字了，然后我们推进一步在30后面找一位最小数，发现自己最小，不用交换。
第三步：........
最后我们排序完毕。大功告成。
既然是来挑战的，那就5局3胜制。
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 SelectionSort
9 {
10 public class Program
11 {
12 static void Main(string[] args)
13 {
14 //5次比较
15 for (int i = 1; i <= 5; i++)
16 {
17 List<int> list = new List<int>();
18
19 //插入2w个随机数到数组中
20 for (int j = 0; j < 20000; j++)
21 {
22 Thread.Sleep(1);
23 list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));
24 }
25
26 Console.WriteLine("\n第" + i + "次比较：");
27
28 Stopwatch watch = new Stopwatch();
29
30 watch.Start();
31 var result = list.OrderBy(single => single).ToList();
32 watch.Stop();
33
34 Console.WriteLine("\n快速排序耗费时间：" + watch.ElapsedMilliseconds);
35 Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));
36
37 watch.Start();
38 result = SelectionSort(list);
39 watch.Stop();
40
41 Console.WriteLine("\n直接选择排序耗费时间：" + watch.ElapsedMilliseconds);
42 Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));
43
44 }
45 }
46
47 //选择排序
48 static List<int> SelectionSort(List<int> list)
49 {
50 //要遍历的次数
51 for (int i = 0; i < list.Count - 1; i++)
52 {
53 //假设tempIndex的下标的值最小
54 int tempIndex = i;
55
56 for (int j = i + 1; j < list.Count; j++)
57 {
58 //如果tempIndex下标的值大于j下标的值,则记录较小值下标j
59 if (list[tempIndex] > list[j])
60 tempIndex = j;
61 }
62
63 //最后将假想最小值跟真的最小值进行交换
64 var tempData = list[tempIndex];
65 list[tempIndex] = list[i];
66 list[i] = tempData;
67 }
68 return list;
69 }
70 }
71 }
比赛结果公布：
