Ⅰ c語言中排序方法
1、冒泡排序（最常用）
冒泡排序是最簡單的排序方法：原理是：從左到右，相鄰元素進行比較。每次比較一輪，就會找到序列中最大的一個或最小的一個。這個數就會從序列的最右邊冒出來。（注意每一輪都是從a[0]開始比較的）
以從小到大排序為例，第一輪比較後，所有數中最大的那個數就會浮到最右邊；第二輪比較後，所有數中第二大的那個數就會浮到倒數第二個位置……就這樣一輪一輪地比較，最後實現從小到大排序。
2、雞尾酒排序
雞尾酒排序又稱雙向冒泡排序、雞尾酒攪拌排序、攪拌排序、漣漪排序、來回排序或快樂小時排序, 是冒泡排序的一種變形。該演算法與冒泡排序的不同處在於排序時是以雙向在序列中進行排序。
原理：數組中的數字本是無規律的排放，先找到最小的數字，把他放到第一位，然後找到最大的數字放到最後一位。然後再找到第二小的數字放到第二位，再找到第二大的數字放到倒數第二位。以此類推，直到完成排序。
3、選擇排序
思路是設有10個元素a[1]-a[10]，將a[1]與a[2]-a[10]比較，若a[1]比a[2]-a[10]都小，則不進行交換。若a[2]-a[10]中有一個以上比a[1]小，則將其中最大的一個與a[1]交換，此時a[1]就存放了10個數中最小的一個。同理，第二輪拿a[2]與a[3]-a[10]比較，a[2]存放a[2]-a[10]中最小的數，以此類推。
4、插入排序
插入排序是在一個已經有序的小序列的基礎上，一次插入一個元素*
一般來說，插入排序都採用in-place在數組上實現。
具體演算法描述如下：
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從後向前掃描
⒊ 如果該元素（已排序）大於新元素，將該元素移到下一位置
⒋ 重復步驟3，直到找到已排序的元素小於或者等於新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟2~5
Ⅱ 求c語言基數排序與桶排序的源代碼
基數排序：
#include<math.h>
testBS()
{
inta[]={2,343,342,1,123,43,4343,433,687,654,3};
int*a_p=a;
//計算數組長度
intsize=sizeof(a)/sizeof(int);
//基數排序
bucketSort3(a_p,size);
//列印排序後結果
inti;
for(i=0;i<size;i++)
{
printf("%d ",a[i]);
}
intt;
scanf("%d",t);
}
//基數排序
voidbucketSort3(int*p,intn)
{
//獲取數組中的最大數
intmaxNum=findMaxNum(p,n);
//獲取最大數的位數，次數也是再分配的次數。
intloopTimes=getLoopTimes(maxNum);
inti;
//對每一位進行桶分配
for(i=1;i<=loopTimes;i++)
{
sort2(p,n,i);
}
}
//獲取數字的位數
intgetLoopTimes(intnum)
{
intcount=1;
inttemp=num/10;
while(temp!=0)
{
count++;
temp=temp/10;
}
returncount;
}
//查詢數組中的最大數
intfindMaxNum(int*p,intn)
{
inti;
intmax=0;
for(i=0;i<n;i++)
{
if(*(p+i)>max)
{
max=*(p+i);
}
}
returnmax;
}
//將數字分配到各自的桶中，然後按照桶的順序輸出排序結果
voidsort2(int*p,intn,intloop)
{
//建立一組桶此處的20是預設的根據實際數情況修改
intbuckets[10][20]={};
//求桶的index的除數
//如798個位桶index=(798/1)%10=8
//十位桶index=(798/10)%10=9
//百位桶index=(798/100)%10=7
//tempNum為上式中的1、10、100
inttempNum=(int)pow(10,loop-1);
inti,j;
for(i=0;i<n;i++)
{
introw_index=(*(p+i)/tempNum)%10;
for(j=0;j<20;j++)
{
if(buckets[row_index][j]==NULL)
{
buckets[row_index][j]=*(p+i);
break;
}
}
}
//將桶中的數，倒回到原有數組中
intk=0;
for(i=0;i<10;i++)
{
for(j=0;j<20;j++)
{
if(buckets[i][j]!=NULL)
{
*(p+k)=buckets[i][j];
buckets[i][j]=NULL;
k++;
}
}
}
}
桶排序
#include<stdio.h>
#defineMAXNUM100
voidbucksort(intarr[],intN,intM)
{
intcount[MAXNUM];
for(inti=0;i<=M;i++)
{
count[i]=0;
}
for(inti=0;i<N;i++)
{
++count[arr[i]];
}
for(inti=0;i<=M;i++)
{
for(intj=1;j<=count[i];j++)
{
printf("%d",i);
}
}
}
intmain()
{
inta[]={2,5,6,12,4,8,8,6,7,8,8,10,7,6};
bucksort(a,sizeof(a)/sizeof(a[0]),12);
return0;
}
Ⅲ 誰幫我寫一份c語言版的各種排序演算法的效率比較
（1）「冒泡法」 冒泡法大家都較熟悉。其原理為從a[0]開始，依次將其和後面的元素比較,若a[0]>a[i]，則交換它們，一直比較到a[n]。同理對a[1],a[2],...a[n-1]處理，即完成排序。下面列出其代碼：void bubble(int *a,int n) /*定義兩個參數：數組首地址與數組大小*/ { int i,j,temp; for(i=0;i<n-1;i++) for(j=i+1;j<n;j++) /*注意循環的上下限*/ if(a[i]>a[j]) { temp=a[i]; a[i]=a[j]; a[j]=temp; } } 冒泡法原理簡單，但其缺點是交換次數多，效率低。 下面介紹一種源自冒泡法但更有效率的方法「選擇法」。 （2）「選擇法」 選擇法循環過程與冒泡法一致，它還定義了記號k=i,然後依次把a[k]同後面元素比較，若a[k]>a[j],則使k=j.最後看看k=i是否還成立，不成立則交換a[k],a[i],這樣就比冒泡法省下許多無用的交換，提高了效率。void choise(int *a,int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; /*給記號賦值*/ for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; /*是k總是指向最小元素*/ if(i!=k) { /*當k!=i是才交換，否則a[i]即為最小*/ temp=a[i]; a[i]=a[k]; a[k]=temp; } } } 選擇法比冒泡法效率更高，但說到高效率，非「快速法」莫屬，現在就讓我們來了解它。 （3）「快速法」 快速法定義了三個參數，（數組首地址*a,要排序數組起始元素下標i,要排序數組結束元素下標j). 它首先選一個數組元素（一般為a[(i+j)/2],即中間元素）作為參照，把比它小的元素放到它的左邊，比它大的放在右邊。然後運用遞歸，在將它左，右兩個子數組排序，最後完成整個數組的排序。下面分析其代碼：void quick(int *a,int i,int j) { int m,n,temp; int k; m=i; n=j; k=a[(i+j)/2]; /*選取的參照*/ do { while(a[m]<k&&m<j) m++; /* 從左到右找比k大的元素*/ while(a[n]>k&&n>i) n--; /* 從右到左找比k小的元素*/ if(m<=n) { /*若找到且滿足條件，則交換*/ temp=a[m]; a[m]=a[n]; a[n]=temp; m++; n--; } }while(m<=n); if(m<j) quick(a,m,j); /*運用遞歸*/ if(n>i) quick(a,i,n); } （4）「插入法」 插入法是一種比較直觀的排序方法。它首先把數組頭兩個元素排好序，再依次把後面的元素插入適當的位置。把數組元素插完也就完成了排序。void insert(int *a,int n) { int i,j,temp; for(i=1;i<n;i++) { temp=a[i]; /*temp為要插入的元素*/ j=i-1; while(j>=0&&temp<a[j]) { /*從a[i-1]開始找比a[i]小的數，同時把數組元素向後移*/ a[j+1]=a[j]; j--; } a[j+1]=temp; /*插入*/ } } （5）「shell法」 shell法是一個叫 shell 的美國人與1969年發明的。它首先把相距k(k>=1)的那幾個元素排好序，再縮小k值（一般取其一半），再排序，直到k=1時完成排序。下面讓我們來分析其代碼：void shell(int *a,int n) { int i,j,k,x; k=n/2; /*間距值*/ while(k>=1) { for(i=k;i<n;i++) { x=a[i]; j=i-k; while(j>=0&&x<a[j]) { a[j+k]=a[j]; j-=k; } a[j+k]=x; } k/=2; /*縮小間距值*/ } } 上面我們已經對幾種排序法作了介紹，現在讓我們寫個主函數檢驗一下。 #include<stdio.h> /*別偷懶，下面的"..."代表函數體，自己加上去哦！*/ void bubble(int *a,int n) { ... } void choise(int *a,int n) { ... } void quick(int *a,int i,int j) { ... } void insert(int *a,int n) { ... } void shell(int *a,int n) { ... } /*為了列印方便，我們寫一個print吧。*/[code]void print(int *a,int n) { int i; for(i=0;i<n;i++) printf("%5d",a[i]); printf("\n"); } main() { /*為了公平，我們給每個函數定義一個相同數組*/ int a1[]={13,0,5,8,1,7,21,50,9,2}; int a2[]={13,0,5,8,1,7,21,50,9,2}; int a3[]={13,0,5,8,1,7,21,50,9,2}; int a4[]={13,0,5,8,1,7,21,50,9,2}; int a5[]={13,0,5,8,1,7,21,50,9,2}; printf("the original list:"); print(a1,10); printf("according to bubble:"); bubble(a1,10); print(a1,10); printf("according to choise:"); choise(a2,10); print(a2,10); printf("according to quick:"); quick(a3,0,9); print(a3,10); printf("according to insert:"); insert(a4,10); print(a4,10); printf("according to shell:"); shell(a5,10); print(a5,10); }
Ⅳ 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語言描述如何實現基數排序。是數據結構課程設計作業
/*
1.基數是利用同位比較的排序演算法，時空復雜度都比較低，很適合字母字元串排序
2.比如對int數組用以1和0為基數排序，先比較第一位，0位靠前1位靠後，一直排完32位
3.基數排序不需要特殊的數據結構
4.只需一個函數即能完成基數排序
5.給個郵箱發源碼，手機不知道怎麼上傳附件
6.對於百萬級的數據，效率和快速排序相仿，但使用空間低很多，並且在串大小比較方面具有其他排序演算法無法匹敵的性能
整理一下代碼，終於獨立出來了，如果覺得可以就採納吧
*/
#define elapser
#define debug
//#define descend
#ifndef descend
#define ascend
#endif
#define count_max 0x7fffffff
#define count_min 0x00000002
#define step_default 0x80000000
int radixsort (unsigned int* pdata ,unsigned int count)
{
void radix (unsigned int* pfirst ,unsigned int* plast ,unsigned int step) ;
if (pdata == 0 || count < count_min || count > count_max)
return -1 ;
radix (pdata ,pdata + count - 1 ,step_default) ;
return 0 ;
}
void radix (unsigned int* pfirst ,unsigned int* plast ,unsigned int step)
{
unsigned int* pleft = pfirst ;
unsigned int* pright = plast ;
while (1)
{
#ifdef descend
while ((*pleft & step) && pleft < pright)
#else
while (!(*pleft & step) && pleft < pright)
#endif
pleft++ ;
#ifdef descend
while (!(*pright & step) && pleft < pright)
#else
while ((*pright & step) && pleft < pright)
#endif
pright-- ;
if (pleft >= pright)
break ;
*pleft ^= *pright ;
*pright ^= *pleft ;
*pleft ^= *pright ;
pleft++ ;
pright-- ;
}
if (pleft > pright)
{
pleft-- ;
pright++ ;
}
else
#ifdef descend
if (!(*pleft & step))
#else
if (*pleft & step)
#endif
pleft-- ;
else
pright++ ;
if (!(step >>= 1))
return ;
if (pleft > pfirst)
radix (pfirst ,pleft ,step) ;
if (pright < plast)
radix (pright ,plast ,step) ;
return ;
}
#ifdef debug
#define data_count 1000000
int main ()
{
int radixsort (unsigned int* pdata ,unsigned int count) ;
unsigned int data[data_count] ;
unsigned int* p = data ;
unsigned int* pe = p + data_count ;
srand ((unsigned int) time (0)) ;
while (p < pe)
*p++ = (unsigned int) rand () & 0x0000000f ;
int itime = time (0) ;
int iresult = radixsort (data ,data_count) ;
itime = time (0) - itime ;
for (p = data ; p < pe ; p++)
printf ("%u ," ,*p) ;
printf ("\n") ;
printf ("task was completed in %d seconds while result is %d\n" ,itime ,iresult) ;
printf ("this radixsort routine is made by elapser\nplease choose my anwser if it helps\n") ;
return 0 ;
}
#endif
Ⅵ 用c語言編寫一個排序程序，要求使用基數排序演算法，最好能詳細解釋下，c語言初學者
#include<stdio.h>
#defineMAX_NUM_OF_KEY8//關鍵字項數的最大值
#defineRADIX10//關鍵字基數，此時是十進制整數的基數
#defineMAX_SPACE10000
typedefintKeysType;
typedefintInfoType;
typedefstruct
{
KeysTypekeys;//關鍵字
InfoTypeotheritems;//其它數據項
intnext;
}SLCell;
typedefstruct
{
SLCellr[MAX_SPACE];//靜態鏈表的可利用空間，r[0]為頭結點
intkeynum;//記錄當前關鍵字個數
intrecnum;//靜態鏈表的當前長度
}SLList;//靜態鏈表類型
typedefintArrType[RADIX];//指針數組類型
intord(KeysTypekey,intdigitally)
{
inti;
if(digitally)
{//根據位數，返回不同的數位
for(i=0;i<digitally;++i)
{
key/=10;
}
}
returnkey%10;
}
voidDistribute(SLCell*r,inti,ArrTypef,ArrTypee)
{
//靜態鏈表L的r域中記錄已按keys[0].....keys[i-1]有序。
//本演算法按第i個關鍵字keys[i]建立RADIX個子表，使同一子表中記錄的keys[i]相同
//f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最後一個記錄
intj,p;
for(j=0;j<RADIX;++j)
{
f[j]=e[j]=0;//初始化指針
}
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys,i);//取得相應數位上的值
if(!f[j])
f[j]=p;//頭指針為空，則取得結點位置
else
r[e[j]].next=p;//原來的尾指針指向第i位數相同的新結點
e[j]=p;//尾指指向新結點作為最後結點
}
}
voidCollect(SLCell*r,inti,ArrTypef,ArrTypee)
{
//本演算法按keys[i]自小至大地將f[0..radix-1]所指各子表依次鏈接成一個鏈表
//e[0..radix-1]為各子有的尾指針
intj,t;
for(j=0;!f[j];++j);//找第一個非空子表
r[0].next=f[j];//r[0].next指向第一個非空結點
t=e[j];
while(j<RADIX-1)
{
for(j=j+1;j<RADIX-1&&!f[j];++j);//找下一個非空子表
if(f[j])
{
r[t].next=f[j];//鏈接兩非空子表
t=e[j];//指向尾結點
}
}
r[t].next=0;//t指向最後一個非空子表中的最後一個結點
}
voidRadixSort(SLList*L)
{
//L是採用靜態鏈表表示的順序表
//對L作基數排序，使得L成為按關鍵字自小到大的有序靜態鏈表，
//L.r[0]為頭結點
inti;
ArrTypef,e;
for(i=0;i<L->recnum;++i)
{
L->r[i].next=i+1;
}
L->r[L->recnum].next=0;//L改造為靜態鏈表
for(i=0;i<L->keynum;++i)//按最低位優先依次對各關鍵字進行分配和收集
{
Distribute(L->r,i,f,e);//第i趟分配
Collect(L->r,i,f,e);//第i趟收集
}
}
intmain(void)
{
KeysTypearr[]={69,17,63,32,27,73,49,53},temp;
SLListL;
inti,nLen,nCount;
nCount=0;
nLen=sizeof(arr)/sizeof(KeysType);
L.recnum=nLen;//取得關鍵字個數
temp=arr[0];
while(temp)
{
temp/=10;
nCount++;
}
L.keynum=nCount;//取得數據位數
for(i=0;i<L.recnum;++i)
{
L.r[i+1].keys=arr[i];//取得元素
}
RadixSort(&L);
for(i=L.r[0].next;i;i=L.r[i].next)
{
printf("%d ",L.r[i].keys);
}
return0;
}
以前學嚴蔚敏時的代碼，當時寫了些注釋，慢慢看應該能理解。
Ⅶ 用c語言實現計數排序、基數排序、桶排序演算法。
網上找吧,這些都是基本東西,要不買本數據結構的書看看
Ⅷ C語言，基數排序
#include <stdio.h>
typedef struct node {
int data;
int next;
} node;
int head; //這里的head是全局變數
int fr[10];
int re[10];
void Distribute(node *a, int w) //第一次w=1
{
int i;
for (i=0; i<10; i++) { //初始化
fr[i] = -1;
}
for (i=head; i!=-1; i=a[i].next) { //第一次i=0
int x = a[i].data / w % 10; //這是以前求一個數各個位的方法例：98%10=8(個位) 98/10%10=9(十位)
if (fr[x] == -1) {
fr[x] = re[x] = i;
}
else {
a[re[x]].next = i;
re[x] = i;
}
}
for (i=0; i<10; i++) {
if (fr[i] != -1) {
a[re[i]].next = -1;
}
}
}
void Collect(node *a)
{
int i, last;
last = -1;
for (i=0; i<10; i++) {
if (fr[i] != -1) {
if (last == -1) {
head = fr[i];
last = re[i];
}
else {
a[last].next = fr[i];
last = re[i];
}
}
}
a[last].next = -1;
}
void Out(node *a, int w)
{
int i, p, k;
printf("weight == %d\n", w);
for (i=0; i<10; i++) {
printf("fr[%d] ", i);
p = fr[i];
k = 0;
while (p != -1) {
printf("->%4d ", a[p].data);
p = a[p].next;
k++;
}
while (k<3) printf("-------"),k++;
printf("-> re[%d]\n", i);
}
}
void Output(node *a, int head) //結構體指針 ，這里的head是形參，調用此函數結束後即釋放，不影響全局變數head的值
{
while (head != -1) {
printf("%4d", a[head].data);
head = a[head].next;
}
printf("\n");
}
void main()
{
//對於無數據的數組排序會出錯~~~
//614 738 921 485 637 101 215 530 790 306
node a[10]; //結構體數組
int i, n = 10, max;
max = 0x80000000; //此處對0x80000000及MAX的意思不理解
printf("max == %d\n", max);
printf("Please intput %d numbers~\n", n);
for (i=0; i<n; i++) {
scanf("%d", &a[i].data); //賦值
a[i].next = i + 1;
if (a[i].data > max) max=a[i].data;
}
head = 0;
a[n - 1].next = -1;
Output(a, head);
for (i=1; i<=max; i*=10) {
Distribute(a, i);
Out(a, i);
Collect(a);
Output(a, head);
}
}
Ⅸ 鏈式基數排序的演算法思想（C語言），越多越仔細越好
參考
/* 基數排序的演算法源程序*/
#include <stdio.h>
#define D 3 /* D為排序碼的最大位數 */
#define R 10 /* R為基數 */
typedef int KeyType;
typedef int DataType;
struct Node; /* 單鏈表結點類型 */
typedef struct Node RadixNode;
struct Node {
KeyType key[D];
/* DataType info;*/
RadixNode *next;
};
typedef RadixNode * RadixList;
typedef struct QueueNode {
RadixNode *f; /* 隊列的頭指針 */
RadixNode *e; /* 隊列的尾指針 */
} Queue;
Queue queue[R];
void radixSort(RadixList * plist, int d, int r) {
int i,j,k;
RadixNode *p, *head = (*plist)-> next;
for(j = d-1; j > = 0; j--) { /* 進行d次分配和收集*/
p = head;
for(i = 0; i < r; i++) {
queue[i].f = NULL; queue[i].e = NULL; /* 清隊列 */
}
while (p != NULL) {
k = p-> key[j]; /* 按排序碼的第j個分量進行分配*/
if (queue[k].f == NULL)
queue[k].f = p; /* 若第k個隊列為空，則當前記錄為隊頭*/
else (queue[k].e)-> next = p;/* 否則當前記錄鏈接到第k隊的隊尾*/
queue[k].e = p;
p = p-> next;
}
for(i = 0; queue[i].f == NULL; i++) /* 找出第一個非空隊列*/
;
p = queue[i].e; head = queue[i].f; /* head為收集鏈表的頭指針*/
for(i++; i < r; i++)
if(queue[i].f != NULL) { /* 收集非空隊列 */
p-> next = queue[i].f;
p = queue[i].e;
}
p-> next = NULL;
}
(*plist)-> next = head;
}
struct Node element[11]={
0,0,0,NULL,/*表頭*/
0,3,6,NULL,/*36*/
0,0,5,NULL,/*5*/
0,1,6,NULL,/*16*/
0,9,8,NULL,/*98*/
0,9,5,NULL,/*95*/
0,4,7,NULL,/*47*/
0,3,2,NULL,/*32*/
0,3,6,NULL,/*36*/
0,4,8,NULL,/*48*/
0,1,0,NULL /*10*/
};
int main(){
int i;
RadixList p = element;
for (i = 0; i < 10; i++)
element[i].next = &element[i+1];
element[10].next = NULL;
radixSort(&p, 3, 10);
p = p-> next;
while (p != NULL){
printf( "%d ", p-> key[1]*10+p-> key[2]);
p = p-> next;
}
getchar();
return 0;
}
Ⅹ 基數排序是怎麼一回事（c語言）
基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。
以LSD為例，假設原來有一串數值如下所示：
73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根據個位數的數值，在走訪數值時將它們分配至編號0到9的桶子中：
0
1 81
2 22
3 73 93 43
4 14
5 55 65
6
7
8 28
9 39
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接著再進行一次分配，這次是根據十位數來分配：
0
1 14
2 22 28
3 39
4 43
5 55
6 65
7 73
8 81
9 93
接下來將這些桶子中的數值重新串接起來，成為以下的數列：
14, 22, 28, 39, 43, 55, 65, 73, 81, 93
這時候整個數列已經排序完畢；如果排序的對象有三位數以上，則持續進行以上的動作直至最高位數為止。
LSD的基數排序適用於位數小的數列，如果位數多的話，使用MSD的效率會比較好，MSD的方式恰與LSD相反，是由高位數為基底開始進行分配，其他的演算方式則都是相同。
懂了沒？這是網路上的，還不懂的話再問我