堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。
堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heapify實現的。

堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。

由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。

堆排序是就地排序，輔助空間為O(1），

它是不穩定的排序方法。

// 兩兩互換
void swap (int* a, int i, int j)
{int tmp;tmp  = a[i];a[i] = a[j];a[j] = tmp;
}// a代表一個數組
// i代表要調整的結點的下標
// len代表數組的長度
// 調整堆
void heapify (int* a, int i, int len)
{int left  = 2 * i + 1;              // 左孩子結點下標  int right = 2 * i + 2;              // 右孩子結點下標int max = i;                        // 三個結點種最大元素下標if (left < len && a[left] > a[max]){max = left;}if (right < len && a[right] > a[max]){max = right;}// 當前父親結點不是所有結點種最大的元素，需要做調整if (max != i){swap (a, i, max);heapify (a, max, len);          // 調整被交換的結點}
}// 堆排序
void CreateHeap (int* a, int len)
{// 建堆int i;for (i = len/2-1; i >= 0; i--){heapify(a, i, len);}// 排序for (i = len-1; i > 0; i--){swap (a, 0, i);                 // 拿堆頂元素與堆尾元素進行交換heapify (a, 0, --len);          // 堆大小，調整堆頂元素}
}

堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄。

---

歸并排序是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列;即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

歸并過程為: 比較a[i]和a[j]的大小，若a[i]≤a[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1;否則將第二個有序表中的元素a[j]復制到r[k]中，并令j和k分別加上1，如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元。歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。

// a 是數組  tmp  是緩沖區
void merge(int *a, int left, int mid, int right, int *tmp)
{int i = left;int j = mid + 1;int k = 0;while (i <= mid && j <= right){if (a[i] > a[j]){tmp[k++] = a[j++];}else{   tmp[k++] = a[i++];}}while (i <= mid){tmp[k++] = a[i++];}while (j <= right){tmp[k++] = a[j++];}k = 0;for (i = left; i <= right; i++){a[i] = tmp[k++];}
}void mergeSort(int *a, int left, int right, int *tmp)
{if (left >= right)return;int mid = (left + right)/2;mergeSort (a, left, mid, tmp);    // 對左邊部分進行歸并排序mergeSort (a, mid+1, right, tmp); // 對右邊部分進行歸并排序merge (a, left, mid, right, tmp); // 將將部分數據進行歸并
}