c語言堆排序
『壹』 【急求】c語言中堆排序如何輸出排序前各數字的序號
最簡單的辦法：再增加一個數組int d0[13]={0,1,2,3,4,5,6,7,8,9,10,11,12}
當交換data數組中data[i]和data[j]時，同步地交換d0數組中d0[i]和d0[j]就可以了。這樣當排序完成後，數據data[k]的排序前序號就是d0[k]。
『貳』 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]);
}
『叄』 怎樣用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,可以用它 ,自已要定義一個簡單的比較函數就可
『肆』 c語言中排序的方法有哪些
排序演算法和語言沒有什麼關系，一般來說面試，考試就是那些
快速排序
冒泡排序
堆排序
『伍』 C語言排序演算法一共多少種
選擇排序
#include<iostream>
usingnamespacestd;
voidselect_sort(intarr[],intnum);
voidoutput_array(intarr[],intnum);
intmain()
{
inta[10];
for(inti=0;i<10;i++)
{
cin>>a[i];
}
select_sort(a,10);
output_array(a,10);
return0;
}
voidselect_sort(intarray[],intn)//形參array是數組名
{
inti,j,k,t;
for(i=0;i<n-1;i++)
{
k=i;//先設第i個就為最小
for(j=i+1;j<n;j++)
if(array[j]<array[k])
k=j;//通過循環，得到k為最小
t=array[k];//交換a[i]和a[k]
array[k]=array[i];
array[i]=t;
}
return;
}
voidoutput_array(intarr[],intnum)
{
inti;
for(i=0;i<num;i++)
{
cout<<arr[i];
cout<<endl;
}
return;
}
2.冒泡排序
#include<stdio.h>
intmain()
{
inti,j,a[10],t;
for(i=0;i<10;i++)
scanf("%d",&a[i]);
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]>a[j])
{
t=a[j];
a[j]=a[i];
a[i]=t;
}
for(i=0;i<10;i++)
printf("%d",a[i]);
return0;
}
3.堆排序
#include<iostream>
usingnamespacestd;
voidpaii(inta[20],inti,intm)
{
intk,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;
}
elsebreak;
}
a[i]=t;
}
voidipai(inta[20],intn)
{
inti,k;
for(i=n/2-1;i>=0;i--)
paii(a,i,n);
for(i=n-1;i>=1;i--)
{
k=a[0];
a[0]=a[i];
a[i]=k;
paii(a,0,i);
}}
intmain()
{
inta[10],i;
for(i=0;i<10;i++)
cin>>a[i];
ipai(a,10);
for(i=0;i<10;i++)
cout<<a[i]<<endl;
}
4.快速排序
#include<iostream>
usingnamespacestd;
voidQuicksort(inta[],intlow,inthigh)
{
if(low>=high)
{
return;
}
intfirst=low;
intlast=high;
intkey=a[first];
while(first<last)
{
while(first<last&&a[last]>=key)
--last;
a[first]=a[last];
while(first<last&&a[first]<=key)
++first;
a[last]=a[first];
}
a[first]=key;
Quicksort(a,low,first-1);
Quicksort(a,last+1,high);
}
intmain()
{
inti,a[100],x,n=0;
while(cin>>x)
{
a[n]=x;
n++;
}
n--;
Quicksort(a,0,n);
for(i=0;i<=n;i++)
cout<<a[i]<<"";
cout<<endl;
return0;
}
5. 基數排序
#include<stdio.h>
#include<stdlib.h>
intmain(){
intdata[10]={73,22,93,43,55,14,82,65,39,81};//對十個數進行排序
inttemp[10][10]={0};//構造一個臨時二維數組，其值為0
intorder[10]={0};//構造一維數組，其值為0
inti,j,k,n,lsd;
k=0;n=1;
for(i=0;i<10;i++)printf("%d",data[i]);//在排序前，對這10個數列印一遍
putchar(' ');
while(n<=10){
for(i=0;i<10;i++){
lsd=((data[i]/n)%10);//lsd先對個位取余，然後再對十位取余，注意循環
temp[lsd][order[lsd]]=data[i];//temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯
order[lsd]++;//需要區分的是lsd和order[lsd]，這兩個不是一樣的概念嗷
}
printf(" 重新排列:");
for(i=0;i<10;i++){
if(order[i]!=0)
for(j=0;j<order[i];j++){
data[k]=temp[i][j];
printf("%d",data[k]);
k++;
}
order[i]=0;
}
n*=10;//第二次用十位
k=0;
}
putchar(' ');
printf(" 排序後:");
for(i=0;i<10;i++)printf("%d",data[i]);
return0;
}
6.希爾排序
#include<iostream>
usingnamespacestd;
voidshell_sort(inta[],intn);
intmain()
{
intn,a[10000];
cin>>n;
for(inty=0;y<n;y++)
cin>>a[y];
shell_sort(a,n);
for(inti=0;i<n;i++)
cout<<a[i]<<"";
cout<<endl;
}
voidshell_sort(inta[],intn)
{
intgap,k,temp;//定義增量；
for(gap=3;gap>0;gap--)//設置初始增量，遞減；
{
for(inti=0;i<gap;i++)//按增量分組；
{
for(intj=i+gap;j<n;j=j+gap)//每組分別比較大小；
{
if(a[j]<a[j-gap])
{
temp=a[j];
k=j-gap;
while(k>=0&&a[k]>temp)
{
a[k+gap]=a[k];
k=k-gap;
}
a[k+gap]=temp;
}
}
}
}
}
7.歸並排序
#include<iostream>
usingnamespacestd;
voidMergeSort(intp[],ints,intm,intt)
{
intq[100];//q[100]用來存放排好的序列
inti=s;
intj=m+1;
intk=s;
while(i<=m&&j<=t)
{
if(p[i]<=p[j])
q[k++]=p[i++];
else
q[k++]=p[j++];
}
if(i<=m)
while(i<=m)
q[k++]=p[i++];
elsewhile(j<=t)
q[k++]=p[j++];
for(intn=s;n<=t;n++)
p[n]=q[n];
}
voidMerge(intp[],ints,intt)
{
if(s<t)
{
intm=(s+t)/2;//將數組分成兩半
Merge(p,s,m);//遞歸拆分左數組
Merge(p,m+1,t);//遞歸拆分右數組
MergeSort(p,s,m,t);//合並數組
}
}
intmain()
{
intn;
intp[100];
cin>>n;
for(inti=0;i<n;i++)
cin>>p[i];
Merge(p,0,n-1);
for(intj=0;j<n;j++)
cout<<p[j]<<"";
cout<<endl;
return0;
}
排序方法基本就這些，還有雙向冒泡這種拓展的排序方法，還有直接排序如桶排序
『陸』 C語言中的堆排序結果是O(nlog2n) ，怎麼計算得來的
其中的一個對比大小的操作是2分的思想是logn的，也就是說每次提取最值得操作是logn的要進行n次這樣的操作就是nlogn
『柒』 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;
}
『捌』 C語言堆排序最壞的情況下比較次數最多要多少次
O(n1og2n)在最壞情況下，冒泡排序所需要的比較次數為n(n－1)/／2；簡單插入排序所需要的比較次數為n(n－1)/2；希爾排序所需要盼的比較次數為0(n1.5)；堆排序所需要的比較次數為0(nlog2n)。
『玖』 數據結構的堆排序
堆排序（C語言版）2010-03-15 23:24/*簡述：
所謂堆排序，就是就是將所要排序的數以二叉樹的形式存儲。其中，有根的元素值大於其孩子結點。一直遞歸下去，每當取出最大的元素，考量其左右子樹，以保持其根節點最大的性質不變。這個演算法的時間復雜性是O（n log2 n）。證明略。 */
#include<stdio.h>
#define max_size 10//數組元素個數
#include<stdlib.h>
int heap_size;//當前堆中的元素數目
void MAX_HEAPFY(int A[], int i) {
int left, right, temp, largest;
left = 2*i;//
right = 2*i + 1;
if( left <= heap_size && A[i] < A[left] )
largest = left;
else largest = i;
if( right <= heap_size && A[right] > A[largest])
largest = right;
if(largest != i) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;
MAX_HEAPFY(A, largest);
}
}
void BUILD_MAX_HEAP(int A[]) {
//這個函數是用來產生最大堆的
int i;
heap_size = max_size-1;
for( i = (max_size-1)/2; i != 0; i--) {
MAX_HEAPFY(A, i);
printf("*****\n");
}
}
void HEAP_SORT(int A[]) {
int i, temp;
BUILD_MAX_HEAP(A);
for( i = (max_size-1); i != 1; i--) {
temp = A[1];
A[1] = A[i];
A[i] = temp;
--heap_size;
MAX_HEAPFY(A, 1);
}
}
int main()
{
int i;
int A[max_size];
for(i = 1; i != max_size; i++) {
A[i] = rand() % max_size;
printf("%5d", A[i]);
}
HEAP_SORT( A );
printf("\n\n");
for(i = 1; i != max_size; i++)
printf("%5d",A[i]);
system("PAUSE");
}
『拾』 C語言:若原始記錄接近正序或反序，則選用堆排序，若初始記錄無序則最好選用快速排序。這是為什麼
1，堆排序的性能：時間復雜度總是Nlogn(N) 的。
2，快速排序不屬於原地排序，由於程序中使用了遞歸，需要遞歸調用棧的支持，而棧的長度取決於遞歸調用的深度。在平均情況下，需要O(logn) 的棧空間；最壞情況下，棧空間可達O(n) 。
1 ）劃分元素的選取是影響時間性能的關鍵。
2 ）輸入數據次序越亂，所選劃分元素值的隨機性越好，排序速度越快。快速排序不是自然排序方法。
3 ）改變劃分元素的選取方法，至多隻能改變演算法平均情況下的時間性能，無法改變最壞情況下的時間性能。即最壞情況下，快速排序的時間復雜性總是O(n 2 )。