1. 怎樣用c語言中堆排序實現一個數組a[10]的排序
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int sort_function( const void *a, const void *b);
char list[5][4] = { "cat", "car", "cab", "cap", "can" };
int main(void)
{
int x;
qsort((void *)list, 5, sizeof(list[0]), sort_function); // 調用快速排序
for (x = 0; x < 5; x++)
printf("%s\n", list[x]);
return 0;
}
int sort_function( const void *a, const void *b)
{ //自已要定義一個簡單的比較函數就可
return( strcmp((char *)a,(char *)b) );
}
// C++中自身有一個通用的快速 qsort,可以用它 ,自已要定義一個簡單的比較函數就可
2. 跪求大神用C語言編程堆排序 不是快速（冒泡）排序！！
void HeapSortData(int SortData[], int Length)
{
int i=0;
//將Hr[0,Lenght-1]建成大根堆
for (i=Length/2-1; i>=0; i--)
{
HeapAdjust(SortData, i, Length);
}
for (i=Length-1; i>0; i--)
{
//與最後一個記錄交換
int tmpData =SortData[0];
SortData[0] =SortData[i];
SortData[i] =tmpData;
//將H.r[0..i]重新調整為大根堆
HeapAdjust(SortData, 0, i);
}
return;
}
3. 希爾排序，選擇排序，插入排序，堆排序的c語言實現
希爾排序演算法
void Shellinsert ( SqList &L, int dk ) {
// 對順序表 L 作一趟希爾插入排序。此演算法和一趟直接插入排序相比，作了以下修改：
// (1) 前後記錄為止的增量是 dk，而不是 1；
// (2) r[0] 只是暫存單元，而不是哨兵。當 j <= 0 時，插入位置已經找到。
for ( i = dk+1; i <=L.length; ++i )
if ( 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; j > 0 && ( L.r[0].key < L.r[j].key ); j -= dk )
L.r[j+dk] = L.r[j]; // 記錄後移，查找插入位置
L.r[j+dk] = L.r[0]; // 插入到正確位置
} // if 結束
} // ShellInsert
4. C語言堆排序 幾個不明白的地方。高手幫忙啊！~
這里為什麼是i=n/2-1，初學者可能會不明白。
你這樣考慮。
首先對於葉子節點，我們沒有必要進行維護操作，也就是沒有必要調用你的HeapAdjust
函數
為什麼呢？因為葉子節點沒有孩子。就算調用了，也不起作用。
所以你應該從n/2-1下標所對應的節點開始，一直維護到0下標對於的節點。
n/2-1是編號最大的非葉子節點，而0號節點是根節點
至於這里為什麼是--i，因為這里是自低向上的維護，最後一個維護的必然是根節點。
實際上這兩句話的作用是建堆。
for(i=n/2-1;i>=0;--i)
HeapAdjust(data,i,n-1);
我畫了個草圖
5. 數據結構（C語言版） 堆排序
#include<stdio.h>
#include<stdlib.h>
#include <math.h>
#define L 8 //排序元素個數
#define FALSE 0
#define TRUE 1
typedef struct
{
int key;
char otherinfo;
}RecType;
typedef RecType Seqlist[L+1];
int num; //定義排序趟數的全局變數
Seqlist R;
//直接插入排序
void Insertsort()
{
int i,j,k,m=0;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=2;i<=L;i++)
{
if(R[i].key<R[i-1].key)
{
R[0]=R[i];
j=i-1;
while(R[0].key<R[j].key)
{
R[j+1]=R[j];
j--;
}
R[j+1]=R[0];
}
m++;
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//希爾排序
void Shellsort()
{
int i,j,gap,x,m=0,k;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
gap=L/2;
while(gap>0)
{
for(i=gap+1;i<=L;i++)
{
j=i-gap;
while(j>0)
{
if(R[j].key>R[j+gap].key)
{
x=R[j].key;
R[j].key=R[j+gap].key;
R[j+gap].key=x;
j=j-gap;
}
else
{
j=0;
}
}
}
gap=gap/2;
m++;
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//冒泡排序
void Bubblesort()
{
int i,j,k;
int exchange;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
exchange=FALSE;
for(j=L;j>=i+1;j--)
{
if(R[j].key<R[j-1].key)
{
R[0].key=R[j].key;
R[j].key=R[j-1].key;
R[j-1].key=R[0].key;
exchange=TRUE;
}
}
if(exchange)
{
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
}
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
int Partition(int i,int j) //i和j為形式參數，分別代表low和high
{
RecType pirot=R[i];
while(i<j)
{
while(i<j&&R[j].key>=pirot.key)
{
j--;
}
if(i<j)
{
R[i++]=R[j];
}
while(i<j&&R[j].key<=pirot.key)
{
i++;
}
if(i<j)
{
R[j--]=R[i];
}
}
R[i]=pirot;
return i;
}
//遞歸排序
void Quicksort(int low,int high)
{
int pirotpos,k;
if(low<high)
{
pirotpos=Partition(low,high);
num++;
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",num);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
Quicksort(low,pirotpos-1);
Quicksort(pirotpos+1,high);
}
}
//選擇排序
void Selectsort()
{
int i,j,k,h;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(i=1;i<L;i++)
{
h=i;
for(j=i+1;j<=L;j++)
{
if(R[j].key<R[h].key)
{
h=j;
}
}
if(h!=j)
{
R[0]=R[i];
R[i]=R[h];
R[h]=R[0];
}
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",i);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
void Merge(int low,int mm,int high)
{
int i=low,j=mm+1,p=0;
RecType *R1;
R1=new RecType[high-low+1];
if(!R1)
{
printf("內存不足！");
}
while(i<=mm&&j<=high)
{
R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
}
while(i<=mm)
{
R1[p++]=R[i++];
}
while(j<=high)
{
R1[p++]=R[j++];
}
for(p=0,i=low;i<=high;p++,i++)
{
R[i]=R1[p];
}
}
void MergePass(int length)
{
int i;
for(i=1;i+2*length-1<=L;i=i+2*length)
{
Merge(i,i+length-1,i+2*length-1);
}
if(i+length-1<L)
{
Merge(i,i+length-1,L);
}
}
//歸並排序
void Mergesort()
{
int length,k,m=0,i;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
for(length=1;length<L;length*=2)
{
MergePass(length);
m++;
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",m);
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
}
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
//堆建
void CreateHeap(int root,int index)
{
int j,temp,finish;
j=2*root;
temp=R[root].key;
finish=0;
while(j<=index&&finish==0)
{
if(j<index)
{
if(R[j].key<R[j+1].key)
{
j++;
}
}
if(temp>=R[j].key)
{
finish=1;
}
else
{
R[j/2].key=R[j].key;
j=j*2;
}
}
R[j/2].key=temp;
}
//堆排序
void Heapsort()
{
int i,j,temp,k;
for(i=(L/2);i>=1;i--)
{
CreateHeap(i,L);
}
for(i=L-1,k=1;i>=1;i--,k++)
{
temp=R[i+1].key;
R[i+1].key=R[1].key;
R[1].key=temp;
CreateHeap(1,i);
printf("\t\t第%d趟排序的結果為（按回車鍵開始排序）：\n\t\t",k);
for(j=1;j<=L;j++)
{
printf("%5d",R[j].key);
}
getchar();
printf("\n");
}
}
void Heap()
{
int i;
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
getchar();
printf("\n");
Heapsort();
printf("\n\t\t排序最終結果是：\n\t\t");
for(i=1;i<=L;i++)
{
printf("%5d",R[i].key);
}
printf("\n");
}
main()
{
Seqlist S;
int i,k;
char ch1,ch2,q;
printf("\n\t\t請輸入%d個待排序的數據（按回車鍵分隔）：\n\t\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t數據輸入完畢！");
ch1='y';
while(ch1=='y'||ch1=='Y')
{
printf("\n");
printf("\n\t\t 排 序 子 系 統 \n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t* 1--------更新排序數據 *\n");
printf("\n\t\t* 2--------直接插入排序 *\n");
printf("\n\t\t* 3--------希 爾 排 序 *\n");
printf("\n\t\t* 4--------冒 泡 排 序 *\n");
printf("\n\t\t* 5--------快 速 排 序 *\n");
printf("\n\t\t* 6--------選 擇 排 序 *\n");
printf("\n\t\t* 7--------歸 並 排 序 *\n");
printf("\n\t\t* 8--------堆 排 序 *\n");
printf("\n\t\t* 0--------退 出 *\n");
printf("\n\t\t*******************************************\n");
printf("\n\t\t請選擇菜單號（0到8）");
scanf("%c",&ch2);
getchar();
for(i=1;i<=L;i++)
{
R[i].key=S[i].key;
}
switch(ch2)
{
case '1':
printf("\n\t\t請輸入%d個待排序數據（按回車鍵分隔）\n\t\t",L);
for(i=1;i<=L;i++)
{
scanf("%d",&S[i].key);
getchar();
printf("\t\t");
}
printf("\n\t\t數據輸入完畢！");
break;
case '2':
Insertsort();
break;
case '3':
Shellsort();
break;
case '4':
Bubblesort();
break;
case '5':
printf("\n\t\t原始數據為（按回車鍵開始排序）：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
getchar();
printf("\n");
num=0;
Quicksort(1,L);
printf("\n\t\t排序最終結果是：\n\t\t");
for(k=1;k<=L;k++)
{
printf("%5d",R[k].key);
}
printf("\n");
break;
case '6':
Selectsort();
break;
case '7':
Mergesort();
break;
case '8':
Heap();
break;
case '0':
ch1='n';
break;
default:
system("cls");
printf("\n\t\t對不起，您輸入有誤，請重新輸入！\n");
break;
}
if(ch2!='0')
{
if(ch2=='2'||ch2=='3'||ch2=='4'||ch2=='5'||ch2=='6'||ch2=='7'||ch2=='8')
{
printf("\n\n\t\t排序完畢！");
printf("\n\t\t按回車鍵繼續！");
q=getchar();
if(q!='\xA')
{
getchar();
ch1='n';
}
}
}
}
}
6. 請問c語言中的 堆排序 原理是什麼，最好有個例子說明一下，謝謝！
如果是最大堆，那麼堆頂元素就是最大的。並且它是一種二叉樹的形式。因此它的左右子樹也是一個最大堆。也就說左子樹和右子樹的根都是當前子樹中最大的元素。堆排序的原理就是維護一個最大堆。可以詳見數據結構書，那段代碼寫的相當簡潔易懂。初始化堆時，要弄明白為什麼是更新一半的元素。你可以在紙上畫一畫，對每一個元素從二叉樹上從1開始標號。會發現標號為1 ， 2，..n/2 的結點剛好可以覆蓋二叉樹的所有路徑，並且是從 n/2 到 1 去更新堆，這樣的話就可以構成一個初始化的最大堆。每次更新最大堆時，都是沿著左右子樹的路徑一次更新，要左右子結點較大的元素往上移動，知道更新的元素大於左右子樹的結點值。那麼就成了一個新的最大堆。復雜度就是二叉樹數的層數。即每次更新復雜度是log(n).
7. c語言 堆排序演算法升序排列N個數
#include<cstdio>
intarr[120000];
intmain()
{
intT,n;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(inti=1;i<=n;i++)
scanf("%d",&arr[i]);
sort(arr+1,arr+n+1);
for(inti=1;i<=n;i++)
printf("%d%c",arr[i],i==n?' ':'';
}
return0;
}
8. C語言堆排序法誰能通俗易懂又清晰地講解一下謝謝
您可以找本數據結構的書看看，比如清華嚴尉敏的《數據結構》
以下摘抄於 http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.4.2.1.htm 這個網站的講解挺不錯，您可以看看
1、 堆排序定義
n個關鍵字序列Kl，K2，…，Kn稱為堆，當且僅當該序列滿足如下性質(簡稱為堆性質)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )
若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉結點的關鍵字均不大於(或不小於)其左右孩子(若存在)結點的關鍵字。
3、堆排序特點
堆排序(HeapSort)是一樹形選擇排序。
堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系【參見二叉樹的順序存儲結構】，在當前無序區中選擇關鍵字最大(或最小)的記錄。
5、堆排序
堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
（1）用大根堆排序的基本思想
① 先將初始文件R[1..n]建成一個大根堆，此堆為初始的無序區
② 再將關鍵字最大的記錄R[1](即堆頂)和無序區的最後一個記錄R[n]交換，由此得到新的無序區R[1..n-1]和有序區R[n]，且滿足R[1..n-1].keys≤R[n].key
③由於交換後新的根R[1]可能違反堆性質，故應將當前無序區R[1..n-1]調整為堆。然後再次將R[1..n-1]中關鍵字最大的記錄R[1]和該區間的最後一個記錄R[n-1]交換，由此得到新的無序區R[1..n-2]和有序區R[n-1..n]，且仍滿足關系R[1..n-2].keys≤R[n-1..n].keys，同樣要將R[1..n-2]調整為堆。
……
直到無序區只有一個元素為止。
（2）大根堆排序演算法的基本操作：
① 初始化操作：將R[1..n]構造為初始堆；
② 每一趟排序的基本操作：將當前無序區的堆頂記錄R[1]和該區間的最後一個記錄交換，然後將新的無序區調整為堆(亦稱重建堆)。
注意：
①只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
②用小根堆排序與利用大根堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻，堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由後往前逐步擴大至整個向量為止。
（3）堆排序的演算法：
void HeapSort(SeqIAst R)
{ //對R[1..n]進行堆排序，不妨用R[0]做暫存單元
int i；
BuildHeap(R)； //將R[1-n]建成初始堆
for(i=n;i>1；i--){ //對當前無序區R[1..i]進行堆排序，共做n-1趟。
R[0]=R[1]；R[1]=R[i];R[i]=R[0]； //將堆頂和堆中最後一個記錄交換
Heapify(R，1，i-1)； //將R[1..i-1]重新調整為堆，僅有R[1]可能違反堆性質
} //endfor
} //HeapSort
9. 計算機C語言的堆排序原理，最好是一個排序的例子，舉數據進行現場排序
#include<stdio.h>
#define N 6
int j,k;
//建堆函數
void build(int *a,int i,int n){
int tmp;
k=i;
j=2*k+1;
while(j<=n){
if((j<n)&&a[j]<a[j+1])
j++;
if(a[k]>=a[j])
break;
tmp=a[k];
a[k]=a[j];
a[j]=tmp;
k=j;
j=2*j+1;
}
}
//列印數組元素
void prnt(int *a,int n){
int i;
printf("\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
printf("\n");
}
//列印堆函數
void prnthp(int *a,int b1,int b2){
int size;
int h=0,sum=0,item=1;
int i,j,cnt,start,tmp;
size=b2-b1+1;
while(sum<=size){
sum+=item;
h++;
item*=2;
}
item=1;
cnt=0;
start=b1;
tmp=1;
printf("\n========================================\n");
printf(" 堆：\n");
while(1){
for(i=0;i<h;i++){
for(j=0;j<h-i;j++)
printf(" ");
/* for(j=0;j<i+1;j++)
printf(" ");*/
for(j=0;j<tmp;j++){
if(cnt>size-1)
goto end;
printf("%4d",a[cnt++]);
}
printf("\n");
tmp*=2;
}
}
end:
printf("\n");
}
//列印排序好地數組
void prntar(int *a,int b2,int len){
int i;
printf(" 已排序： \n");
for(i=0;i<b2;i++)
printf(" ");
for(i=b2;i<=len;i++)
printf("%d ",a[i]);
printf("\n");
}
int main(){
int a[50];
int i;
int tmp;
int sum;
int len;
printf(" 堆排序\n");
printf("\n=============================================\n");
printf("\n請輸入堆排序的數組元素個數，回車結束:\n");
scanf("%d",&len);
printf("\n請輸入待排序的數組以回車結束：\n");
for(i=0;i<len;i++)
scanf("%d",&a[i]);
tmp=1;sum=0;
while (sum+tmp<=len){
sum+=tmp;
tmp*=2;
}
printf("\n==============================================================\n");
printf("\n 初始數組：\n");
prnt(a,len);
for(i=sum-1;i>=0;i--)
build(a,i,len-1);
prnthp(a,0,len-1);
for(i=0;i<len-1;i++){
tmp=a[0];
a[0]=a[len-1-i];
a[len-1-i]=tmp;
build(a,0,len-2-i);
prnthp(a,0,len-2-i);
prntar(a,len-1-i,len-1);
}
printf("\n===================================\n");
printf("\n 排序結果：\n");
prnt(a,len);
printf("\n=======================================\n");
return 0;
}
10. c語言堆排序代碼
#include<stdio.h>
void shift(int a[] , int i , int m)
{
int k , t;
t = a[i]; k = 2 * i + 1;
while (k < m)
{
if ((k < m - 1) && (a[k] < a[k+1])) k ++;
if (t < a[k]) {a[i] = a[k]; i = k; k = 2 * i + 1;}
else break;
}
a[i] = t;
}
void heap(int a[] , int n) //a 為排序數組，n為數組大小（編號0-n-1）
{
int i , k;
for (i = n/2-1; i >= 0; i --) shift(a , i , n);
for (i = n-1; i >= 1; i --)
{
k = a[0]; a[0] = a[i]; a[i] = k;
shift(a , 0 , i);
}
}
void main()
{
int a[10],i;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
heap(a,10);
for(i=0;i<10;i++)
printf("%d",a[i]);
}