今天我們的目標(biāo)是選擇排序：簡單選擇排序與堆排序。兩者排序的過程都在于每次選擇一個(gè)最大值或者最小值放到合適的位置，因此都屬于選擇排序的范疇。區(qū)別在于：簡單選擇排序暴力選擇出最大最小值，而堆排序合理的利用完全二叉樹的特性使得算法的時(shí)間復(fù)雜度大大降低。接下來我們詳細(xì)講解兩種排序：
簡單選擇排序：
思想：每次從一組數(shù)據(jù)中，找到最小的，然后放置在隊(duì)列前面（當(dāng)然也可以每次找到最大的，甚至有一些優(yōu)化，每次可以同時(shí)找到最大值和最小值進(jìn)行排序，我們這里采用找最小值）。可以看一下動(dòng)畫演示（動(dòng)畫是用unity制作的）：
接下來著手寫代碼：
public static void SelectionSort(int[] arr)
{
int length = arr.Length;
if (length < 2)
{
return;
}
for (int i = 0; i < length - 1; i++)
{
int min = arr[i];
int minIndex = i;
//找到數(shù)列中的最小值
for (int j = i + 1; j < length; j++)
{
if (min > arr[j])
{
min = arr[j];
minIndex = j;
}
}
//與其適應(yīng)的位置交換
if (minIndex != i)
{
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
時(shí)間復(fù)雜度：
我們主要看兩層循環(huán)，第一層執(zhí)行次數(shù)為（length-1)，第二層最小為1，最大為（length-1)。第1次外循環(huán)內(nèi)循環(huán)次數(shù)（length-1）次，第2次外循環(huán)內(nèi)循環(huán)次數(shù)（length-2）…第（length-1）次外循環(huán)內(nèi)循環(huán)1次，相加就是(length-1)+(length-2)…+1，即（length）x（length -1）/2，用大O法，通常我們只關(guān)心數(shù)量級(jí)，而不關(guān)心系數(shù)，所以其復(fù)雜度就是：O（n2）。
空間復(fù)雜度： O(1)。
穩(wěn)定性：這里要注意一下，簡單選擇排序是一種不穩(wěn)定排序，這是因?yàn)樵谶x擇了最小值之后，最小值要與數(shù)列頭部的值進(jìn)行交換，這樣會(huì)導(dǎo)致打亂相同數(shù)值序列，比如（4，4，2，1）的序列，第一次最小值為1，與頭部的4交換位置之后，導(dǎo)致兩個(gè)4的前后順序被打亂了，因此是不穩(wěn)定排序。
堆排序：
堆排序首先是構(gòu)建最大堆或最小堆。最大堆是用來正序排序，最小堆是用來倒序排序。
最大堆是指二叉樹中每個(gè)結(jié)點(diǎn)的值都比其左右子結(jié)點(diǎn)的值大。同理最小堆是指二叉樹中每個(gè)結(jié)點(diǎn)的值都比其左右子結(jié)點(diǎn)的值小。
對于二叉樹不了解，在這里可以只有一個(gè)印象就可以。二叉樹就是一個(gè)結(jié)點(diǎn)最多只有兩個(gè)左右子結(jié)點(diǎn)。至于什么是完全二叉樹，這里就不在過多解釋，以后有機(jī)會(huì)寫數(shù)據(jù)結(jié)構(gòu)的時(shí)候，會(huì)著重解釋，但是有一點(diǎn)要知道，數(shù)列從上往下，從左往右，按照只有一個(gè)根結(jié)點(diǎn)，且每個(gè)結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn)這樣構(gòu)建二叉樹，那么他就是一顆完全二叉樹。
下面我用一張圖，來表示上面的概念，并加深印象。
完全二叉樹：
可以發(fā)現(xiàn)其實(shí)每個(gè)結(jié)點(diǎn)的下標(biāo)和其左右子結(jié)點(diǎn)的下標(biāo)是有一定關(guān)系的，即結(jié)點(diǎn)下標(biāo)為n，左子結(jié)點(diǎn)下標(biāo)為：2n+1，右子結(jié)點(diǎn)的下標(biāo)為：2n+2。
最大堆：
上圖為第一次構(gòu)建最大堆的結(jié)果
可以看出因?yàn)楦Y(jié)點(diǎn)要比左右子結(jié)點(diǎn)數(shù)值大，而且其左右子結(jié)點(diǎn)要比其孫子結(jié)點(diǎn)數(shù)值大，以此類推，此時(shí)的根結(jié)點(diǎn)即為數(shù)列的最大值。
那么我們?nèi)绾伟岩粋€(gè)無序構(gòu)建成一個(gè)最大堆。首先看最大堆的最大特點(diǎn)就是：父結(jié)點(diǎn)的數(shù)值一定比左右結(jié)點(diǎn)數(shù)值大，我們依照這個(gè)規(guī)則不斷的調(diào)整結(jié)點(diǎn)使其滿足條件即可。
再仔細(xì)觀察堆我們發(fā)現(xiàn)，由一半以上的結(jié)點(diǎn)是沒有孩子結(jié)點(diǎn)的，這部分結(jié)點(diǎn)就稱為葉子結(jié)點(diǎn)，那么也就是說，這部分結(jié)點(diǎn)是不需要向下調(diào)整的。我們選擇從(length/2)-1的下標(biāo)開始依次從0下標(biāo)的方向進(jìn)行調(diào)整。每次調(diào)整之后，調(diào)整的結(jié)點(diǎn)還要繼續(xù)比較他的子結(jié)點(diǎn)看看是否仍然滿足最大堆特點(diǎn)，一直調(diào)整到葉子結(jié)點(diǎn)。這樣做的目的就是使數(shù)列的大值向上浮，小值向下沉。直到下標(biāo)0結(jié)點(diǎn)（根結(jié)點(diǎn)）調(diào)整完成，此時(shí)就是一個(gè)最大堆。
此時(shí)根結(jié)點(diǎn)是一個(gè)最大值，我們把最大值排在無序數(shù)列最后，即把最大值與隊(duì)尾交換位置。此時(shí)我們發(fā)現(xiàn)除了根結(jié)點(diǎn)，其他結(jié)點(diǎn)仍然是符合最大堆特點(diǎn)的（注意，從這個(gè)位置往后，我們講述的情況都是排除了最后一個(gè)數(shù)，因?yàn)樗呀?jīng)排好了位置）。這時(shí)我們只用調(diào)整根結(jié)點(diǎn)就可以了，調(diào)整之后，就得到了數(shù)列的第二個(gè)最大值。依次調(diào)整，直到數(shù)列排好即可。
思路：演示動(dòng)畫如下：
代碼如下：
public static void HeapSort(int[] arr)
{
int length = arr.Length;
if (length < 2)
{
return;
}
//初次構(gòu)建最大堆。從后往前第一個(gè)非葉子結(jié)點(diǎn)開始調(diào)整。
for (int i = length / 2 - 1; i >= 0; i--)
{
AdjustHeap(arr, i, length);
}
//將堆頂最大值移動(dòng)到數(shù)組末端，再次從根結(jié)點(diǎn)開始調(diào)整構(gòu)建最大堆。
//注意長度要-1，因?yàn)殛?duì)尾的元素已經(jīng)是排好序的。
for (int i = 0; i < length -1; i++)
{
Swap(arr, 0, length - 1 - i);
AdjustHeap(arr, 0, length - i - 1);
}
}
/// <summary>
/// 構(gòu)建最大堆
/// </summary>
/// <param name="arr">需要構(gòu)建的數(shù)組</param>
/// <param name="index">需要開始調(diào)整的結(jié)點(diǎn)下標(biāo)</param>
/// <param name="length">需要構(gòu)建的數(shù)組長度</param>
private static void AdjustHeap(int[] arr, int index, int length)
{
int leftIndex = index * 2 + 1; //左孩子結(jié)點(diǎn)下標(biāo)
int rightIndex = index * 2 + 2; //右孩子結(jié)點(diǎn)下標(biāo)
//如果左孩子下標(biāo)大于等于數(shù)組長，則說明其為葉子結(jié)點(diǎn)，不需要調(diào)整
if (leftIndex >= length)
{
return;
}
//找到左右結(jié)點(diǎn)最大值的下標(biāo)
int maxIndex = leftIndex;
if (rightIndex < length)
{
if (arr[leftIndex] < arr[rightIndex])
{
maxIndex = rightIndex;
}
}
//如果孩子結(jié)點(diǎn)的值要大于父結(jié)點(diǎn)，則交換兩個(gè)結(jié)點(diǎn)的值，
//并且從交換后的子結(jié)點(diǎn)繼續(xù)向下調(diào)整
if (arr[maxIndex] > arr[index])
{
Swap(arr, maxIndex, index);
AdjustHeap(arr, maxIndex, length);
}
}
private static void Swap(int[] arr, int index1, int index2)
{
int length = arr.Length;
if (index1 >= length || index2 >= length)
{
return;
}
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
時(shí)間復(fù)雜度：
首先我們來看函數(shù)的遞歸算法，了解到算法是根據(jù)二叉樹依次向下分支進(jìn)行遍歷，那么他的運(yùn)行次數(shù)跟樹的深度有關(guān)，比如index下標(biāo)結(jié)點(diǎn)的調(diào)整則最多需要：最深葉子結(jié)點(diǎn)的深度減去index下標(biāo)結(jié)點(diǎn)的深度值即可。深度（用h表示，此處根結(jié)點(diǎn)的深度按0處理，樹的最大深度位log2n）的計(jì)算可以自行查閱資料。另外完全二叉樹為相同深度的結(jié)點(diǎn)個(gè)數(shù)** 2h-1**。
然后我們看初次構(gòu)建最大堆，總共有一半的結(jié)點(diǎn)數(shù)需要調(diào)整，其中調(diào)整1次的結(jié)點(diǎn)為2h-1，調(diào)整2次的結(jié)點(diǎn)為2h-2，…，調(diào)整h次的結(jié)點(diǎn)為20。每調(diào)整一次的交換次數(shù)為2（左右結(jié)點(diǎn)比較，然后和父類結(jié)點(diǎn)比較）。
所以總的次數(shù)為：
????2x2h-1+4x2h-2+…+2xhx20
運(yùn)用數(shù)學(xué)歸納法：
????212h-1+222h-2+…+2h20 =S
即
????1x2h+2x2h-1+…+hx21 =S ????公式1；
兩邊乘以2：
????2h+1+2X2h+…+hx22 =2S ????公式2；
公式2-公式1：
????2h+1+2h+…+ 22- hx21 =S????公式3；
兩邊乘以2：
????2h+2+2h+1+…+ 23- hx22 =2S ????公式4；
公式4-公式3：
????2h+2- hx22-22+ hx21=S
簡化后可的
????S=2h+2-2*h-4
而
????h= log2n
所以
????S=2hx22+2-2xh-4 =4xn-2x log2n-4
采用大O法，則其復(fù)雜度為O(n)
我們再看排序調(diào)整部分，交換算法算1次執(zhí)行，循環(huán)下來執(zhí)行的次數(shù)為(length-1)次，結(jié)點(diǎn)的調(diào)整情況我們可以類似初始構(gòu)建最大堆的情況分析。有21的結(jié)點(diǎn)調(diào)整了1次，有22的結(jié)點(diǎn)調(diào)整了2次，…，有2h個(gè)結(jié)點(diǎn)調(diào)整了h次。
累加可得：
????2x1x21+2x1x22+…+2xhx2h =S
同樣運(yùn)用數(shù)學(xué)歸納法得到最終的S:
????S=4n log2n-4n+4
這部分的復(fù)雜度為:
????S +n-1 = 4n log2n-3n+3
采用大O法，其復(fù)雜度為O(n log2n)。
兩個(gè)階段總的復(fù)雜度即為O(n log2n)。
空間復(fù)雜度：O(1)。
穩(wěn)定性：不穩(wěn)定排序。道理同簡單選擇排序一樣。
