数据结构_排序④堆排序

2019-08-15 0 条评论 49 次阅读 0 人点赞

堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是
通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
时间复杂度:O( N*logN)
空间复杂度: O(1)
稳定性: 不稳定

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

//向下调整,调成大根堆 O(logN)
void ShiftDown(int* a,int n,int root){//数组个数n
    //(n - 2) / 2是最后一个非叶子索引
    // 0~(n - 2) / 2 所有非叶子节点索引
    assert(a);
    int parent = root;
    int child = 2 * parent + 1;
    //当前节点是否有child
    while (child < n){
        //是否有右child,如果有,两者当中选最大
        if(child + 1 < n && a[child + 1] > a[child])
            ++child;
        //child是否大于parent
        if(a[child] > a[parent]){
            //交换
            Swap(&a[child] , &a[parent]);
            //更新下一次调整的位置
            parent = child;
            child = 2 * parent + 1;
        }else{
            //以parent为根的子树已经是一个大堆,结束调整
            break;
        }
    }
}
// 堆排序
void HeapSort(int* a, int n){
    //建堆
    //最后一棵子树开始 (n - 2) /2
    int i , end;
    for (i = (n - 2) / 2 ; i >= 0 ; --i) {
        ShiftDown(a , n , i );
    }
    //堆排序
    end = n - 1;
    while(end > 0){//一次排序确定一个元素
        Swap(&a[0], &a[end]);//交换
        ShiftDown(a, end, 0);//从堆顶向下调整
        --end;//排一个 堆少一个元素
    }
}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)