堆排序
是利用堆这种数据结构而设计的一种排序算法, 堆排序是一种选择排序, 它的最坏, 最好, 平均时间复杂度均为 O(nlogn), 它也是不稳定排序.
首先简单了解下堆结构.
堆
堆是具有以下性质的完全二叉树: 每个结点的值都大于或等于其左右孩子结点的值, 称为大顶堆;
或者每个结点的值都小于或等于其左右孩子结点的值, 称为小顶堆.
如下图:
该数组从逻辑上讲就是一个堆结构, 我们用简单的公式来描述一下堆的定义就是:
大顶堆: arr[i]>= arr[2i+1] && arr[i]>= arr[2i+2]
小顶堆: arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
ok, 了解了这些定义.
接下来, 我们来看看堆排序的基本思想及基本步骤:
堆排序的基本思想是: 将待排序序列构造成一个大顶堆, 此时, 整个序列的最大值就是堆顶的根节点. 将其与末尾元素进行交换, 此时末尾就为最大值.
然后将剩余 n-1 个元素重新构造成一个堆, 这样会得到 n 个元素的次小值. 如此反复执行, 便能得到一个有序序列了
步骤一 构造初始堆. 将给定无序序列构造成一个大顶堆(一般升序采用大顶堆, 降序采用小顶堆).
a. 假设给定无序序列结构如下
2. 此时我们从最后一个非叶子结点开始(叶结点自然不用调整, 第一个非叶子结点 arr.length/2-1=5/2-1=1, 也就是下面的 6 结点), 从左至右, 从下至上进行调整.
- #include <iostream>
- #include <vector>
- using namespace std;
- class Solution
- {
- public:
- // 首先构建一个大根堆(len 是数组长度, index 是第一个非叶子节点下标)
- void adjust(vector<int>&vec, int len, int index)
- {
- if (index> len) // 递归出口
- return ;
- int left = 2*index + 1; // index 的左孩子
- int right = 2*index + 2; // index 的右孩子
- int maxIdx = index;
- // 将 maxidx 作为子树的最大值, 在下标不越界的情况下
- if (vec[maxIdx] <vec[left] && left < len)
- {
- maxIdx = left;
- }
- if(vec[maxIdx] < vec[right] && right < len)
- {
- maxIdx = right;
- }
- if (index != maxIdx) // 最大值不是在堆顶就交换
- {
- swap(vec[index], vec[maxIdx]);
- adjust(vec, len, maxIdx); // 递归所有的子树, 构建
- }
- }
- void heapSort(vector<int>&vec, int len)
- {
- // 调用一次 adjust 只是进行一次的调整
- // 构建整个大根堆, 从(最后一个非叶子节点向上)
- // 找到最后一个根节点, 然后不断向上构建 // 3 那个节点
- for (int i = len / 2 - 1; i>= 0; i--)
- {
- adjust(vec, len, i);
- }
- // 这里结束之后就是一个大根堆了
- // 调整大根堆
- for(int i = len-1; i>= 1; --i)
- {
- swap(vec[0], vec[i]); // 将最大的放到数组最后
- adjust(vec, i, 0); // 尚未排完序的部分继续进行堆排序
- }
- }
- };
- int main()
- {
- vector<int> vec = {3,5,6,32,35,56,3};
- Solution s;
- s.heapSort(vec, vec.size());
- for(int i = 0; i< vec.size(); i++)
- cout << vec[i] << " ";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3461135.html