C++ 堆排序 缺少输出

Question

输出结果:
数组长度:69

数组:
11255 22082 1581 29372 24075 22357 3907 15302 14921 28617 17571 3254 11398 16681 21108 28329 12475 20898 30727 28219 356 4301 18781 26363 1317 7880 10729 8988 16307 2443 25750 9069 18930 29817 1292 9099 5467 24118 22063 11860 32417 30905 10729 22176 29588 18338 20010 26668 12357 30925 21293 9431 22379 11047 1788 25105 27141 6080 18998 6800 25153 20770 8720 18500 30109 3298 11162 6798 16972
排序结果:
32417

---

Process exited after 0.02977 seconds with return value 3221226356
请按任意键继续. . .

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cstdarg>
using namespace std;

//声明函数:给定一个编号,输出它的父的编号
int father(int x)
{
    return ((x - 1) / 2);
}

//声明函数:给定一个编号,输出它的左孩子的编号
int leftchild(int x)
{
    return (x * 2 + 1);
}

//声明函数:给定一个编号,输出它的右孩子的编号
int rightchild(int x)
{
    return (x * 2 + 2);
}

//声明函数:给定数组元素的地址,输出它对应的元素在数组中的编号
int number_from_position(int *x, int *head)
{
    int *current;
    current = x;
    int count;
    count = 0;
    while (current != head)
    {
        current--;
        count++;
    }
    return count;
}

//声明函数:给定数组元素的编号,输出它的地址
int *position_from_number(int x, int *head)
{
    int *current;
    current = head;
    int count;
    count = 0;
    while (count < x)
    {
        current++;
        count++;
    }
    return current;
}

//声明函数:给定一个数,输出它是否属于数组元素的编号
int belong_to_array(int x, int xlength)
{
    if (x < xlength)
    {
        return 1;
    }
    return 0;
}

int main()
{
    //决定数组长度
    int length;
    srand((unsigned)time(NULL));
    length = (unsigned)rand() % 128;
    cout << "数组长度:" << length << "\n" << endl;
    //创建数组
    int *array = (int *)malloc(sizeof(int) * length);
    //发牌
    {
        int *operating;
        operating = array;
        int i;
        cout << "数组:" << endl;
        for (i = 0; i < length; i++)
        {
            *operating = (unsigned)rand();
            printf("%d\u0020", *operating);
            operating++;
        }
    }
    cout << "\n" << "排序结果:" << endl;

    //堆排序
    {
        int *operating;
        int remain;
        remain = length; //标记待排序区域
        while (remain > 0)
        {
            operating = array - 1 + remain; //把操作指针移到最后一个元素
            //创建最大堆
            while (number_from_position(operating, array) > 0)
            {
                int *position_of_father_current;
                position_of_father_current = position_from_number(father(number_from_position(operating, array)), array);
                int *position_of_leftchild_current;
                position_of_leftchild_current = position_from_number(leftchild(number_from_position(position_of_father_current,
                                                array)), array);
                int *position_of_rightchild_current;
                position_of_rightchild_current = position_from_number(rightchild(number_from_position(position_of_father_current,
                                                 array)), array);
                //将当前堆中的最大值移至顶端
                //两孩情况
                if (belong_to_array(number_from_position(position_of_rightchild_current, array), remain))
                {
                    *position_of_father_current = *position_of_father_current + *position_of_leftchild_current;
                    *position_of_leftchild_current = abs(*position_of_leftchild_current * 2 - *position_of_father_current);
                    *position_of_leftchild_current = (*position_of_father_current - *position_of_leftchild_current) / 2;
                    *position_of_father_current = *position_of_father_current - *position_of_leftchild_current;
                    *position_of_father_current = *position_of_father_current + *position_of_rightchild_current;
                    *position_of_rightchild_current = abs(*position_of_rightchild_current * 2 - *position_of_father_current);
                    *position_of_rightchild_current = (*position_of_father_current - *position_of_rightchild_current) / 2;
                    *position_of_father_current = *position_of_father_current - *position_of_rightchild_current;
                    operating--;
                }
                //一孩情况
                else if (belong_to_array(number_from_position(position_of_leftchild_current, array), remain))
                {
                    *position_of_father_current = *position_of_father_current + *position_of_leftchild_current;
                    *position_of_leftchild_current = abs(*position_of_leftchild_current * 2 - *position_of_father_current);
                    *position_of_leftchild_current = (*position_of_father_current - *position_of_leftchild_current) / 2;
                    *position_of_father_current = *position_of_father_current - *position_of_leftchild_current;
                    operating--;
                }
                //无孩情况
                else
                {
                    continue;
                }
                operating--;
            }
            //头尾交换
            int *tail;
            tail = array - 1 + remain;
            *array = *array + *tail;
            *tail = *array - *tail;
            *array = *array - *tail;
            remain--;
            printf("%d\u0020", *tail);
            free(tail);
        }
    }
    cout << "\n" << "完成" << endl;
    return 0;
}

Answer 1

代码看着有点乱，给你个堆排序的代码参考一下：

//堆排序
void swap(int array[], int x, int y) {
    int key  = array[x];
    array[x] = array[y];
    array[y] = key;
}
// 从小到大排序
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
    int parent = i;                    // 父节点下标
    int child  = 2 * i + 1;            // 子节点下标
    while (child < n) {
        if (child + 1 < n && array[child] < array[child + 1]) { // 判断子节点那个大，大的与父节点比较
            child++;
        }
        if (array[parent] < array[child]) { // 判断父节点是否小于子节点
            swap(array, parent, child);     // 交换父节点和子节点
            parent = child;                 // 子节点下标 赋给 父节点下标
        }
        child = child * 2 + 1; // 换行，比较下面的父节点和子节点
    }
}

void BuildHeap(int array[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆，必须从下往上比较
        Down(array, i, size);                 // 否则有的不符合大顶堆定义
    }
}

void HeapSort(int array[], int size) {
    BuildHeap(array, size); // 初始化堆
    
    for (int i = size - 1; i > 0; i--) {
        swap(array, 0, i); // 交换顶点和第 i 个数据
        // 因为只有array[0]改变，其它都符合大顶堆的定义，所以可以从上往下重新建立
        Down(array, 0, i); // 重新建立大顶堆        
    }
}

使用的时候直接调用HeapSort()函数就可以

HeapSort(array, length);