堆排序

废话不多说先上代码

void heapSort(int arr[], int length) {
    int *heap = heapBuild(arr, length);
    for(int i = 0; i < length; ++i) {
        arr[i] = heapPop(heap, length);
    }

    return;
}
int* heapBuild(int arr[], int length) {
    int *heap = (int*)calloc(length + 1, sizeof(int));
    int middle = length >> 1;
    for(int i = middle; i > 0; --i) {
        heapfiy(heap, i, length);
    }

    return heap;
}
void heapfiy(int *heap, int index, int length) {
    int swap = index;
    int temp;
    while(1) {
        if(index * 2 <= length && heap[index * 2] < heap[swap])
            swap = index * 2;
        if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
            swap = index * 2 + 1;
        if(index == swap)
            break;
        temp = heap[index];
        heap[index] = heap[swap];
        heap[swap] = temp;
        index = swap;
    }

    return;
}
int heapPop(int *heap, int *length) {
    int result = heap[1];
    heap[1] = heap[*length];
    (*length)--;
    heapfiy(heap, 1, *length);

    return result;
}

时间复杂度

O(n * log n)

空间复杂度

O(1) 原地排序,注意我这里写的代码不是原地排序。

稳定排序

不是稳定排序，因为弹出堆顶元素要和最后一个元素互换，保证二叉树的完全性。

算法核心思想

将待排序数组构建为二叉堆，不断弹出堆顶元素。
关于什么是二叉堆我就不详细说了，以后有时间再写。

堆排序的实现

将待排序数组构建成二叉堆

//堆排序
void heapSort(int arr[], int length) {
    int *heap = heapBuild(arr, length);
}
//建堆函数
int* heapBuild(int arr[], int length) {
    //为了方便计算数的下标 我们申请一个比length大的一的空间
    int *heap = (int*)calloc(length + 1, sizeof(int));
     //我们只需对非子节点进行堆化；
    int middle = length >> 1;
    for(int i = middle; i > 0; --i) {
        heapfiy(heap, i, length);
    }

    return heap;
}
//堆化过程
void heapfiy(int *heap, int index, int length) {
    int swap = index;
    int temp;
    while(1) {
        //如果左节点小于当前节点就交换
        if(index * 2 <= length && heap[index * 2] < heap[swap])
            swap = index * 2;
        //如果右节点小于当前节点 或 小于右节点且小于当前节点就交换
        if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
            swap = index * 2 + 1;
        //终止条件 当前节点大于子节点
        if(index == swap)
            break;
        temp = heap[index];
        heap[index] = heap[swap];
        heap[swap] = temp;
        index = swap;
    }

    return;
}

弹出对顶元素并赋值

//堆排序
void heapSort(int arr[], int length) {
    int *heap = heapBuild(arr, length);
    for(int i = 0; i < length; ++i) {
        arr[i] = heapPop(heap, length);
    }

    return;
}
//建堆函数
int* heapBuild(int arr[], int length) {
    //为了方便计算数的下标 我们申请一个比length大的一的空间
    int *heap = (int*)calloc(length + 1, sizeof(int));
     //我们只需对非子节点进行堆化；
    int middle = length >> 1;
    for(int i = middle; i > 0; --i) {
        heapfiy(heap, i, length);
    }

    return heap;
}
//堆化过程
void heapfiy(int *heap, int index, int length) {
    int swap = index;
    int temp;
    while(1) {
        //如果左节点小于当前节点就交换
        if(index * 2 <= length && heap[index * 2] < heap[swap])
            swap = index * 2;
        //如果右节点小于当前节点 或 小于右节点且小于当前节点就交换
        if(index * 2 + 1 <= length && heap[index * 2 + 1] < heap[swap])
            swap = index * 2 + 1;
        //终止条件 当前节点大于子节点
        if(index == swap)
            break;
        temp = heap[index];
        heap[index] = heap[swap];
        heap[swap] = temp;
        index = swap;
    }

    return;
}
//弹出堆顶元素
int heapPop(int *heap, int *length) {
    int result = heap[1];
    heap[1] = heap[*length];
    (*length)--;
    heapfiy(heap, 1, *length);

    return result;
}

堆排序到这就结束了，动手写一遍会更容易理解~

堆排序，堆排序你必须理解什么是堆，再谈排序。以后有时间我会写写这类数据结构的。
都看到这了，点个赞再走啊~。