频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
算法系列15天速成——第二天 七大经典排序【中】
2011-11-26 12:47:33           
收藏   我要投稿

 

今天说的是选择排序,包括“直接选择排序”和“堆排序”。

 

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

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

 

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 }

 

 

 

比赛结果公布:

\

 

堆排序:

要知道堆排序,首先要了解一下二叉树的模型。

下图就是一颗二叉树,具体的情况我后续会分享的。

\

那么堆排序中有两种情况(看上图理解):

    大根堆:  就是说父节点要比左右孩子都要大。

    小根堆:  就是说父节点要比左右孩子都要小。

 

那么要实现堆排序,必须要做两件事情:

   第一:构建大根堆。

           首先上图:

           \

首先这是一个无序的堆,那么我们怎样才能构建大根堆呢?

     第一步: 首先我们发现,这个堆中有2个父节点(2,,3);

     第二步: 比较2这个父节点的两个孩子(4,5),发现5大。

     第三步: 然后将较大的右孩子(5)跟父节点(2)进行交换,至此3的左孩子堆构建完毕,

                 如图:

                         \

     第四步: 比较第二个父节点(3)下面的左右孩子(5,1),发现左孩子5大。

     第五步: 然后父节点(3)与左孩子(5)进行交换,注意,交换后,堆可能会遭到破坏,

                 必须按照以上的步骤一,步骤二,步骤三进行重新构造堆。

           

最后构造的堆如下:

                 

\

 

   第二:输出大根堆。

 

  至此,我们把大根堆构造出来了,那怎么输出呢?我们做大根堆的目的就是要找出最大值,

 

         那么我们将堆顶(5)与堆尾(2)进行交换,然后将(5)剔除根堆,由于堆顶现在是(2),

 

         所以破坏了根堆,必须重新构造,构造完之后又会出现最大值,再次交换和剔除,最后也就是俺们

 

         要的效果了,

 

 

 

 

 

发现自己兄弟被别人狂殴,,堆排序再也坐不住了,决定要和快排干一场。

 

同样,快排也不甘示弱,谁怕谁?

 

 

 

  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 HeapSort

  9 {

 10     public class Program

 11     {

 12         static void Main(string[] args)

 13         {

 14             //5次比较

 15             for (int j = 1; j <= 5; j++)

 16             {

 17                 List<int> list = new List<int>();

 18

 19                 //插入2w个数字

 20                 for (int i = 0; i < 20000; i++)

 21                 {

 22                     Thread.Sleep(1);

 23                     list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

 24                 }

 25

 26                 Console.WriteLine("\n第" + j + "次比较:");

 27

 28                 Stopwatch watch = new Stopwatch();

 29                 watch.Start();

 30                 var result = list.OrderBy(single => single).ToList();

 31                 watch.Stop();

 32                 Console.WriteLine("\n快速排序耗费时间:" + watch.ElapsedMilliseconds);

 33                 Console.WriteLine("输出前十个数" + string.Join(",", result.Take(10).ToList()));

 34

 35                 watch = new Stopwatch();

 36                 watch.Start();

 37                 HeapSort(list);

 38                 watch.Stop();

 39                 Console.WriteLine("\n堆排序耗费时间:" + watch.ElapsedMilliseconds);

 40                 Console.WriteLine("输出前十个数" + string.Join(",", list.Take(10).ToList()));

 41             }

 42

 43         }

 44

 45         ///<summary>

 46 /// 构建堆

 47 ///</summary>

 48 ///<param name="list">待排序的集合</param>

 49 ///<param name="parent">父节点</param>

 50 ///<param name="length">输出根堆时剔除最大值使用</param>

 51         static void HeapAdjust(List<int> list, int parent, int length)

 52         {

 53             //temp保存当前父节点

 54             int temp = list[parent];

 55

 56             //得到左孩子(这可是二叉树的定义,大家看图也可知道)

 57             int child = 2 * parent + 1;

 58

 59             while (child < length)

 60             {

 61                 //如果parent有右孩子,则要判断左孩子是否小于右孩子

 62                 if (child + 1 < length && list[child] < list[child + 1])

 63                     child++;

 64

 65                 //父亲节点大于子节点,就不用做交换

 66                 if (temp >= list[child])

 67                     break;

 68

 69                 //将较大子节点的值赋给父亲节点

 70                 list[parent] = list[child];

 71

 72                 //然后将子节点做为父亲节点,已防止是否破坏根堆时重新构造

 73                 parent = child;

 74

 75                 //找到该父亲节点较小的左孩子节点

 76                 child = 2 * parent + 1;

 77             }

 78             //最后将temp值赋给较大的子节点,以形成两值交换

 79             list[parent] = temp;

 80         }

 81

 82         ///<summary>

 83 /// 堆排序

 84 ///</summary>

 85 ///<param name="list"></param>

 86         public static void HeapSort(List<int> list)

 87         {

 88             //list.Count/2-1:就是堆中父节点的个数

 89             for (int i = list.Count / 2 - 1; i >= 0; i--)

 90             {

 91                 HeapAdjust(list, i, list.Count);

 92             }

 93

 94             //最后输出堆元素

 95             for (int i = list.Count - 1; i > 0; i--)

 96             {

 97                 //堆顶与当前堆的第i个元素进行值对调

 98                 int temp = list[0];

 99                 list[0] = list[i];

100                 list[i] = temp;

101

102                 //因为两值交换,可能破坏根堆,所以必须重新构造

103                 HeapAdjust(list, 0, i);

104             }

105         }

106     }

107 }           www.2cto.com

