簡單選擇排序（直接選擇排序）：
基本思路：
第一次從A[0..n-1]中選取最小值升筏，與A[0]交換童叠；
第二次從A[1..n-1]中選取最小值，與A[1]交換漠酿；
第i次從A[i-1..n-1]中選取最小值，與A[i-1]交換吉嚣，
......
n個記錄的文件的直接選擇排序可經過n-1趟直接選擇排序得到有序結果梢薪。
實現(xiàn)代碼：(C#)
static void SelectSort(int[] array)
{
int pos; //用于記錄的下標
for (int i = 0; i < array.Length - 1; i++)
{
pos = i;
for (int j = i + 1; j < array.Length; j++)//從第二個下標開始，遍歷后面所有的數(shù)
{
//比pos小尝哆，則記錄下標秉撇，直到遍歷完，找到最小值
if (array[j] < array[pos]) pos = j;
}
if (pos != i) //交換操作
{
int temp = array[i];
array[i] = array[pos];
array[pos] = temp;
}
}
}
總結：
1秋泄、若初始對象是有序的琐馆，則對象移動次數(shù)為0，達到最泻阈颉瘦麸；但比較次數(shù)還是多，且與初始對象排列無關歧胁；時間效率：O(n2)
堆排序：
什么是堆：
一個k[0]到k[n-1]的序列滿足以下條件稱為堆
將該序列順次排成一棵完全二叉樹滋饲，則此樹的特點是：
樹中所有結點的值均大于（或小于）其左右孩子，此樹的根結點（即堆頂）必最大（或最泻拔 ）屠缭。
如何建堆：
步驟：從最后一個非終端結點開始往前逐步調整，讓每個雙親大于（或小于）子女崭参，直到根結點為止呵曹。（終端節(jié)點即葉子，沒有任何子女）何暮；
根據(jù)性質奄喂，最后非終端節(jié)點下標必為 (n-1)/2 。
例：關鍵字序列T= (21海洼，25砍聊，49，25*贰军，16玻蝌，08），請建大根堆词疼。
解：為便于理解俯树，先將原始序列畫成完全二叉樹的形式：
這樣可以很清晰地從 (n-1)/2 開始調整。
怎樣進行堆排序：
方法：將當前頂點與堆尾記錄交換贰盗，然后仿建堆動作重新調整许饿，如此反復直至排序結束。
例：對剛建好的大根堆進行排序：
代碼實現(xiàn)：(C#)
創(chuàng)建堆：
//創(chuàng)建堆
//n為需要建堆的元素個數(shù)舵盈，root_index為傳入的非葉結點下標
public static void CreateHeap(int[] nums, int n, int root_index)
{
int i, j;
int temp;
i = root_index;
j = 2 * i + 1; //左子結點下標
temp = nums[i];
while (j < n)
{
if (j < n - 1 && nums[j] < nums[j + 1]) j++; //獲取左右葉結點中最大的一個
//因為初始化是從下往上創(chuàng)建陋率，下面已經滿足堆的狀態(tài)球化，
//所以遇到父節(jié)點大于葉結點直接退出循環(huán)即可
if (temp > nums[j])
{
break;
}
else
{
//繼續(xù)往下比較
nums[i] = nums[j];
i = j;
j = 2 * j + 1;
}
}
nums[i] = temp;
}
初始化堆：
public static void InitHeap(int[] nums)
{
//從最后一個非葉結點開始往前，一直到根節(jié)點
for (int i = (nums.Length - 1) / 2; i >= 0; i--)
{
CreateHeap(nums, nums.Length, i);
}
}
堆排序實現(xiàn)：
public static void HeapSort(int[] nums)
{
int temp;
InitHeap(nums);
for (int i = nums.Length - 1; i > 0; i--)
{
//根節(jié)點與最后一個葉結點交換
temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
CreateHeap(nums, i, 0);
}
}
總結：
1瓦糟、時間效率： O(nlog2n)筒愚。因為整個排序過程中需要調用n-1次堆頂點的調整，而每次堆排序算法本身耗時為log2n
2菩浙、優(yōu)點：對小文件效果不明顯巢掺，但對大文件有效。
