算法速成（二）七大经典排序之选择排序

算法速成（二）七大经典排序之选择排序2014-04-28今天说的是选择排序，包括“直接选择排序”和“堆排序”。

话说上次“冒泡排序”被快排虐了，而且“快排”赢得了内库的重用，众兄弟自然眼红，非要找快排一比高下。

这不今天就来了两兄弟找快排算账。

1.直接选择排序：

先上图：

说实话，直接选择排序最类似于人的本能思想，比如把大小不一的玩具让三岁小毛孩对大小排个序，

那小孩首先会在这么多玩具中找到最小的放在第一位，然后找到次小的放在第二位，以此类推。。。。。。

，小孩子多聪明啊，这么小就知道了直接选择排序。羡慕中........

对的，小孩子给我们上了一课，

第一步：我们拿80作为参照物（base），在80后面找到一个最小数20,然后将80跟20交换。

第二步: 第一位数已经是最小数字了，然后我们推进一步在30后面找一位最小数，发现自己最小，不用交换。

第三步：........

最后我们排序完毕。大功告成。

既然是来挑战的，那就5局3胜制。

using System;using System.Collections.Generic;using System.Linq;using System.Text;using System.Threading;using System.Diagnostics;namespace SelectionSort{public class Program{static void Main（string[] args）{//5次比较for （int i = 1; i <= 5; i++）{List<int> list = new List<int>（）;//插入2w个随机数到数组中for （int j = 0; j < 20000; j++）{Thread.Sleep（1）;list.Add（new Random（（int）DateTime.Now.Ticks）.Next（1000, 1000000））;}Console.WriteLine（"
第" + i + "次比较："）;Stopwatch watch = new Stopwatch（）;watch.Start（）;var result = list.OrderBy（single => single）.ToList（）;watch.Stop（）;Console.WriteLine（"
快速排序耗费时间：" + watch.ElapsedMilliseconds）;Console.WriteLine（"输出前十个数:" + string.Join（",", result.Take（10）.ToList（）））;watch.Start（）;result = SelectionSort（list）;watch.Stop（）;Console.WriteLine（"
直接选择排序耗费时间：" + watch.ElapsedMilliseconds）;Console.WriteLine（"输出前十个数:" + string.Join（",", list.Take（10）.ToList（）））;}}//选择排序static List<int> SelectionSort（List<int> list）{//要遍历的次数for （int i = 0; i < list.Count - 1; i++）{//假设tempIndex的下标的值最小int tempIndex = i;for （int j = i + 1; j < list.Count; j++）{//如果tempIndex下标的值大于j下标的值,则记录较小值下标jif （list[tempIndex] > list[j]）tempIndex = j;}//最后将假想最小值跟真的最小值进行交换var tempData = list[tempIndex];list[tempIndex] = list[i];list[i] = tempData;}return list;}}}