算法-堆排序

堆排序分两步：
建堆：把数组中元素按照堆的结构排成一定的顺序
排序：把有序的堆结构的数组元素排成升序
heapify本质上是一个排序方法，把无序变成堆的结构序列，递归迭代可以把下面所有子序列也排好。建堆过程用的正是这一点，而排序过程则是每次把堆顶(最大的值)拿出去，然后把剩下的被交换搞混乱的序列重新归为堆序列。

1、原理图解

数组中的堆结构

2、代码

void heapify(int arr[], int len, int i)
{
    int largest = i;
    int lson = i * 2 + 1;
    int rson = i * 2 + 2;
    NSLog(@"i=%d l=%d r=%d",largest,lson,rson);
    print_arr(arr, 10);

    if (lson < len && arr[largest] < arr[lson])
        largest = lson;
    if (rson < len && arr[largest] < arr[rson])
        largest = rson;
    if (largest != i)
    {
        swap(&arr[largest], &arr[i]);
        heapify(arr, len, largest);
    }
}

// 堆排序入口
void heap_sort(int arr[], int len)
{
    int i;
    // 建堆
    NSLog(@"建堆");
    for (i = len / 2 - 1; i >= 0; i--)
        heapify(arr, len, i);

    // 排序
    NSLog(@"排序");
    for (i = len - 1; i > 0; i--)
    {
        swap(&arr[i], &arr[0]);
        heapify(arr, i, 0);
    }
}

3、运行图解

建堆
i=4 l=9 r=10
6 1 5 3 9 2 10 8 4 7 
i=3 l=7 r=8
6 1 5 3 9 2 10 8 4 7 
i=7 l=15 r=16
6 1 5 8 9 2 10 3 4 7 
i=2 l=5 r=6
6 1 5 8 9 2 10 3 4 7 
i=6 l=13 r=14
6 1 10 8 9 2 5 3 4 7 
i=1 l=3 r=4
6 1 10 8 9 2 5 3 4 7 
i=4 l=9 r=10
6 9 10 8 1 2 5 3 4 7 
i=9 l=19 r=20
6 9 10 8 7 2 5 3 4 1 
i=0 l=1 r=2
6 9 10 8 7 2 5 3 4 1 
i=2 l=5 r=6
10 9 6 8 7 2 5 3 4 1 
排序
i=0 l=1 r=2
1 9 6 8 7 2 5 3 4 10 
i=1 l=3 r=4
9 1 6 8 7 2 5 3 4 10 
i=3 l=7 r=8
9 8 6 1 7 2 5 3 4 10 
i=8 l=17 r=18
9 8 6 4 7 2 5 3 1 10 
i=0 l=1 r=2
1 8 6 4 7 2 5 3 9 10 
i=1 l=3 r=4
8 1 6 4 7 2 5 3 9 10 
i=4 l=9 r=10
8 7 6 4 1 2 5 3 9 10 
i=0 l=1 r=2
3 7 6 4 1 2 5 8 9 10 
i=1 l=3 r=4
7 3 6 4 1 2 5 8 9 10 
i=3 l=7 r=8
7 4 6 3 1 2 5 8 9 10 
i=0 l=1 r=2
5 4 6 3 1 2 7 8 9 10 
i=2 l=5 r=6
6 4 5 3 1 2 7 8 9 10 
i=0 l=1 r=2
2 4 5 3 1 6 7 8 9 10 
i=2 l=5 r=6
5 4 2 3 1 6 7 8 9 10 
i=0 l=1 r=2
1 4 2 3 5 6 7 8 9 10 
i=1 l=3 r=4
4 1 2 3 5 6 7 8 9 10 
i=3 l=7 r=8
4 3 2 1 5 6 7 8 9 10 
i=0 l=1 r=2
1 3 2 4 5 6 7 8 9 10 
i=1 l=3 r=4
i=0 l=1 r=2
2 1 3 4 5 6 7 8 9 10 
i=0 l=1 r=2
1 2 3 4 5 6 7 8 9 10