既然其它數(shù)都已經(jīng)排好,只需要排最上面一個(gè)數(shù)了,算法比較簡(jiǎn)單,一看就應(yīng)該能明白.我設(shè)計(jì)的是從A[0]....A[N-1],如果你要從A[1]...A[N]的話,把那個(gè)2*I+1,2*I+2改成2*I,2*I+1即可...
創(chuàng)新互聯(lián)長期為超過千家客戶提供的網(wǎng)站建設(shè)服務(wù)，團(tuán)隊(duì)從業(yè)經(jīng)驗(yàn)10年，關(guān)注不同地域、不同群體，并針對(duì)不同對(duì)象提供差異化的產(chǎn)品和服務(wù)；打造開放共贏平臺(tái)，與合作伙伴共同營造健康的互聯(lián)網(wǎng)生態(tài)環(huán)境。為托克托企業(yè)提供專業(yè)的網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì)，托克托網(wǎng)站改版等技術(shù)服務(wù)。擁有十多年豐富建站經(jīng)驗(yàn)和眾多成功案例,為您定制開發(fā)。
#include stdio.h
void swap(int *x, int *y){
int temp = *x;
*x = *y;
*y = temp;
}
void sift(int a[],int n){ //調(diào)整堆頂元素
int i = 0;
while(2*i+2 n){ //找出最大的與a[i]交換,如果就是本身退出循環(huán)
int max = i;
if(a[max] a[2*i+1]){
max = 2*i+1;
}
if(a[max] a[2*i+2]){
max = 2*i+2;
}
if(max == i){
break;
}
else{
swap(a[i], a[max]);
i = max;
}
}
}
int main(){
int a[8] = {10, 88, 40, 50, 76, 9, 32, 5}, i;
sift(a, 8);
for(i=0; i8; i++){
printf("%d\t", a[i]);
}
printf("\n");
return 0;
}
能構(gòu)成大根堆，因?yàn)榇蟾岩蟾?jié)點(diǎn)大于左右節(jié)點(diǎn)，且5放在根節(jié)點(diǎn)，接下來以3.4為左右孩子，然后將1.2作為3或4的孩子即可，
最大堆是堆的兩種形式之一。
根結(jié)點(diǎn)（亦稱為堆頂）的關(guān)鍵字是堆里所有結(jié)點(diǎn)關(guān)鍵字中最大者，稱為大根堆，又稱最大堆（大頂堆）。
大根堆要求根節(jié)點(diǎn)的關(guān)鍵字既大于或等于左子樹的關(guān)鍵字值，又大于或等于右子樹的關(guān)鍵字值。
//總共給你整理了7種排序算法：希爾排序，鏈?zhǔn)交鶖?shù)排序，歸并排序
//起泡排序，簡(jiǎn)單選擇排序，樹形選擇排序，堆排序,先自己看看吧，
//看不懂可以再問身邊的人或者查資料,既然可以上網(wǎng)，我相信你所在的地方信息流通方式應(yīng)該還行,所有的程序全部在VC++6.0下編譯通過
//希爾排序
#includestdio.h
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)(b))
#define LQ(a,b) ((a)=(b))
#define MAXSIZE 20 // 一個(gè)用作示例的小順序表的最大長度
typedef int KeyType; // 定義關(guān)鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void ShellInsert(SqList L,int dk)
{ // 對(duì)順序表L作一趟希爾插入排序。本算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前后記錄位置的增量是dk,而不是1;
// 2.r[0]只是暫存單元,不是哨兵。當(dāng)j=0時(shí),插入位置已找到。算法10.4
int i,j;
for(i=dk+1;i=L.length;++i)
if LT(L.r[i].key,L.r[i-dk].key)
{ // 需將L.r[i]插入有序增量子表
L.r[0]=L.r[i]; // 暫存在L.r[0]
for(j=i-dk;j0LT(L.r[0].key,L.r[j].key);j-=dk)
L.r[j+dk]=L.r[j]; // 記錄后移，查找插入位置
L.r[j+dk]=L.r[0]; // 插入
}
}
void print(SqList L)
{
int i;
for(i=1;i=L.length;i++)
printf("%d ",L.r[i].key);
printf("\n");
}
void print1(SqList L)
{
int i;
for(i=1;i=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
void ShellSort(SqList L,int dlta[],int t)
{ // 按增量序列dlta[0..t-1]對(duì)順序表L作希爾排序。算法10.5
int k;
for(k=0;kt;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量為dlta[k]的插入排序
printf("第%d趟排序結(jié)果: ",k+1);
print(L);
}
}
#define N 10
#define T 3
void main()
{
RedType d[N]=,,,,,,,,,};
SqList l;
int dt[T]=; // 增量序列數(shù)組
for(int i=0;iN;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序后: ");
print1(l);
}
/*****************************************************************/
//鏈?zhǔn)交鶖?shù)排序
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
typedef int KeyType; // 定義RedType類型的關(guān)鍵字為整型
struct RedType // 記錄類型(同c10-1.h)
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)
};
typedef char KeysType; // 定義關(guān)鍵字類型為字符型
#includestring.h
#includectype.h
#includemalloc.h // malloc()等
#includelimits.h // INT_MAX等
#includestdio.h // EOF(=^Z或F6),NULL
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h // floor(),ceil(),abs()
#includeprocess.h // exit()
#includeiostream.h // cout,cin
// 函數(shù)結(jié)果狀態(tài)代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 關(guān)鍵字項(xiàng)數(shù)的最大值
#define RADIX 10 // 關(guān)鍵字基數(shù)，此時(shí)是十進(jìn)制整數(shù)的基數(shù)
#define MAX_SPACE 1000
struct SLCell // 靜態(tài)鏈表的結(jié)點(diǎn)類型
{
KeysType keys[MAX_NUM_OF_KEY]; // 關(guān)鍵字
InfoType otheritems; // 其它數(shù)據(jù)項(xiàng)
int next;
};
struct SLList // 靜態(tài)鏈表類型
{
SLCell r[MAX_SPACE]; // 靜態(tài)鏈表的可利用空間，r[0]為頭結(jié)點(diǎn)
int keynum; // 記錄的當(dāng)前關(guān)鍵字個(gè)數(shù)
int recnum; // 靜態(tài)鏈表的當(dāng)前長度
};
typedef int ArrType[RADIX];
void InitList(SLList L,RedType D[],int n)
{ // 初始化靜態(tài)鏈表L（把數(shù)組D中的數(shù)據(jù)存于L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max為關(guān)鍵字的最大值
for(i=1;in;i++)
if(maxD[i].key)
max=D[i].key;
L.keynum=int(ceil(log10(max)));
L.recnum=n;
for(i=1;i=n;i++)
{
L.r[i].otheritems=D[i-1].otherinfo;
itoa(D[i-1].key,c,10); // 將10進(jìn)制整型轉(zhuǎn)化為字符型,存入c
for(j=strlen(c);jL.keynum;j++) // 若c的長度max的位數(shù),在c前補(bǔ)'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;jL.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}
int ord(char c)
{ // 返回k的映射(個(gè)位整數(shù))
return c-'0';
}
void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 算法10.15
{ // 靜態(tài)鍵表L的r域中記錄已按(keys[0],…,keys[i-1])有序。本算法按
// 第i個(gè)關(guān)鍵字keys[i]建立RADIX個(gè)子表,使同一子表中記錄的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個(gè)和最后一個(gè)記錄
int j,p;
for(j=0;jRADIX;++j)
f[j]=0; // 各子表初始化為空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord將記錄中第i個(gè)關(guān)鍵字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 將p所指的結(jié)點(diǎn)插入第j個(gè)子表中
}
}
int succ(int i)
{ // 求后繼函數(shù)
return ++i;
}
void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成
// 一個(gè)鏈表，e[0..RADIX-1]為各子表的尾指針。算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一個(gè)非空子表，succ為求后繼函數(shù)
r[0].next=f[j];
t=e[j]; // r[0].next指向第一個(gè)非空子表中第一個(gè)結(jié)點(diǎn)
while(jRADIX-1)
{
for(j=succ(j);jRADIX-1!f[j];j=succ(j)); // 找下一個(gè)非空子表
if(f[j])
{ // 鏈接兩個(gè)非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最后一個(gè)非空子表中的最后一個(gè)結(jié)點(diǎn)
}
void printl(SLList L)
{ // 按鏈表輸出靜態(tài)鏈表
int i=L.r[0].next,j;
while(i)
{
for(j=L.keynum-1;j=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" ");
i=L.r[i].next;
}
}
void RadixSort(SLList L)
{ // L是采用靜態(tài)鏈表表示的順序表。對(duì)L作基數(shù)排序，使得L成為按關(guān)鍵字
// 自小到大的有序靜態(tài)鏈表，L.r[0]為頭結(jié)點(diǎn)。算法10.17
int i;
ArrType f,e;
for(i=0;iL.recnum;++i)
L.r[i].next=i+1;
L.r[L.recnum].next=0; // 將L改造為靜態(tài)鏈表
for(i=0;iL.keynum;++i)
{ // 按最低位優(yōu)先依次對(duì)各關(guān)鍵字進(jìn)行分配和收集
Distribute(L.r,i,f,e); // 第i趟分配
Collect(L.r,f,e); // 第i趟收集
printf("第%d趟收集后:\n",i+1);
printl(L);
printf("\n");
}
}
void print(SLList L)
{ // 按數(shù)組序號(hào)輸出靜態(tài)鏈表
int i,j;
printf("keynum=%d recnum=%d\n",L.keynum,L.recnum);
for(i=1;i=L.recnum;i++)
{
printf("keys=");
for(j=L.keynum-1;j=0;j--)
printf("%c",L.r[i].keys[j]);
printf(" otheritems=%d next=%d\n",L.r[i].otheritems,L.r[i].next);
}
}
void Sort(SLList L,int adr[]) // 改此句(類型)
{ // 求得adr[1..L.length]，adr[i]為靜態(tài)鏈表L的第i個(gè)最小記錄的序號(hào)
int i=1,p=L.r[0].next;
while(p)
{
adr[i++]=p;
p=L.r[p].next;
}
}
void Rearrange(SLList L,int adr[]) // 改此句(類型)
{ // adr給出靜態(tài)鏈表L的有序次序，即L.r[adr[i]]是第i小的記錄。
// 本算法按adr重排L.r，使其有序。算法10.18(L的類型有變)
int i,j,k;
for(i=1;iL.recnum;++i) // 改此句(類型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暫存記錄L.r[i]
while(adr[j]!=i)
{ // 調(diào)整L.r[adr[j]]的記錄到位直到adr[j]=i為止
k=adr[j];
L.r[j]=L.r[k];
adr[j]=j;
j=k; // 記錄按序到位
}
L.r[j]=L.r[0];
adr[j]=j;
}
}
#define N 10
void main()
{
RedType d[N]=,,,,,,,,,};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域還沒賦值):\n");
print(l);
RadixSort(l);
printf("排序后(靜態(tài)鏈表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序后(重排記錄):\n");
print(l);
}
/*******************************************/
//歸并排序
#includestdio.h
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)(b))
#define LQ(a,b) ((a)=(b))
#define MAXSIZE 20 // 一個(gè)用作示例的小順序表的最大長度
typedef int KeyType; // 定義關(guān)鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void Merge(RedType SR[],RedType TR[],int i,int m,int n)
{ // 將有序的SR[i..m]和SR[m+1..n]歸并為有序的TR[i..n] 算法10.12
int j,k,l;
for(j=m+1,k=i;i=mj=n;++k) // 將SR中記錄由小到大地并入TR
if LQ(SR[i].key,SR[j].key)
TR[k]=SR[i++];
else
TR[k]=SR[j++];
if(i=m)
for(l=0;l=m-i;l++)
TR[k+l]=SR[i+l]; // 將剩余的SR[i..m]復(fù)制到TR
if(j=n)
for(l=0;l=n-j;l++)
TR[k+l]=SR[j+l]; // 將剩余的SR[j..n]復(fù)制到TR
}
void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 將SR[s..t]歸并排序?yàn)門R1[s..t]。算法10.13
int m;
RedType TR2[MAXSIZE+1];
if(s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2; // 將SR[s..t]平分為SR[s..m]和SR[m+1..t]
MSort(SR,TR2,s,m); // 遞歸地將SR[s..m]歸并為有序的TR2[s..m]
MSort(SR,TR2,m+1,t); // 遞歸地將SR[m+1..t]歸并為有序的TR2[m+1..t]
Merge(TR2,TR1,s,m,t); // 將TR2[s..m]和TR2[m+1..t]歸并到TR1[s..t]
}
}
void MergeSort(SqList L)
{ // 對(duì)順序表L作歸并排序。算法10.14
MSort(L.r,L.r,1,L.length);
}
void print(SqList L)
{
int i;
for(i=1;i=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 7
void main()
{
RedType d[N]=,,,,,,};
SqList l;
int i;
for(i=0;iN;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序后:\n");
print(l);
}
/**********************************************/
//起泡排序
#includestring.h
#includectype.h
#includemalloc.h // malloc()等
#includelimits.h // INT_MAX等
#includestdio.h // EOF(=^Z或F6),NULL
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h // floor(),ceil(),abs()
#includeprocess.h // exit()
#includeiostream.h // cout,cin
// 函數(shù)結(jié)果狀態(tài)代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status;
typedef int Boolean;
#define N 8
void bubble_sort(int a[],int n)
{ // 將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i1change;--i)
{
change=FALSE;
for(j=0;ji;++j)
if(a[j]a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
change=TRUE;
}
}
}
void print(int r[],int n)
{
int i;
for(i=0;in;i++)
printf("%d ",r[i]);
printf("\n");
}
void main()
{
int d[N]=;
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序后:\n");
print(d,N);
}
/****************************************************/
//簡(jiǎn)單選擇排序
#includestdio.h
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
#define MAXSIZE 20 // 一個(gè)用作示例的小順序表的最大長度
typedef int KeyType; // 定義關(guān)鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的記錄的序號(hào)
KeyType min;
int j,k;
k=i; // 設(shè)第i個(gè)為最小
min=L.r[i].key;
for(j=i+1;j=L.length;j++)
if(L.r[j].keymin) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}
void SelectSort(SqList L)
{ // 對(duì)順序表L作簡(jiǎn)單選擇排序。算法10.9
int i,j;
RedType t;
for(i=1;iL.length;++i)
{ // 選擇第i小的記錄，并交換到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中選擇key最小的記錄
if(i!=j)
{ // 與第i個(gè)記錄交換
t=L.r[i];
L.r[i]=L.r[j];
L.r[j]=t;
}
}
}
void print(SqList L)
{
int i;
for(i=1;i=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]=,,,,,,,};
SqList l;
int i;
for(i=0;iN;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序后:\n");
print(l);
}
/************************************************/
//樹形選擇排序
#includestring.h
#includectype.h
#includemalloc.h // malloc()等
#includelimits.h // INT_MAX等
#includestdio.h // EOF(=^Z或F6),NULL
#includestdlib.h // atoi()
#includeio.h // eof()
#includemath.h // floor(),ceil(),abs()
#includeprocess.h // exit()
#includeiostream.h // cout,cin
// 函數(shù)結(jié)果狀態(tài)代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
#define MAXSIZE 20 // 一個(gè)用作示例的小順序表的最大長度
typedef int KeyType; // 定義關(guān)鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void TreeSort(SqList L)
{ // 樹形選擇排序
int i,j,j1,k,k1,l,n=L.length;
RedType *t;
l=(int)ceil(log(n)/log(2))+1; // 完全二叉樹的層數(shù)
k=(int)pow(2,l)-1; // l層完全二叉樹的結(jié)點(diǎn)總數(shù)
k1=(int)pow(2,l-1)-1; // l-1層完全二叉樹的結(jié)點(diǎn)總數(shù)
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉樹采用順序存儲(chǔ)結(jié)構(gòu)
for(i=1;i=n;i++) // 將L.r賦給葉子結(jié)點(diǎn)
t[k1+i-1]=L.r[i];
for(i=k1+n;ik;i++) // 給多余的葉子的關(guān)鍵字賦無窮大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 給非葉子結(jié)點(diǎn)賦值
for(i=j1;ij;i+=2)
t[i].keyt[i+1].key?(t[(i+1)/2-1]=t[i]):(t[(i+1)/2-1]=t[i+1]);
j=j1;
j1=(j1-1)/2;
}
for(i=0;in;i++)
{
L.r[i+1]=t[0]; // 將當(dāng)前最小值賦給L.r[i]
j1=0;
for(j=1;jl;j++) // 沿樹根找結(jié)點(diǎn)t[0]在葉子中的序號(hào)j1
t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);
t[j1].key=INT_MAX;
while(j1)
{
j1=(j1+1)/2-1; // 序號(hào)為j1的結(jié)點(diǎn)的雙親結(jié)點(diǎn)序號(hào)
t[2*j1+1].key=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);
}
}
free(t);
}
void print(SqList L)
{
int i;
for(i=1;i=L.length;i++)
printf("(%d,%d)",L.r[i].key,L.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]=,,,,,,,};
SqList l;
int i;
for(i=0;iN;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序后:\n");
print(l);
}
/****************************/
//堆排序
#includestdio.h
typedef int InfoType; // 定義其它數(shù)據(jù)項(xiàng)的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)(b))
#define LQ(a,b) ((a)=(b))
#define MAXSIZE 20 // 一個(gè)用作示例的小順序表的最大長度
typedef int KeyType; // 定義關(guān)鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關(guān)鍵字項(xiàng)
InfoType otherinfo; // 其它數(shù)據(jù)項(xiàng)，具體類型在主程中定義
};
struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
typedef SqList HeapType; // 堆采用順序表存儲(chǔ)表示
void HeapAdjust(HeapType H,int s,int m) // 算法10.10
{ // 已知H.r[s..m]中記錄的關(guān)鍵字除H.r[s].key之外均滿足堆的定義，本函數(shù)
// 調(diào)整H.r[s]的關(guān)鍵字,使H.r[s..m]成為一個(gè)大頂堆(對(duì)其中記錄的關(guān)鍵字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j=m;j*=2)
{ // 沿key較大的孩子結(jié)點(diǎn)向下篩選
if(jmLT(H.r[j].key,H.r[j+1].key))
++j; // j為key較大的記錄的下標(biāo)
if(!LT(rc.key,H.r[j].key))
break; // rc應(yīng)插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}
void HeapSort(HeapType H)
{ // 對(duì)順序表H進(jìn)行堆排序。算法10.11
RedType t;
int i;
for(i=H.length/2;i0;--i) // 把H.r[1..H.length]建成大頂堆
HeapAdjust(H,i,H.length);
for(i=H.length;i1;--i)
{ // 將堆頂記錄和當(dāng)前未經(jīng)排序子序列H.r[1..i]中最后一個(gè)記錄相互交換
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 將H.r[1..i-1]重新調(diào)整為大頂堆
}
}
void print(HeapType H)
{
int i;
for(i=1;i=H.length;i++)
printf("(%d,%d)",H.r[i].key,H.r[i].otherinfo);
printf("\n");
}
#define N 8
void main()
{
RedType d[N]=,,,,,,,};
HeapType h;
int i;
for(i=0;iN;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序后:\n");
print(h);
}
重慶分公司
重慶分公司
