堆排序

#include <stdio.h>

void Swap(int arr[], int m, int n)
{
        if (m == n) return;
        arr[m] += arr[n];
        arr[n] = arr[m] - arr[n];
        arr[m] = arr[m] - arr[n];
}

int Max(int a, int b, int c)
{
        if (a >= b)
        {
                if (a >= c) return a;
                else return c;
        }
        else
        {
                if (b >= c) return b;
                else return c;
        }
}

// 只有s不符合堆规则（s的left和right都符合），需要调整s
void HeapAdjust(int arr[], int s, int e)
{
        int left = s * 2 + 1;
        int right = left + 1;

        if (left > e) return;
        else if (right > e)
        {
                if (arr[s] >= arr[left]) return;
                else
                {
                        Swap(arr, s, left);
                        HeapAdjust(arr, left, e);
                }
        }
        else
        {
                int i = Max(arr[s], arr[left], arr[right]);
                if (i == arr[s])
                        return;
                else if (i == arr[left])
                {
                        Swap(arr, s, left);
                        HeapAdjust(arr, left, e);
                }
                else
                {
                        Swap(arr, s, right);
                        HeapAdjust(arr, right, e);
                }
        }
}

void BuildHeap(int arr[], int num)
{
        for (int i=int(num/2-1); i>=0; --i)  //最后一个非叶子节点int(num/2-1)，如果从1编号，则为int(num/2)
        {
                HeapAdjust(arr, i, num-1);
        }
}

int main(int argc, char * argv[])
{
        printf("Hello World\n");

        int array[] = {12, 33, 2, 34, 29, 101, 7, 23, 48, 100};
        int len = sizeof(array)/sizeof(array[0]);

        BuildHeap(array, len);

        for (int i=len-1; i>0; --i)  //条件i>0，因为循环语句中有i-1
        {
                Swap(array, 0, i);
                HeapAdjust(array, 0, i-1);
        }

        for (int i=0; i<len; ++i)
        {
                printf("%d ", array[i]);
        }
        printf("\n");
}