数据结构算法学习排序堆排序

8次阅读

共计 945 个字符,预计需要花费 3 分钟才能阅读完成。

排序

将一组有顺序的元素按大小 (只要定义可以返回 true 或 false 的比较关系,非一定数值比较) 重新调整顺序。

堆排序

堆排序利用堆这种结构,把要排序的序列插入数组,保证最小堆的性质(父节点小于子节点),依次删除最小元素(在位置 0 上),并调整保证最小堆性质。

算法实现

#include <stdio.h>
#include <stdlib.h>
#include "elr_heap_int.h"
#include "elr_sort_heap.h"

long long int* elrSortHeap(long long int* arr, int len) {
    int i;
    pHeap tmp;
    if (arr) {tmp = elrInitHeap(len);
        for (i = 0; i < len; i++) {elrPushHeap(tmp, arr[i]);
        }
        for (i = 0; i < len; i++) {arr[i] = elrDeleteHeapMin(tmp);
        }
        elrFreeHeap(tmp);
    }
    
    return arr;
}

调试调用

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

int main(int argc, char **argv){
    int i;
    long long int arr[] = {6, 2, 4, 1, 3, 5, 0, 8, 9, 7};
    elrSortHeap(arr, 10);
    printf("%d\n", (int)(sizeof(arr) / sizeof(long long int)));
    for (i = 0; i < 10; i++) {printf("%lld", arr[i]);
    }
    printf("\n");
    return 0;
}

输出

insert:6   
insert:2   6   
insert:2   6   4   
insert:1   2   4   6   
insert:1   2   4   6   3   
insert:1   2   4   6   3   5   
insert:0   2   1   6   3   5   4   
insert:0   2   1   6   3   5   4   8   
insert:0   2   1   6   3   5   4   8   9   
insert:0   2   1   6   3   5   4   8   9   7   
delmin:1   2   4   6   3   5   7   8   9   
delmin:2   3   4   6   9   5   7   8   
delmin:3   6   4   8   9   5   7   
delmin:4   6   5   8   9   7   
delmin:5   6   7   8   9   
delmin:6   8   7   9   
delmin:7   8   9   
delmin:8   9   
delmin:9   
0   1   2   3   4   5   6   7   8   9 

正文完
 0