// test20.cpp : 定義控制臺應用程序的入口點。
//

#include "stdafx.h" #include<iostream> #include<vector> #include<string> #include<queue> #include<stack> #include<cstring> #include<string.h> #include<deque> #include <forward_list>using namespace std;class Solution { public://一般選擇排序void SelectSort(vector<int> &vec){for (int i = 0;i < vec.size();++i){int min_lable= i; //記錄下最小值對應的編號for (int j = i+1;j < vec.size();++j){if (vec[min_lable] > vec[j]){min_lable = j;}}if (min_lable != i){int temp = vec[i];vec[i] = vec[min_lable];vec[min_lable] = temp;}}print(vec);}//堆排序//調整堆void HeapAdjust(vector<int> &vec,int h,int m)//h為堆頭，m為總的元素數量h+1...m已經是堆{int lable = h;//cout << "原來的head:" <<vec[lable] << endl;for (int i = (h + 1) * 2 - 1;i < m;i = (i + 1) * 2 - 1) //(h+1)*2-1對應h的左孩子，(h+1)*2對應節點的右孩子{if (i + 1 < m)//判斷右孩子是否存在{if (vec[i] < vec[i + 1]) i=i+1;//右孩子比較大}if (vec[lable] > vec[i]){break;}//頭節點的值比兩個孩子都大，則已經是堆，break；else //與最大的孩子交換值{int temp = vec[lable];vec[lable] = vec[i];vec[i] = temp;lable = i;//注意更新lable,之前就是因為這一塊的問題總是出現問題！！！！！！！！！！！！} //交換完成之后繼續向下判斷}}//除建立堆//所有葉子節點都是堆，所以建立堆的時候應該是從size/2-1的節點開始處建立堆void CreatHeap(vector<int> &vec){int size = vec.size();for (int i = size / 2 - 1;i >= 0;--i){HeapAdjust(vec,i,size);//反復調用HeadAdjust來調整堆cout << "第" << i << "遍歷：";print(vec);}cout << "第最后的排序：";print(vec);}//堆排序void HeapSort(vector<int> &vec){//先建堆//每次選擇堆中最大的值與最后一個節點交換//再調整堆CreatHeap(vec);for (int i = vec.size() - 1;i > 0;--i){int temp = vec[0];vec[0] = vec[i];vec[i] = temp; //每次和vec數組后面的值交換HeapAdjust(vec,0,i);//調整前i個元素為堆}print(vec);}void print(vector<int> &vec)//打印數據{for (auto it = vec.begin();it != vec.end();++it){cout << *it << " ";}cout << endl;}}; int main() {vector<int> vec = { 49,38,65,97,76,13,27,49}; // vector<int> vec = {7,6,5,4,3,2,1 }; // vector<int> vec = { 0,1,2,3,4,5,6,7 }; // vector<int> vec = { 0,1,6,7,4,5,2,3};Solution so;//原來的序列cout << "原來的序列: ";so.print(vec);/*cout << "選擇排序后的的序列: ";so.SelectSort(vec);*///cout << "大堆頂的序列為：" << endl;//so.CreatHeap(vec);cout << "堆排序：" << endl;so.HeapSort(vec);return 0; }

轉載于:https://www.cnblogs.com/wdan2016/p/6057348.html

總結

以上是生活随笔為你收集整理的选择排序——一般选择排序，堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。