首先感謝朋友們對(duì)第一篇文章的鼎力支持，感動(dòng)中....... 
今天說(shuō)的是選擇排序，包括“直接選擇排序”和“堆排序”。
話說(shuō)上次“冒泡排序”被快排虐了，而且“快排”贏得了內(nèi)庫(kù)的重用，眾兄弟自然眼紅，非要找快排一比高下。
這不今天就來(lái)了兩兄弟找快排算賬。
1.直接選擇排序：
先上圖：
說(shuō)實(shí)話，直接選擇排序最類似于人的本能思想，比如把大小不一的玩具讓三歲小毛孩對(duì)大小排個(gè)序，
那小孩首先會(huì)在這么多玩具中找到最小的放在第一位，然后找到次小的放在第二位，以此類推。。。。。。
，小孩子多聰明啊，這么小就知道了直接選擇排序。羨慕中........
對(duì)的，小孩子給我們上了一課，
第一步： 我們拿80作為參照物（base），在80后面找到一個(gè)最小數(shù)20,然后將80跟20交換。
第二步: 第一位數(shù)已經(jīng)是最小數(shù)字了，然后我們推進(jìn)一步在30后面找一位最小數(shù)，發(fā)現(xiàn)自己最小，不用交換。
第三步：........
最后我們排序完畢。大功告成。
既然是來(lái)挑戰(zhàn)的，那就5局3勝制。
復(fù)制代碼 代碼如下:
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++)
{
Listint> list = new Listint>();
//插入2w個(gè)隨機(jī)數(shù)到數(shù)組中
for (int j = 0; j 20000; j++)
{
Thread.Sleep(1);
list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));
}
Console.WriteLine("\n第" + i + "次比較：");
Stopwatch watch = new Stopwatch();
watch.Start();
var result = list.OrderBy(single => single).ToList();
watch.Stop();
Console.WriteLine("\n快速排序耗費(fèi)時(shí)間：" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù):" + string.Join(",", result.Take(10).ToList()));
watch.Start();
result = SelectionSort(list);
watch.Stop();
Console.WriteLine("\n直接選擇排序耗費(fèi)時(shí)間：" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù):" + string.Join(",", list.Take(10).ToList()));
}
}
//選擇排序
static Listint> SelectionSort(Listint> list)
{
//要遍歷的次數(shù)
for (int i = 0; i list.Count - 1; i++)
{
//假設(shè)tempIndex的下標(biāo)的值最小
int tempIndex = i;
for (int j = i + 1; j list.Count; j++)
{
//如果tempIndex下標(biāo)的值大于j下標(biāo)的值,則記錄較小值下標(biāo)j
if (list[tempIndex] > list[j])
tempIndex = j;
}
//最后將假想最小值跟真的最小值進(jìn)行交換
var tempData = list[tempIndex];
list[tempIndex] = list[i];
list[i] = tempData;
}
return list;
}
}
}
比賽結(jié)果公布：
堆排序：
要知道堆排序，首先要了解一下二叉樹(shù)的模型。
下圖就是一顆二叉樹(shù)，具體的情況我后續(xù)會(huì)分享的。
那么堆排序中有兩種情況（看上圖理解）：
大根堆： 就是說(shuō)父節(jié)點(diǎn)要比左右孩子都要大。
小根堆： 就是說(shuō)父節(jié)點(diǎn)要比左右孩子都要小。
那么要實(shí)現(xiàn)堆排序,必須要做兩件事情：
第一：構(gòu)建大根堆。
首先上圖：
首先這是一個(gè)無(wú)序的堆，那么我們?cè)鯓硬拍軜?gòu)建大根堆呢？
第一步： 首先我們發(fā)現(xiàn)，這個(gè)堆中有2個(gè)父節(jié)點(diǎn)(2,,3);
第二步： 比較2這個(gè)父節(jié)點(diǎn)的兩個(gè)孩子（4，5），發(fā)現(xiàn)5大。
第三步： 然后將較大的右孩子（5）跟父節(jié)點(diǎn)（2）進(jìn)行交換，至此3的左孩子堆構(gòu)建完畢，
如圖：
第四步： 比較第二個(gè)父節(jié)點(diǎn)（3）下面的左右孩子（5，1），發(fā)現(xiàn)左孩子5大。
第五步： 然后父節(jié)點(diǎn)（3）與左孩子（5）進(jìn)行交換，注意，交換后，堆可能會(huì)遭到破壞，
必須按照以上的步驟一，步驟二，步驟三進(jìn)行重新構(gòu)造堆。
最后構(gòu)造的堆如下:
第二：輸出大根堆。
至此，我們把大根堆構(gòu)造出來(lái)了，那怎么輸出呢？我們做大根堆的目的就是要找出最大值，
那么我們將堆頂（5）與堆尾（2）進(jìn)行交換，然后將（5）剔除根堆，由于堆頂現(xiàn)在是（2），
所以破壞了根堆，必須重新構(gòu)造，構(gòu)造完之后又會(huì)出現(xiàn)最大值，再次交換和剔除，最后也就是俺們
要的效果了，
發(fā)現(xiàn)自己兄弟被別人狂毆，
，堆排序再也坐不住了，決定要和快排干一場(chǎng)。
同樣，快排也不甘示弱，誰(shuí)怕誰(shuí)？
復(fù)制代碼 代碼如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
namespace HeapSort
{
public class Program
{
static void Main(string[] args)
{
//5次比較
for (int j = 1; j = 5; j++)
{
Listint> list = new Listint>();
//插入2w個(gè)數(shù)字
for (int i = 0; i 20000; i++)
{
Thread.Sleep(1);
list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
}
Console.WriteLine("\n第" + j + "次比較：");
Stopwatch watch = new Stopwatch();
watch.Start();
var result = list.OrderBy(single => single).ToList();
watch.Stop();
Console.WriteLine("\n快速排序耗費(fèi)時(shí)間:" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù)" + string.Join(",", result.Take(10).ToList()));
watch = new Stopwatch();
watch.Start();
HeapSort(list);
watch.Stop();
Console.WriteLine("\n堆排序耗費(fèi)時(shí)間:" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù)" + string.Join(",", list.Take(10).ToList()));
}
}
///summary>
/// 構(gòu)建堆
////summary>
///param name="list">待排序的集合/param>
///param name="parent">父節(jié)點(diǎn)/param>
///param name="length">輸出根堆時(shí)剔除最大值使用/param>
static void HeapAdjust(Listint> list, int parent, int length)
{
//temp保存當(dāng)前父節(jié)點(diǎn)
int temp = list[parent];
//得到左孩子(這可是二叉樹(shù)的定義，大家看圖也可知道)
int child = 2 * parent + 1;
while (child length)
{
//如果parent有右孩子，則要判斷左孩子是否小于右孩子
if (child + 1 length list[child] list[child + 1])
child++;
//父親節(jié)點(diǎn)大于子節(jié)點(diǎn)，就不用做交換
if (temp >= list[child])
break;
//將較大子節(jié)點(diǎn)的值賦給父親節(jié)點(diǎn)
list[parent] = list[child];
//然后將子節(jié)點(diǎn)做為父親節(jié)點(diǎn)，已防止是否破壞根堆時(shí)重新構(gòu)造
parent = child;
//找到該父親節(jié)點(diǎn)較小的左孩子節(jié)點(diǎn)
child = 2 * parent + 1;
}
//最后將temp值賦給較大的子節(jié)點(diǎn)，以形成兩值交換
list[parent] = temp;
}
///summary>
/// 堆排序
////summary>
///param name="list">/param>
public static void HeapSort(Listint> list)
{
//list.Count/2-1:就是堆中父節(jié)點(diǎn)的個(gè)數(shù)
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
HeapAdjust(list, i, list.Count);
}
//最后輸出堆元素
for (int i = list.Count - 1; i > 0; i--)
{
//堆頂與當(dāng)前堆的第i個(gè)元素進(jìn)行值對(duì)調(diào)
int temp = list[0];
list[0] = list[i];
list[i] = temp;
//因?yàn)閮芍到粨Q，可能破壞根堆，所以必須重新構(gòu)造
HeapAdjust(list, 0, i);
}
}
}
}
結(jié)果公布：
堆排序此時(shí)心里很尷尬，雙雙被KO，心里想，一定要撈回面子，一定要贏，
于是堆排序提出了求“前K大問(wèn)題”。（就是在海量數(shù)據(jù)中找出前幾大的數(shù)據(jù)），
快排一口答應(yīng)，小意思，沒(méi)問(wèn)題。
雙方商定，在2w隨機(jī)數(shù)中找出前10大的數(shù)：
復(fù)制代碼 代碼如下:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
using System.Diagnostics;
namespace QuickSort
{
public class Program
{
static void Main(string[] args)
{
//5此比較
for (int j = 1; j = 5; j++)
{
Listint> list = new Listint>();
for (int i = 0; i 20000; i++)
{
Thread.Sleep(1);
list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));
}
Console.WriteLine("\n第" + j + "次比較：");
Stopwatch watch = new Stopwatch();
watch.Start();
var result = list.OrderByDescending(single => single).Take(10).ToList();
watch.Stop();
Console.WriteLine("\n快速排序求前K大耗費(fèi)時(shí)間:" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù):" + string.Join(",", result.Take(10).ToList()));
watch = new Stopwatch();
watch.Start();
result = HeapSort(list, 10);
watch.Stop();
Console.WriteLine("\n堆排序求前K大耗費(fèi)時(shí)間：" + watch.ElapsedMilliseconds);
Console.WriteLine("輸出前十個(gè)數(shù):" + string.Join(",", list.Take(10).ToList()));
}
}
///summary>
/// 構(gòu)建堆
////summary>
///param name="list">待排序的集合/param>
///param name="parent">父節(jié)點(diǎn)/param>
///param name="length">輸出根堆時(shí)剔除最大值使用/param>
static void HeapAdjust(Listint> list, int parent, int length)
{
//temp保存當(dāng)前父節(jié)點(diǎn)
int temp = list[parent];
//得到左孩子(這可是二叉樹(shù)的定義哇)
int child = 2 * parent + 1;
while (child length)
{
//如果parent有右孩子，則要判斷左孩子是否小于右孩子
if (child + 1 length list[child] list[child + 1])
child++;
//父節(jié)點(diǎn)大于子節(jié)點(diǎn)，不用做交換
if (temp >= list[child])
break;
//將較大子節(jié)點(diǎn)的值賦給父親節(jié)點(diǎn)
list[parent] = list[child];
//然后將子節(jié)點(diǎn)做為父親節(jié)點(diǎn)，已防止是否破壞根堆時(shí)重新構(gòu)造
parent = child;
//找到該父節(jié)點(diǎn)左孩子節(jié)點(diǎn)
child = 2 * parent + 1;
}
//最后將temp值賦給較大的子節(jié)點(diǎn)，以形成兩值交換
list[parent] = temp;
}
///summary>
/// 堆排序
////summary>
///param name="list">待排序的集合/param>
///param name="top">前K大/param>
///returns>/returns>
public static Listint> HeapSort(Listint> list, int top)
{
Listint> topNode = new Listint>();
//list.Count/2-1:就是堆中非葉子節(jié)點(diǎn)的個(gè)數(shù)
for (int i = list.Count / 2 - 1; i >= 0; i--)
{
HeapAdjust(list, i, list.Count);
}
//最后輸出堆元素（求前K大）
for (int i = list.Count - 1; i >= list.Count - top; i--)
{
//堆頂與當(dāng)前堆的第i個(gè)元素進(jìn)行值對(duì)調(diào)
int temp = list[0];
list[0] = list[i];
list[i] = temp;
//最大值加入集合
topNode.Add(temp);
//因?yàn)轫樞虮淮騺y，必須重新構(gòu)造堆
HeapAdjust(list, 0, i);
}
return topNode;
}
}
}
求前K大的輸出結(jié)果：
最后堆排序趕緊拉著直接選擇排序一路小跑了，因?yàn)榍笄癒大問(wèn)題已經(jīng)不是他原本來(lái)的目的。
ps： 直接選擇排序的時(shí)間復(fù)雜度為：O(n^2)
堆排序的時(shí)間復(fù)雜度：O(NlogN)
您可能感興趣的文章:- 算法系列15天速成 第十四天 圖【上】
- 算法系列15天速成——第十三天 樹(shù)操作【下】
- 算法系列15天速成 第十二天 樹(shù)操作【中】
- 算法系列15天速成 第十一天 樹(shù)操作（上）
- 算法系列15天速成 第十天 棧
- 算法系列15天速成 第八天 線性表【下】
- 算法系列15天速成 第九天 隊(duì)列
- 算法系列15天速成 第七天 線性表【上】
- 算法系列15天速成 第六天 五大經(jīng)典查找【下】
- 算法系列15天速成 第五天 五大經(jīng)典查找【中】
- 算法系列15天速成 第四天 五大經(jīng)典查找【上】
- 算法系列15天速成 第三天 七大經(jīng)典排序【下】
- 算法系列15天速成 第一天 七大經(jīng)典排序【上】
- 算法系列15天速成——第十五天 圖【下】（大結(jié)局）
