简单选择排序和堆排序

最近在全面学习数据结构，常用算法记录：简单选择排序和堆排序，简单选择排序的基本思想是每一趟在待排序元素中选取关键字最小的元素加入有序子序列，直到所有元素有序，总共进行 $n-1$ 趟。 堆排序的基本思想见文末图片。 简单选择排序为**不稳定**排序。 堆排序为**不稳定**排序。 **简单选择排序时间复杂度：** 时间复杂度：$O(n^2)$ 空间复杂度：$O(1)$ **堆排序时间复杂度：** 一个节点每下降一层，最多只需要比较两次关键字。若树高度为 $h$，某节点在第 $i$ 层，则将这个节点向下调整最多只需要下降 $h-i$ 层，那么对比次数不超过 ${2}(h-i)$，$n$ 个节点的完全二叉树树高 $h = \left\lfloor {{{\log }_2}n} \right\rfloor + 1$。 将整棵树调整为大根堆，关键字比较次数不超过： $$ \sum\limits_{{\rm{i}} = h - 1}^1 {{2^{i - 1}}2(h - i) = } \sum\limits_{{\rm{i}} = h - 1}^1 {{2^i}(h - i) = } \sum\limits_{j = 1}^{h - 1} {{2^{h - j}}j \le 2n\sum\limits_{j = 1}^{h - 1} {\frac{j}{{{2^j}}}} } \le 4n $$ 建堆的过程关键字的对比次数不超过 ${4}n$，建堆的时间复杂度：$O(n)$ `heapSort`总共需要 $n-1$ 趟，每一趟完成后都需要将根节点下坠，根节点最多下降 $h-1$ 层，因此，每一趟排序的复杂度不超过 $O(h)=O({{{\log }_2}n})$，总共 $n-1$ 趟，故总时间复杂度：$O(n{{{\log }_2}n})$ 故堆排序的时间复杂度：$O(n)+O(n{{{\log }_2}n})=O(n{{{\log }_2}n})$ 空间复杂度：$O(1)$ ```cpp #include using namespace std; void swap(int &a, int &b); void selectSort(int arr[], int n); //简单选择排序 void buildMaxHeap(int arr[], int len); //建立大根堆 void headAdjust(int arr[], int k, int len); //调整节点，使其较小节点下坠，使其符合大根堆的特性 void heapSort(int arr[], int len); //堆排序（基于大根堆） int main() { int arr[] = {5, 7, 12, 6, 2, 0, 8, 15, 1, 11}, heap_arr[] = {-1, 5, 7, 12, 6, 2, 0, 8, 15, 1, 11}; int length = (int)(sizeof(arr) / sizeof(int)); //数组长度 selectSort(arr, length); for(auto item:arr) cout 0; i--) //从最后一个分支节点开始调整，0为暂存节点 headAdjust(arr, i, len); } void headAdjust(int arr[], int k, int len) { arr[0] = arr[k]; //将当前节点暂存给arr[0] for (int i = 2 * k; i = arr[i]) break; //如果当前节点大于等于左右子节点，则不需要调整 else{ arr[k] = arr[i]; //将左右子节点中较大的节点放入当前双亲节点 k = i; //替换为较大的节点，进入下一次循环，看是否满足大于左右孩子的条件 } } arr[k] = arr[0]; //将待调整的节点的值放入最终位置 } void heapSort(int arr[], int len) { buildMaxHeap(arr, len); //建立大根堆 for (int i = len; i > 1; i--) { swap(arr[1], arr[i]); //堆顶和堆底交换，使堆底元素最大，注意堆顶是arr[1]，arr[0]是暂存节点 headAdjust(arr, 1, i - 1); //调整剩余的堆（i及其后面的序列已经有序），让堆顶元素下坠 } } ``` 

以上内容来自博客订阅源，版权归原作者。热度统计站内详情页访问。