您好,登錄后才能下訂單哦!
這篇文章將為大家詳細(xì)講解有關(guān)C語言中怎么實現(xiàn)堆排序,文章內(nèi)容質(zhì)量較高,因此小編分享給大家做個參考,希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。
1. 堆排序
堆排序的定義及思想可以參考百度百科:
用一句概括,堆排序就是一種改進(jìn)的選擇排序,改進(jìn)的地方在于,每次做選擇的時候,不單單把最大的數(shù)字選擇出來,而且把排序過程中的一些操作進(jìn)行了記錄,這樣在后續(xù)排序中可以利用,并且有分組的思想在里面,從而提高了排序效率,其效率為O(n*logn).
2. 源代碼
堆排序中有兩個核心的操作,一個是創(chuàng)建大頂堆(或者小頂堆,這里用的是大頂堆),再一個就是對堆進(jìn)行調(diào)整。這里需要注意的是,并沒有真正的創(chuàng)建堆,只是利用完全二叉樹的特性,將其對應(yīng)到數(shù)組的下標(biāo)中(例如對于節(jié)點i,如果其存在左孩子和右孩子,那么其下標(biāo)一定是2*i, 和2*i+1)其中創(chuàng)建的時候是從下向上創(chuàng)建,而調(diào)整則是從上向下調(diào)整。
這里為了方便,堆從a[1]位置開始。
代碼運行結(jié)果如下:
源代碼如下:
#include<stdio.h> int c=0; /*heapadjust()函數(shù)的功能是實現(xiàn)從a[m]到a[n]的數(shù)據(jù)進(jìn)行調(diào)整,使其滿足大頂堆的特性*/ /*a[]是待處理的數(shù)組,m是起始坐標(biāo), n是終止坐標(biāo)*/ void heapadjust(int a[], int m, int n) { int i, temp; temp=a[m]; for(i=2*m;i<=n;i*=2)//從m的左孩子開始 { if(i+1<=n && a[i]<a[i+1])//如果左孩子小于右孩子,則將i++,這樣i的值就是最大孩子的下標(biāo)值 { i++; } if(a[i]<temp)//如果最大的孩子小于temp,則不做任何操作,退出循環(huán);否則交換a[m]和a[i]的值,將最大值放到a[i]處 { break; } a[m]=a[i]; m=i; } a[m]=temp; } void crtheap(int a[], int n)//初始化創(chuàng)建一個大頂堆 { int i; for(i=n/2; i>0; i--)//n/2為最后一個雙親節(jié)點,依次向前建立大頂堆 { heapadjust(a, i, n); } } /*swap()函數(shù)的作用是將a[i]和a[j]互換*/ void swap(int a[], int i, int j) { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; c++; } void heapsort(int a[], int n) { int i; crtheap(a, n); for(i=n; i>1; i--) { swap(a, 1, i);//將第一個數(shù),也就是從a[1]到a[i]中的最大的數(shù),放到a[i]的位置 heapadjust(a, 1, i-1);//對剩下的a[1]到a[i],再次進(jìn)行堆排序,選出最大的值,放到a[1]的位置 } } int main(void) { int i; int a[10]={-1,5,2,6,0,3,9,1,7,4}; printf("排序前:"); for(i=1;i<10;i++) { printf("%d",a[i]); } heapsort(a, 9); printf("\n\n共交換數(shù)據(jù)%d次\n\n", c); printf("排序后:"); for(i=1;i<10;i++) { printf("%d",a[i]); } printf("\n\n\n"); return 0; }
關(guān)于C語言中怎么實現(xiàn)堆排序就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,可以學(xué)到更多知識。如果覺得文章不錯,可以把它分享出去讓更多的人看到。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。