一般來說矿微，這三者的時間復(fù)雜度O(NlogN)，空間復(fù)雜度O(n)
優(yōu)化后尚揣，空間復(fù)雜度均可為O(1)涌矢，如下文中的快排和堆排序
歸并排序是穩(wěn)定排序算法，其余兩者不是穩(wěn)定排序
快排的最差時間復(fù)雜度為O(N^2),平均為O(NlogN)
歸并和堆的最差快骗、平均時間復(fù)雜度為O(NlogN)
T(n) = 2T(n/2)+cn

//歸并排序的特點：分治的應(yīng)用娜庇。需要準(zhǔn)確并深入的理解分治的思想，分而治之

#include <stdio.h>
#include <stdlib.h>

void Merge(int* a, int low, int mid, int high)
{
    int i = low, j = mid+1, size = 0;
    int tmpa[high-low+1] ;
    for (int k = 0; k < high-low+1; ++k){
        if(i > mid) tmpa[size++] = a[j++];
        else if(j > high) tmpa[size++] = a[i++];
        else if(a[i] <= a[j]) tmpa[size++] = a[i++];
        else tmpa[size++] = a[j++];
    }

    for(i = 0; i < size; i++)
        a[low+i] = tmpa[i];
}

void MergeSort(int* a, int low, int high)
{
    if(low >= high) return;

    int mid = (low + high) / 2;
    MergeSort(a, low, mid);
    MergeSort(a, mid+1, high);
    Merge(a, low, mid, high);
}

int Partition2(int* a, int l, int r)
{
    if(l >= r) return l;
    int len = r-l+1, tmp = a[l];
    int i = 0, j = len, k = 0;
    int atmp[len];

    for (k = l+1; k <= r; ++k){
        if (a[k] >= tmp) atmp[--j] = a[k];
        else atmp[i++] = a[k];
    }
    atmp[i] = tmp;
    for (k = 0; k < len; ++k){
        a[l+k] = atmp[k];
    }
    return l+i;
}

int Partition(int* a, int l, int r)
{
    int i = l, j = r, tmp = a[l];

    while(i < j){
        while((i < j) && (a[j] >= tmp)) j--;
        if (i < j){
            a[i++] = a[j];
        }
        while((i < j) && (a[i] < tmp)) i++;
        if (i < j){
            a[j--] = a[i];
        }
    }

    a[i] = tmp;
    return i;
}

void QuickSort(int* a, int low, int high)
{
    if(low >= high) return;

    int mid = Partition2(a, low, high);
    QuickSort(a, low, mid-1);
    QuickSort(a, mid+1, high);
}

# @arr:順序存儲二叉堆的數(shù)組
# @s: 調(diào)整的起始非葉節(jié)點
# @t: 二叉堆總長度方篮，或總結(jié)點數(shù)
# @Description:將以s節(jié)點為根的子二叉樹名秀，調(diào)整為二叉堆
def heap_adjust(arr, s, size):
    child = 2*s + 1  # s的左子節(jié)點
    while child < size:
        if (child+1 < size) and (arr[child] < arr[child+1]): # 左右倆中，找值大的孩子
            child += 1
        if arr[s] > arr[child]: # 孩子比父親小藕溅，說明無需調(diào)整
            break

        tmp = arr[child] # 孩子比父親大泰偿，則交換父親和大孩子，使其符合二叉堆性質(zhì)
        arr[child] = arr[s]
        arr[s] = tmp
        
        s = child # 這個孩子剛和父親交換被修改過蜈垮，所以以其為根的二叉堆要重新調(diào)整
        child = 2*s + 1

# @arr, 數(shù)組大小為N, 從0開始到N-1, heap也從零開始
# 最后一個非葉子節(jié)點序號為 N/2 -1
def heap_sort(arr):
    # 初始化堆耗跛，將原始數(shù)組，調(diào)整為大頂堆攒发，O(N)
    for i in range(len(arr)/2 - 1, -1, -1): # 從最后一個非葉子節(jié)點開始調(diào)整
        heap_adjust(arr, i, len(arr))

    for i in range(len(arr)-1, 0, -1):
        # 將堆頂元素(大頂堆调塌，故此為最大值)與最后一個元素交換，然后重新調(diào)整堆
        tmp = arr[i]
        arr[i] = arr[0]
        arr[0] = tmp
        heap_adjust(arr, 0, i)

int main()
{
    int arr[]={3, 4, 5, 6, 24, 13, 26, 1, 2, 27, 38, 15, 15};
    int size = sizeof(arr) / sizeof(int);

    //MergeSort(arr, 0, size-1);
    QuickSort(arr, 0, size-1);

    for(int i = 0; i < size; i++){
        printf("%3d ", arr[i]);
    }
    printf("\n");
    return 0;
}