首页 > 代码库 > 算法练习:堆排序
算法练习:堆排序
C++代码 1:
#include <iostream> #include <assert.h> using namespace std;//调整堆//s:需要调整的非终端节点的位序//len:整个待排序数组的长度void HeapAdjust(int a[], int s, int len){ int tmp = a[s]; for(int i=s*2; i<=len; i=i*2) { int largeIndex = i; if(i+1 <= len && a[i+1] > a[i]) { largeIndex = i+1; } if(tmp < a[largeIndex]) { a[s] = a[largeIndex]; s = largeIndex; } } a[s] = tmp;}void HeapSort(int a[], int len){ //构建大根堆 for(int i=len/2; i>=1; i--) { HeapAdjust(a, i, len); } //堆排序 for(int i=len; i>=1; i--) { //交换每次调整后的堆的相应的第一个元素和最后一个元素 int tmp = a[i]; a[i] = a[1]; a[1] = tmp; HeapAdjust(a, 1, i-1); }}int main() //堆排序,构建大根堆排序,输出数组元素的非递减序列//首先构建大根堆,然后交换根元素和最后一个元素->调整剩余的(n-1)个元素为新的大根堆,如此反复直到排序结束(即只剩下最后一个未排序元素){ int a[] = {0, 29, 345, 11, 3, 4, 899, 8, 1014};//因为堆排序的第一个元素序号为1,而数组的第一个元素序号为0,这里添加一个无用的首元素"0" int len = sizeof(a) / sizeof(int); cout << "----original----" << endl; for(int i=1; i<len; i++) cout << a[i] << " "; cout << endl; HeapSort(a, len-1); cout << "----result----" << endl; for(int i=1; i<len; i++) cout << a[i] << " "; cout << endl; cin.get(); cin.get(); return 0;}
C++代码 2 :用递归方式实现调整堆
#include <iostream> #include <assert.h> using namespace std;//调整堆//s:需要调整的非终端节点的位序//len:整个待排序数组的长度void HeapAdjust(int a[], int s, int len){ int largeIndex = s; int leftChildIndex = 2*s; if(leftChildIndex<=len && a[s]<a[leftChildIndex]) { largeIndex = leftChildIndex; } int rightChildIndex = 2*s + 1; if(rightChildIndex<=len && a[s]<a[rightChildIndex] && a[leftChildIndex]<a[rightChildIndex]) { largeIndex = rightChildIndex; } if(largeIndex != s) { int tmp = a[largeIndex]; a[largeIndex] = a[s]; a[s] = tmp; //用递归方式实现调整堆 HeapAdjust(a, largeIndex, len); }}void HeapSort(int a[], int len){ //构建大根堆 for(int i=len/2; i>=1; i--) { HeapAdjust(a, i, len); } //堆排序 for(int i=len; i>=1; i--) { //交换每次调整后的堆的相应的第一个元素和最后一个元素 int tmp = a[i]; a[i] = a[1]; a[1] = tmp; HeapAdjust(a, 1, i-1); }}int main() //堆排序,构建大根堆排序,输出数组元素的非递减序列//首先构建大根堆,然后交换根元素和最后一个元素->调整剩余的(n-1)个元素为新的大根堆,如此反复直到排序结束(即只剩下最后一个未排序元素){ int a[] = {0, 29, 345, 11, 3, 4, 899, 8, 1014};//因为堆排序的第一个元素序号为1,而数组的第一个元素序号为0,这里添加一个无用的首元素"0" int len = sizeof(a) / sizeof(int); cout << "----original----" << endl; for(int i=1; i<len; i++) cout << a[i] << " "; cout << endl; HeapSort(a, len-1); cout << "----result----" << endl; for(int i=1; i<len; i++) cout << a[i] << " "; cout << endl; cin.get(); cin.get(); return 0;}
算法练习:堆排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。