C++排序之堆排序

以升序为例&＃xff0c;堆排序简单来说就是先将原数组调整为大堆&＃xff0c;此时根节点的数最大&＃xff0c;最后一个叶子节点数最小&＃xff0c;所以需将这两个节点的值进行交换&＃xff0c;然后保证最后这个叶子节点的数不变&＃xff0c;并从根节点开始往下调整&＃xff0c;使除最后一个叶子节点之外的数维持大堆状态。同理&＃xff0c;继续将调整后的根节点与倒数第二个叶子节点进行交换&＃xff0c;然后完成以上操作&＃xff0c;以此类推&＃xff0c;直至调整到根节点。

具体堆排序的理论只是可见博主的博客 温故而知新 -&＃xff1e; 数据结构 -&＃xff1e;排序。
同时&＃xff0c;因为堆排序基于二叉树的顺序结构存储&＃xff0c;因此在代码编写中会利用二叉树的一些性质&＃xff0c;若有不懂可见博主的博客 二叉树介绍 ~ 概念、存储结构、性质。

2.1 C&＃43;&＃43;代码

#include
#include
using namespace std;void display(vector<int>& arr)
{for (auto& n : arr)cout << n << " ";cout << endl;
}void _heapSort(vector<int>& arr, int len, int idx)
{int left &＃61; 2 * idx &＃43; 1;//左子节点的索引int right &＃61; 2 * idx &＃43; 2;//右子节点的索引int maxidx &＃61; idx;//用于保存idx指向的节点与两个子节点中最大值的索引if (left < len && arr[left] > arr[maxidx])maxidx &＃61; left;if (right < len && arr[right] > arr[maxidx])maxidx &＃61; right;if (maxidx !&＃61; idx){swap(arr[maxidx], arr[idx]);//将最大值置于根节点处_heapSort(arr, len, maxidx);//从交换过的节点的位置继续向下调整}
}void heapSort(vector<int>& arr)
{int len &＃61; arr.size();//先将原数组进行大堆调整for (int i &＃61; len / 2 - 1; i >&＃61; 0; i--)_heapSort(arr, len, i);//对调整后的数组进行调整for (int i &＃61; len - 1; i >&＃61; 1; i--)//此处判断条件 i >&＃61; 1 也可设置为 i >&＃61; 0&＃xff0c;只不过如此会产生一些无用的工作量{swap(arr[0], arr[i]);_heapSort(arr, i, 0);}
}void test()
{vector<int> arr &＃61; { 5, 2, 8, 6, 4, 7, 9, 1, 3 };cout << "原数组&＃xff1a;";display(arr);heapSort(arr);cout << "堆排序后&＃xff1a;";display(arr);
}int main()
{test();return 0;
}

2.2 运行结果