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