手记

算法系列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 }

比赛结果公布:

 

堆排序:

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

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

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

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

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

 

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

   第一:构建大根堆。

           首先上图:

           

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

     第一步: 首先我们发现,这个堆中有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 }

结果公布:

 

堆排序此时心里很尴尬,双双被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)

2人推荐
随时随地看视频
慕课网APP