常見排序算法集合：堆排序與歸併排序深度解析

常見排序算法集合：堆排序與歸併排序深度解析

堆排序

堆排序分為兩個階段：建堆和排序。利用完全二叉樹的性質，將數組映射為堆結構。

數組索引映射關係

零基數組：

父節點：floor((i-1)/2)
左子節點：2*i + 1
右子節點：2*i + 2

一基數組（代碼中採用）：

父節點：floor(i/2)
左子節點：2*i
右子節點：2*i + 1

堆排序核心代碼

#include "priority_queue.h"
#define DEBUG

int heap_sort(int* array, int size) {
    struct heap* p_heap = init_heap(size);
    if (!p_heap) {
        printf("initialization failed in function %s()!\n", __FUNCTION__);
        return -1;
    }
    
    build_heap(p_heap, array, size);
    int tmp = 0;
    for (tmp = size; tmp > 0; tmp--) {
        p_heap->element[tmp] = delete_heap(p_heap);
    }
    p_heap->size = size;
    
    #ifdef DEBUG
    for (tmp = 1; tmp <= size; tmp++) {
        printf("%4d", p_heap->element[tmp]);
    }
    printf("\n");
    #endif
    
    destroy_heap(p_heap);
    return 0;
}

測試結果

使用最小堆，排序結果為從大到小：

歸併排序

歸併排序採用分治策略，關鍵優化：在外部預分配臨時數組，避免遞歸中重複 malloc/free 開銷。

頭文件定義

#ifndef _MERGE_SORT_H
#define _MERGE_SORT_H
#include <stdio.h>
#include <stdlib.h>

int merge(int* array, int* tmp_array, int left_pos, int right_pos, int right_end);
void msort(int* array, int* tmp_array, int left, int right);
#endif

核心合併函數

int merge(int* array, int* tmp_array, int left_pos, int right_pos, int right_end) {
    if (!array || !tmp_array) return -1;
    
    int tmp_pos = left_pos;
    int left_end = right_pos - 1;
    int num_element = right_end - left_pos + 1;
    
    while (left_pos <= left_end && right_pos <= right_end) {
        if (array[left_pos] <= array[right_pos])
            tmp_array[tmp_pos++] = array[left_pos++];
        else
            tmp_array[tmp_pos++] = array[right_pos++];
    }
    
    while (left_pos <= left_end)
        tmp_array[tmp_pos++] = array[left_pos++];
    while (right_pos <= right_end)
        tmp_array[tmp_pos++] = array[right_pos++];
    
    for (int tmp = 0; tmp < num_element; tmp++, right_end--)
        array[right_end] = tmp_array[right_end];
    
    return 0;
}

遞歸排序函數

void msort(int* array, int* tmp_array, int left, int right) {
    if (!array || !tmp_array) return;
    if (left >= right) return;
    
    int center = (left + right) / 2;
    msort(array, tmp_array, left, center);
    msort(array, tmp_array, center + 1, right);
    merge(array, tmp_array, left, center + 1, right);
}

測試程序與結果

int main() {
    int array[] = {10,12,1,14,6,5,8,15,3,9,7,4,11,13,2};
    int size = sizeof(array)/sizeof(array[0]);
    int* tmp_array = (int*)malloc(sizeof(int)*size);
    
    msort(array, tmp_array, 0, size-1);
    free(tmp_array);
    
    for (int i = 0; i < size; i++)
        printf("%5d", array[i]);
    printf("\n");
    return 0;
}

關鍵優化總結

• 堆排序：原地排序，空間 O(1)，時間 O(n log n)
• 歸併排序：預分配臨時數組避免重複內存分配，穩定排序
• 兩者都是 O(n log n) 級別的高效排序算法