堆排序
算法思想:堆排序(Heap Sort)是指利用堆(heaps)这种数据结构来构造的一种排序算法。
堆是一个近似完全二叉树结构,并同时满足堆属性:即子节点的键值或索引总是
小于(或者大于)它的父节点。
时间复杂度 o(nlogn)
空间复杂度 o(1)
比较次数:较多
*/
void heap_adjust(int array[],int i,int len)
{
int rc = array[i];
for(int j = 2 * i; j { if(j < len && array[j]< array[j+1]) j++; if(rc >= array[j]) break; array[i] = array[j]; i = j; } array[i] = rc; } void heap_sort(int array[],int len) { int i; for(i = (len-1)/2; i >= 0; i--) heap_adjust(array,i,len); for( i = (len-1); i > 0; i--) { swap(array[0],array[i]); //弹出最大值,重新对i-1个元素建堆 heap_adjust(array,0,i-1); } } int main() { int array[] = {45, 56, 76, 234, 1, 34,23, 2, 3, 55, 88, 100}; int len = sizeof(array)/sizeof(int); //bubble_sort(array,len); //冒泡排序 /*insert_sort(array,len);*/ //插入排序 /*bi_insert_sort(array,len);*/ //二路插入排序 /*shell_sort(array,len);*/ //希尔排序 /*quick_sort(array,0,len-1);*/ //快速排序 /*select_sort(array,len);*/ //选择排序 /*merge_sort(array,0,len-1);*/ //归并排序 heap_sort(array,len); //堆排序 display(array,len); return 0; }
① 凡本网注明稿件来源为"原创"的所有文字、图片和音视频稿件,版权均属本网所有。任何媒体、网站或个人转载、链接转贴或以其他方式复制发表时必须注明"稿件来源:我考网",违者本网将依法追究责任;
② 本网部分稿件来源于网络,任何单位或个人认为我考网发布的内容可能涉嫌侵犯其合法权益,应该及时向我考网书面反馈,并提供身份证明、权属证明及详细侵权情况证明,我考网在收到上述法律文件后,将会尽快移除被控侵权内容。