常见的排序算法归并排序(十大经典排序堆排序)

常见的排序算法归并排序(十大经典排序堆排序)(1)

什么堆?
  • 堆就是用数组实现的完全二叉树结构(除叶节点以外,所有节点都是非空,且叶节点从左到右排列)。
  • 完全二叉树中如果每颗子树的的最大值都在顶部就是大根堆。
  • 完全二叉树中如果每颗子树的的最小值都在顶部就是小根堆。
  • 堆结构就是heapInsert与heapfy操作。
  • 堆结构的增加和减少。
  • 优先级队列就是堆结构。
堆的heapInsert与heapfy操作

数组:1 9 4 8 2 6

索引:0 1 2 3 4 5

对应的完全二叉树结构:

常见的排序算法归并排序(十大经典排序堆排序)(2)

数组模拟完全二叉树

索引 i:i的左孩子对应的索引2*i 1

i的右孩子对应的索引2*i 2

i的父节点对应的索引(i-1)/2

  • heapInsert操作

某个位置处在index位置上往上继续移动,自下而上,构建大根堆/小根堆---------heapinsert操作

#include<iostream> #include<vector> using namespace std; //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>&arr, int index) { int parent = (index - 1) / 2; while (arr[index] > arr[parent]) { swap(arr[index], arr[parent]); index = parent; parent = (index - 1) / 2; } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; for (int i = 0; i < arr.size(); i ) { heapinsert(arr, i); } for (auto e : arr) { cout << e << " "; } return 0; }

运行结果:

常见的排序算法归并排序(十大经典排序堆排序)(3)

  • heapfy操作

某个数在index位置,能否往下移动,自上而下,构建大根堆/小根堆---------heapfy操作

#include<iostream> #include<vector> using namespace std; //某个数在index位置,能否往下移动---------heapfy操作 void heapify(vector<int>&arr, int index, int heapsize) { //左孩子下标 int left = 2 * index 1; //两个孩子中谁大,就把下标给largest while (left < heapsize) //左孩子存在 { int largest; if ((left 1 < heapsize) && arr[left 1] > arr[left]) { largest = left 1; } else { largest = left; } if (arr[largest] > arr[index]) { largest = largest; } else { largest = index; } if (largest == index) { break; } swap(arr[largest], arr[index]); index = largest; left = index * 2 1; } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; for (int i = arr.size()-1; i >= 0; i--) { heapify(arr, i, arr.size()); } int len = arr.size(); for (auto e : arr) { cout << e << " "; } return 0; }

运行结果:

常见的排序算法归并排序(十大经典排序堆排序)(4)

堆排序
  • 基本思想

用数组来模拟构建大根堆,完成数组的升序或降序。

  • 堆排序算法代码

(1)升序----构建大根堆

#include<iostream> #include<vector> using namespace std; //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>&arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr[index], arr[(index - 1) / 2]); } } //某个数在index位置,能否往下移动---------heapfy操作 void heapify(vector<int>&arr, int index, int heapsize) { //左孩子下标 int left = 2 * index 1; //两个孩子中谁大,就把下表给largest while (left < heapsize) //左孩子存在 { int largest; if ((left 1 < heapsize) && arr[left 1] > arr[left]) { largest = left 1; } else { largest = left; } if (arr[largest] > arr[index]) { largest = largest; } else { largest = index; } if (largest == index) { break; } swap(arr[largest], arr[index]); index = largest; left = index * 2 1; } } //堆排序----升序 void heap_sort(vector<int>&arr,int len) { if (len < 2) return; //heapinsert构建大根堆 //for (int i = 0; i < len; i ) //{ // heapinsert(arr, i); //} //heapfy构建大根堆 for(int i = len - 1; i >=0; i--) { heapify(arr, i, len); } int heapsize = len; swap(arr[0], arr[--heapsize]); while (heapsize > 0) { heapify(arr, 0, heapsize); swap(arr[0], arr[--heapsize]); } } int main() { vector<int>arr = { 1,9,4,8,2,6 }; int len = arr.size(); heap_sort(arr, len); for (auto e : arr) { cout << e << " "; } return 0; }

运行结果:

常见的排序算法归并排序(十大经典排序堆排序)(5)

(2)降序---构建小根堆

#include<iostream> using namespace std; #include<vector> //堆操作--------heapinsert 和 heapfy //某个位置处在index位置上 往上继续移动---------heapinsert操作 void heapinsert(vector<int>& arr, int index) { int parent = (index - 1) / 2; while (arr[index] < arr[parent]) { swap(arr[index], arr[parent]); index = parent; parent = (index - 1) / 2; } } //某个数在index位置,能否往下移动---------heapfy操作 void heapify(vector<int>& arr, int index, int heapsize) { //左孩子下标 int left = 2 * index 1; //两个孩子中谁大,就把小标给small while (left < heapsize) //左孩子存在 { int small; if ((left 1 < heapsize) && arr[left 1] < arr[left]) { small = left 1; } else { small = left; } if (arr[small] < arr[index]) { small = small; } else { small = index; } if (small == index) { break; } swap(arr[small], arr[index]); index = small; left = index * 2 1; } } //堆排序,降序 void heap_sort(vector<int>& arr, int len) { if (len < 2) return; //heapinsert构建小根堆 for (int i = 0; i < len; i ) { heapinsert(arr, i); } //heapfy构建小根堆 //for (int i = len - 1; i >= 0; i--) //{ // heapify(arr, i, len); //} int heapsize = len; swap(arr[0], arr[--heapsize]); while (heapsize > 0) { heapify(arr, 0, heapsize); swap(arr[0], arr[--heapsize]); } } int main() { vector<int> arr = { 1,9,4,8,2,6 }; //for (int i = 0; i < arr.size(); i ) //{ // heapinsert(arr, i); //} //for (int i = arr.size() - 1; i >= 0; i--) //{ // heapify(arr, i, arr.size()); //} heap_sort(arr, arr.size()); for (int i = 0; i < arr.size(); i ) { cout << arr[i] << " "; } return 0; }

运行结果:

常见的排序算法归并排序(十大经典排序堆排序)(6)

算法特性

时间复杂度:O(N*logN)

空间复杂度:O(1)

稳定性:不稳定

常见的排序算法归并排序(十大经典排序堆排序)(7)

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页