当前位置：首页 > news >正文

数据结构-堆排序问题

news 来源：原创 2024/9/29 19:19:33

需要在数组里面进行排序，我们可以采取堆排序对其解决问题

版本1：

创建一个数组等大的堆，把数组里面的数值输入到堆里面进行堆排序，但是这样的弊端就是，不是顺序排序

版本2：

每次我们取堆顶然后打印，最后出堆，循环

弊端就是这样是时间复杂度我们发现还是o(n)，没有必要那么麻烦半天时间复杂度还是这样

版本3:（推荐）

在数组上面进行排序，直接输出顺序排序

逻辑讲解

1，需要在数组里面进行排序，我们可以采取在数组建堆

2，然后交换收尾元素，每次调整的数值减少1

讲解逻辑

首先我们需要知道，

如果我们需要排序的是降序，我们就需要建立小堆

如果我们需要排序的是升序，我们就需要建立大堆

如果我们需要的是升序建立小堆的话

如果我们采取相反的方式的话，就会导致：（出现两个根）

首先n个数建小堆，固定第一个值是最小值
剩下的n-1个数再建堆
效率就很差了

如果相反的话，会导致根节点变化，从而导致逻辑混乱，数组里面的数值少的时候是不明显的，但是多的时候就不行了

逻辑实现图解

代码实现
//向下调整（大堆）
void AdjustDown(HPDataType* a, int n, int parent)
{int chile = parent * 2 + 1;//循环条件不能是父亲，不然会导致越界while (chile < n){//三个孩子进行比较if (chile + 1 < n && a[chile] < a[chile + 1]){chile++;}if (a[chile] > a[parent]){Swap(&a[chile], &a[parent]);parent = chile;chile = parent * 2 + 1;}else{break;}}
}
//堆排序数组内进行调整解决
void sort_test(int* a, int sz)
{//放出来的是小堆，所以我们只能排序降序，这样逻辑更融洽//建堆for (int i = 0; i < sz; i++){AdjustUp(a, i);}//交换排序 把首个元素和最后一个交换进行排序 每次--while (sz > 0){Swap(&a[0], &a[sz - 1]);AdjustDown(a, sz - 1, 0);sz--;}
}
这个 sort_test 函数实现了一个堆排序算法，它接收一个整数数组 a 和它的大小 sz：

建堆：首先，函数通过调用 AdjustUp 函数来构建一个小顶堆（最小堆）。建堆过程是从最后一个非叶子节点开始向上调整，直到堆顶。

交换和排序：在建堆之后，函数进入一个循环，每次循环中，它将堆顶元素（当前堆中的最小元素）与当前堆的最后一个元素交换。然后，堆的大小减少 1，并且对剩余的堆进行向下调整以保持最小堆性质。

循环结束：循环继续进行，直到堆的大小减小到 0。最终，数组 a 将被排序为降序。