【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
堆排序是另外一種常用的遞歸排序。因為堆排序有著優秀的排序性能，所以在軟件設計中也經常使用。堆排序有著屬於自己的特殊性質，和二叉平衡樹基本是一致的。打一個比方說，處於大堆中的每一個數據都必須滿足這樣一個特性：
（1）每一個array[n] 大於array[2*n]
（2）每一個array[n]大於array[2 * n + 1]
構建這樣一個堆只是基礎，後面我們需要每次從堆的頂部拿掉一個數據，不斷調整堆，直到這個數組變成有序數組為主。所以詳細的堆排序算法應該是這樣的：
1）構建大堆，使得堆中的每一個數據都滿足上面提到的性質
2）將堆的第一個數據和堆的最後一個數據進行互換，然後重新調整堆，直到堆重新平衡為止
3）重復2）的過程，直到整個數組有序。
上面的描述過程很簡單，那麼實踐操作是怎麼樣的呢？
a）對入參進行判斷
void heap_sort(int array[], int length)
{
if(NULL == array || 0 == length)
return ;
/* to make sure data starts at number 1 */
_heap_sort(array-1, length);
}
void heap_sort(int array[], int length)
{
if(NULL == array || 0 == length)
return ;
/* to make sure data starts at number 1 */
_heap_sort(array-1, length);
} b）構建大堆和調整大堆
void _heap_sort(int array[], int length)
{
int index = 0;
int median = 0;
construct_big_heap(array, length);
for(index = length; index > 1; index --)
{
median = array[1];
array[1] = array[index];
array[index] = median;
reconstruct_heap(array, 1, index-1);
}
}
void _heap_sort(int array[], int length)
{
int index = 0;
int median = 0;
construct_big_heap(array, length);
for(index = length; index > 1; index --)
{
median = array[1];
array[1] = array[index];
array[index] = median;
reconstruct_heap(array, 1, index-1);
}
} c）構建大堆的細節操作部分
void set_sorted_value(int array[], int length)
{
int index = length;
int median = 0;
if(length == 1) return;
while(index > 1){
if(array[index >> 1] >= array[index])
break;
median = array[index];
array[index] = array[index >> 1];
array[index >> 1] = median;
index >>= 1;
}
}
void construct_big_heap(int array[], int length)
{
int index = 0 ;
for(index = 1; index <= length; index ++)
{
set_sorted_value(array, index);
}
}
void set_sorted_value(int array[], int length)
{
int index = length;
int median = 0;
if(length == 1) return;
while(index > 1){
if(array[index >> 1] >= array[index])
break;
median = array[index];
array[index] = array[index >> 1];
array[index >> 1] = median;
index >>= 1;
}
}
void construct_big_heap(int array[], int length)
{
int index = 0 ;
for(index = 1; index <= length; index ++)
{
set_sorted_value(array, index);
}
} d）大堆迭代調整
void reconstruct_heap(int array[], int index, int length)
{
int swap = 0;
if(length < index << 1)
return;
if(length == index << 1){
adjust_leaf_position(array, index);
return;
}
if(-1 != (swap = adjust_normal_position(array, index))){
reconstruct_heap(array, swap, length);
}
}
void reconstruct_heap(int array[], int index, int length)
{
int swap = 0;
if(length < index << 1)
return;
if(length == index << 1){
adjust_leaf_position(array, index);
return;
}
if(-1 != (swap = adjust_normal_position(array, index))){
reconstruct_heap(array, swap, length);
}
} e）對單分支節點和滿分支節點分別處理
int adjust_normal_position(int array[], int index)
{
int left = index << 1 ;
int right = left + 1;
int median = 0;
int swap = 0;
if(array[index] >= array[left]){
if(array[index] >= array[right]){
return -1;
}else{
swap = right;
}
}else{
if(array[index] >= array[right]){
swap = left;
}else{
swap = array[left] > array[right] ? left : right;
}
}
if(swap == left) {
median = array[index];
array[index] = array[left];
array[left] = median;
}else{
median = array[index];
array[index] = array[right];
array[right] = median;
}
return swap;
}
STATUS adjust_leaf_position(int array[], int index)
{
int median = 0;
if(array[index] > array[index << 1])
return TRUE;
median = array[index];
array[index] = array[index << 1];
array[index << 1] = median;
return FALSE;
}
int adjust_normal_position(int array[], int index)
{
int left = index << 1 ;
int right = left + 1;
int median = 0;
int swap = 0;
if(array[index] >= array[left]){
if(array[index] >= array[right]){
return -1;
}else{
swap = right;
}
}else{
if(array[index] >= array[right]){
swap = left;
}else{
swap = array[left] > array[right] ? left : right;
}
}
if(swap == left) {
median = array[index];
array[index] = array[left];
array[left] = median;
}else{
median = array[index];
array[index] = array[right];
array[right] = median;
}
return swap;
}
STATUS adjust_leaf_position(int array[], int index)
{
int median = 0;
if(array[index] > array[index << 1])
return TRUE;
median = array[index];
array[index] = array[index << 1];
array[index << 1] = median;
return FALSE;
}
f）堆排序算法介紹完畢，創建測試用例驗證
static void test1()
{
int array[] = {1};
heap_sort(array, sizeof(array)/sizeof(int));
}
static void test2()
{
int array[] = {2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
}
static void test3()
{
int array[] = {3, 2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test4()
{
int array[] = {2, 3, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test5()
{
int array[] = {5,3, 4, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(3 == array[1]);
assert(4 == array[2]);
assert(5 == array[3]);
}
static void test6()
{
int array[] = {2, 3,6, 8, 7};
heap_sort(array, sizeof(array)/sizeof(int));
assert(2 == array[0]);
assert(3 == array[1]);
assert(6 == array[2]);
assert(7 == array[3]);
assert(8 == array[4]);
}
static void test7()
{
int array[] = {3,4,2,7,1,9,8,6,5};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
assert(4 == array[3]);
assert(5 == array[4]);
assert(6 == array[5]);
assert(7 == array[6]);
assert(8 == array[7]);
assert(9 == array[8]);
}
static void test1()
{
int array[] = {1};
heap_sort(array, sizeof(array)/sizeof(int));
}
static void test2()
{
int array[] = {2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
}
static void test3()
{
int array[] = {3, 2, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test4()
{
int array[] = {2, 3, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
}
static void test5()
{
int array[] = {5,3, 4, 1};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(3 == array[1]);
assert(4 == array[2]);
assert(5 == array[3]);
}
static void test6()
{
int array[] = {2, 3,6, 8, 7};
heap_sort(array, sizeof(array)/sizeof(int));
assert(2 == array[0]);
assert(3 == array[1]);
assert(6 == array[2]);
assert(7 == array[3]);
assert(8 == array[4]);
}
static void test7()
{
int array[] = {3,4,2,7,1,9,8,6,5};
heap_sort(array, sizeof(array)/sizeof(int));
assert(1 == array[0]);
assert(2 == array[1]);
assert(3 == array[2]);
assert(4 == array[3]);
assert(5 == array[4]);
assert(6 == array[5]);
assert(7 == array[6]);
assert(8 == array[7]);
assert(9 == array[8]);
}