结果公布:

\

 

堆排序此时心里很尴尬,双双被KO,心里想,一定要捞回面子,一定要赢,

 

于是堆排序提出了求“前K大问题”。(就是在海量数据中找出前几大的数据),

快排一口答应,小意思,没问题。

双方商定,在2w随机数中找出前10大的数:

 

 

  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 QuickSort

  9 {

 10     public class Program

 11     {

 12         static void Main(string[] args)

 13         {

 14             //5此比较

 15             for (int j = 1; j <= 5; j++)

 16             {

 17                 List<int> list = new List<int>();

 18

 19                 for (int i = 0; i < 20000; i++)

 20                 {

 21                     Thread.Sleep(1);

 22                     list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

 23                 }

 24

 25                 Console.WriteLine("\n第" + j + "次比较:");

 26

 27                 Stopwatch watch = new Stopwatch();

 28                 watch.Start();

 29                 var result = list.OrderByDescending(single => single).Take(10).ToList();

 30                 watch.Stop();

 31                 Console.WriteLine("\n快速排序求前K大耗费时间:" + watch.ElapsedMilliseconds);

 32                 Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

 33

 34                 watch = new Stopwatch();

 35                 watch.Start();

 36                 result = HeapSort(list, 10);

 37                 watch.Stop();

 38                 Console.WriteLine("\n堆排序求前K大耗费时间:" + watch.ElapsedMilliseconds);

 39                 Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

 40             }

 41

 42         }

 43

 44         ///<summary>

 45 /// 构建堆

 46 ///</summary>

 47 ///<param name="list">待排序的集合</param>

 48 ///<param name="parent">父节点</param>

 49 ///<param name="length">输出根堆时剔除最大值使用</param>

 50         static void HeapAdjust(List<int> list, int parent, int length)

 51         {

 52             //temp保存当前父节点

 53             int temp = list[parent];

 54

 55             //得到左孩子(这可是二叉树的定义哇)

 56             int child = 2 * parent + 1;

 57

 58             while (child < length)

 59             {

 60                 //如果parent有右孩子,则要判断左孩子是否小于右孩子

 61                 if (child + 1 < length && list[child] < list[child + 1])

 62                     child++;

 63

 64                 //父节点大于子节点,不用做交换

 65                 if (temp >= list[child])

 66                     break;

 67

 68                 //将较大子节点的值赋给父亲节点

 69                 list[parent] = list[child];

 70

 71                 //然后将子节点做为父亲节点,已防止是否破坏根堆时重新构造

 72                 parent = child;

 73

 74                 //找到该父节点左孩子节点

 75                 child = 2 * parent + 1;

 76             }

 77             //最后将temp值赋给较大的子节点,以形成两值交换

 78             list[parent] = temp;

 79         }

 80

 81         ///<summary>

 82 /// 堆排序

 83 ///</summary>

 84 ///<param name="list">待排序的集合</param>

 85 ///<param name="top">前K大</param>

 86 ///<returns></returns>

 87         public static List<int> HeapSort(List<int> list, int top)

 88         {

 89             List<int> topNode = new List<int>();

 90

 91             //list.Count/2-1:就是堆中非叶子节点的个数

 92             for (int i = list.Count / 2 - 1; i >= 0; i--)

 93             {

 94                 HeapAdjust(list, i, list.Count);

 95             }

 96

 97             //最后输出堆元素(求前K大)

 98             for (int i = list.Count - 1; i >= list.Count - top; i--)

 99             {

100                 //堆顶与当前堆的第i个元素进行值对调

101                 int temp = list[0];

102                 list[0] = list[i];

103                 list[i] = temp;

104

105                 //最大值加入集合

106                 topNode.Add(temp);

107

108                 //因为顺序被打乱,必须重新构造堆

109                 HeapAdjust(list, 0, i);

110             }

111             return topNode;

112         }

113     }

114 }

 

求前K大的输出结果:

 

\

 

最后堆排序赶紧拉着直接选择排序一路小跑了,因为求前K大问题已经不是他原本来的目的。

 

ps: 直接选择排序的时间复杂度为:O(n^2)

       堆排序的时间复杂度:O(NlogN)

 


作者 huangxincheng520

点击复制链接 与好友分享!回本站首页
上一篇:算法系列15天速成——第一天 七大经典排序【上】
下一篇:算法系列15天速成——第二天 七大经典排序【中】
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站