|
首先感謝朋友們對第一篇文章的鼎力支持，感動中....... 
今天說的是選擇排序，包括“直接選擇排序”和“堆排序”。
話說上次“冒泡排序”被快排虐了，而且“快排”贏得了內(nèi)庫的重用，眾兄弟自然眼紅，非要找快排一比高下。
這不今天就來了兩兄弟找快排算賬。
1.直接選擇排序：
先上圖：
說實話，直接選擇排序最類似于人的本能思想，比如把大小不一的玩具讓三歲小毛孩對大小排個序，
那小孩首先會在這么多玩具中找到最小的放在第一位，然后找到次小的放在第二位，以此類推。。。。。。
 ，小孩子多聰明啊，這么小就知道了直接選擇排序。羨慕中........
對的，小孩子給我們上了一課，
第一步： 我們拿80作為參照物（base），在80后面找到一個最小數(shù)20,然后將80跟20交換。
第二步: 第一位數(shù)已經(jīng)是最小數(shù)字了，然后我們推進一步在30后面找一位最小數(shù)，發(fā)現(xiàn)自己最小，不用交換。
第三步：........
最后我們排序完畢。大功告成。
既然是來挑戰(zhàn)的，那就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個隨機數(shù)到數(shù)組中
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("輸出前十個數(shù):" + 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("輸出前十個數(shù):" + string.Join(",", list.Take(10).ToList()));
43
44 }
45 }
46
47 //選擇排序
48 static List<int> SelectionSort(List<int> list)
49 {
50 //要遍歷的次數(shù)
51 for (int i = 0; i < list.Count - 1; i++)
52 {
53 //假設(shè)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 }
比賽結(jié)果公布：
堆排序：
要知道堆排序，首先要了解一下二叉樹的模型。
下圖就是一顆二叉樹，具體的情況我后續(xù)會分享的。
那么堆排序中有兩種情況（看上圖理解）：
大根堆： 就是說父節(jié)點要比左右孩子都要大。
小根堆： 就是說父節(jié)點要比左右孩子都要小。
那么要實現(xiàn)堆排序,必須要做兩件事情：
第一：構(gòu)建大根堆。
首先上圖：
首先這是一個無序的堆，那么我們怎樣才能構(gòu)建大根堆呢？
第一步： 首先我們發(fā)現(xiàn)，這個堆中有2個父節(jié)點(2,,3);
第二步： 比較2這個父節(jié)點的兩個孩子（4，5），發(fā)現(xiàn)5大。
第三步： 然后將較大的右孩子（5）跟父節(jié)點（2）進行交換，至此3的左孩子堆構(gòu)建完畢，
如圖：
第四步： 比較第二個父節(jié)點（3）下面的左右孩子（5，1），發(fā)現(xiàn)左孩子5大。
第五步： 然后父節(jié)點（3）與左孩子（5）進行交換，注意，交換后，堆可能會遭到破壞，
必須按照以上的步驟一，步驟二，步驟三進行重新構(gòu)造堆。
最后構(gòu)造的堆如下:
第二：輸出大根堆。
至此，我們把大根堆構(gòu)造出來了，那怎么輸出呢？我們做大根堆的目的就是要找出最大值，
那么我們將堆頂（5）與堆尾（2）進行交換，然后將（5）剔除根堆，由于堆頂現(xiàn)在是（2），
所以破壞了根堆，必須重新構(gòu)造，構(gòu)造完之后又會出現(xiàn)最大值，再次交換和剔除，最后也就是俺們
要的效果了，
發(fā)現(xiàn)自己兄弟被別人狂毆，，堆排序再也坐不住了，決定要和快排干一場。
同樣，快排也不甘示弱，誰怕誰？
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個數(shù)字
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("輸出前十個數(shù)" + 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("輸出前十個數(shù)" + string.Join(",", list.Take(10).ToList()));
41 }
42
43 }
44
45 ///<summary>
46 /// 構(gòu)建堆
47 ///</summary>
48 ///<param name="list">待排序的集合</param>
49 ///<param name="parent">父節(jié)點</param>
50 ///<param name="length">輸出根堆時剔除最大值使用</param>
51 static void HeapAdjust(List<int> list, int parent, int length)
52 {
53 //temp保存當(dāng)前父節(jié)點
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 //父親節(jié)點大于子節(jié)點，就不用做交換
66 if (temp >= list[child])
67 break;
68
69 //將較大子節(jié)點的值賦給父親節(jié)點
70 list[parent] = list[child];
71
72 //然后將子節(jié)點做為父親節(jié)點，已防止是否破壞根堆時重新構(gòu)造
73 parent = child;
74
75 //找到該父親節(jié)點較小的左孩子節(jié)點
76 child = 2 * parent + 1;
77 }
78 //最后將temp值賦給較大的子節(jié)點，以形成兩值交換
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:就是堆中父節(jié)點的個數(shù)
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 //堆頂與當(dāng)前堆的第i個元素進行值對調(diào)
98 int temp = list[0];
99 list[0] = list[i];
100 list[i] = temp;
101
102 //因為兩值交換，可能破壞根堆，所以必須重新構(gòu)造
103 HeapAdjust(list, 0, i);
104 }
105 }
106 }
107 }
結(jié)果公布：
堆排序此時心里很尷尬，雙雙被KO，心里想，一定要撈回面子，一定要贏，
于是堆排序提出了求“前K大問題”。（就是在海量數(shù)據(jù)中找出前幾大的數(shù)據(jù)），
快排一口答應(yīng)，小意思，沒問題。
雙方商定，在2w隨機數(shù)中找出前10大的數(shù)：
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("輸出前十個數(shù):" + 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("輸出前十個數(shù):" + string.Join(",", list.Take(10).ToList()));
40 }
41
42 }
43
44 ///<summary>
45 /// 構(gòu)建堆
46 ///</summary>
47 ///<param name="list">待排序的集合</param>
48 ///<param name="parent">父節(jié)點</param>
49 ///<param name="length">輸出根堆時剔除最大值使用</param>
50 static void HeapAdjust(List<int> list, int parent, int length)
51 {
52 //temp保存當(dāng)前父節(jié)點
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 //父節(jié)點大于子節(jié)點，不用做交換
65 if (temp >= list[child])
66 break;
67
68 //將較大子節(jié)點的值賦給父親節(jié)點
69 list[parent] = list[child];
70
71 //然后將子節(jié)點做為父親節(jié)點，已防止是否破壞根堆時重新構(gòu)造
72 parent = child;
73
74 //找到該父節(jié)點左孩子節(jié)點
75 child = 2 * parent + 1;
76 }
77 //最后將temp值賦給較大的子節(jié)點，以形成兩值交換
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:就是堆中非葉子節(jié)點的個數(shù)
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 //堆頂與當(dāng)前堆的第i個元素進行值對調(diào)
101 int temp = list[0];
102 list[0] = list[i];
103 list[i] = temp;
104
105 //最大值加入集合
106 topNode.Add(temp);
107
108 //因為順序被打亂，必須重新構(gòu)造堆
109 HeapAdjust(list, 0, i);
110 }
111 return topNode;
112 }
113 }
114 }
求前K大的輸出結(jié)果：
最后堆排序趕緊拉著直接選擇排序一路小跑了，因為求前K大問題已經(jīng)不是他原本來的目的。
ps： 直接選擇排序的時間復(fù)雜度為：O(n^2)
堆排序的時間復(fù)雜度：O(NlogN)
|
