c語言中桶排法實際應用

⑴ c語言（高分）

1.相對於遞歸演算法,遞推演算法免除了數據進出棧的過程，也就是說,不需要函數不斷的向邊界值靠攏,而直接從邊界出發,直到求出函數值.
比如階乘函數：f(n)=n*f(n-1)
在f(3)的運算過程中,遞歸的數據流動過程如下:
f(3){f(i)=f(i-1)*i}-->f(2)-->f(1)-->f(0){f(0)=1}-->f(1)-->f(2)--f(3){f(3)=6}
而遞推如下:
f(0)-->f(1)-->f(2)-->f(3)
由此可見,遞推的效率要高一些,在可能的情況下應盡量使用遞推.但是遞歸作為比較基礎的演算法,它的作用不能忽視.所以,在把握這兩種演算法的時候應該特別注意.
2.所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
分類
在計算機科學所使用的排序演算法通常被分類為：
計算的復雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序演算法總平均上總是至少需要Ω(n log n)。
記憶體使用量（以及其他電腦資源的使用）
穩定度：穩定排序演算法會依照相等的關鍵（換言之就是值）維持紀錄的相對次序。也就是一個排序演算法是穩定的，就是當有兩個有相等關鍵的紀錄R和S，且在原本的串列中R出現在S之前，在排序過的串列中R也將會是在S之前。
一般的方法：插入、交換、選擇、合並等等。交換排序包含冒泡排序（bubble sort）和快速排序（quicksort）。選擇排序包含shaker排序和堆排序（heapsort）。
當相等的元素是無法分辨的，比如像是整數，穩定度並不是一個問題。然而，假設以下的數對將要以他們的第一個數字來排序。
(4, 1) (3, 1) (3, 7) (5, 6)
在這個狀況下，有可能產生兩種不同的結果，一個是依照相等的鍵值維持相對的次序，而另外一個則沒有：
(3, 1) (3, 7) (4, 1) (5, 6) (維持次序)
(3, 7) (3, 1) (4, 1) (5, 6) (次序被改變)
不穩定排序演算法可能會在相等的鍵值中改變紀錄的相對次序，但是穩定排序演算法從來不會如此。不穩定排序演算法可以被特別地時作為穩定。作這件事情的一個方式是人工擴充鍵值的比較，如此在其他方面相同鍵值的兩個物件間之比較，就會被決定使用在原先資料次序中的條目，當作一個同分決賽。然而，要記住這種次序通常牽涉到額外的空間負擔。
排列演算法列表
在這個表格中，n是要被排序的紀錄數量以及k是不同鍵值的數量。
穩定的
冒泡排序（bubble sort） — O(n2)
雞尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n2)
插入排序 （insertion sort）— O(n2)
桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
計數排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
歸並排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
原地歸並排序 — O(n2)
二叉樹排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
鴿巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
Gnome sort — O(n2)
Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體
不穩定
選擇排序 （selection sort）— O(n2)
希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
Comb sort — O(n log n)
堆排序 （heapsort）— O(n log n)
Smoothsort — O(n log n)
快速排序 （quicksort）— O(n log n) 期望時間, O(n2) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n)
Patience sorting — O(n log n + k) 最外情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序演算法
Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
Stupid sort — O(n3); 遞回版本需要 O(n2) 額外記憶體
Bead sort — O(n) or O(√n), 但需要特別的硬體
Pancake sorting — O(n), 但需要特別的硬體
排序的演算法
排序的演算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序演算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對於簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小范圍內的排序演算法。
插入排序
冒泡排序
選擇排序
快速排序
堆排序
歸並排序
基數排序
希爾排序
插入排序
插入排序是這樣實現的：
首先新建一個空列表，用於保存已排序的有序數列（我們稱之為"有序列表"）。
從原數列中取出一個數，將其插入"有序列表"中，使其仍舊保持有序狀態。
重復2號步驟，直至原數列為空。
插入排序的平均時間復雜度為平方級的，效率不高，但是容易實現。它藉助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等於原列表的長度。
冒泡排序
冒泡排序是這樣實現的：
首先將所有待排序的數字放入工作列表中。
從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大於他的下一位，則將它與它的下一位交換。
重復2號步驟，直至再也不能交換。
冒泡排序的平均時間復雜度與插入排序相同，也是平方級的，但也是非常容易實現的演算法。
選擇排序
選擇排序是這樣實現的：
設數組內存放了n個待排數字，數組下標從1開始，到n結束。
i=1
從數組的第i個元素開始到第n個元素，尋找最小的元素。
將上一步找到的最小元素和第i位元素交換。
如果i=n－1演算法結束，否則回到第3步
選擇排序的平均時間復雜度也是O(n²)的。
快速排序
現在開始，我們要接觸高效排序演算法了。實踐證明，快速排序是所有排序演算法中最高效的一種。它採用了分治的思想：先保證列表的前半部分都小於後半部分，然後分別對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序演算法中，演算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小於後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當別論了。
堆排序
堆排序與前面的演算法都不同，它是這樣的：
首先新建一個空列表，作用與插入排序中的"有序列表"相同。
找到數列中最大的數字，將其加在"有序列表"的末尾，並將其從原數列中刪除。
重復2號步驟，直至原數列為空。
堆排序的平均時間復雜度為nlogn,效率高（因為有堆這種數據結構以及它奇妙的特徵，使得"找到數列中最大的數字"這樣的操作只需要O(1)的時間復雜度，維護需要logn的時間復雜度），但是實現相對復雜（可以說是這里7種演算法中比較難實現的）。
看起來似乎堆排序與插入排序有些相像，但他們其實是本質不同的演算法。至少，他們的時間復雜度差了一個數量級，一個是平方級的，一個是對數級的。
平均時間復雜度
插入排序 O(n2)
冒泡排序 O(n2)
選擇排序 O(n2)
快速排序 O(n log n)
堆排序 O(n log n)
歸並排序 O(n log n)
基數排序 O(n)
希爾排序 O(n1.25)
3.索引查找是在索引表和主表(即線性表的索引存儲結構)上進行的查找。索引查找的過程是：首先根據給定的索引值K1，在索引表上查找出索引值等於KI的索引項，以確定對應予表在主表中的開始位置和長度，然後再根據給定的關鍵字K2，茬對應的子表中查找出關鍵字等於K2的元素(結點)。對索引表或子表進行查找時，若表是順序存儲的有序表，則既可進行順序查找，也可進行二分查找，否則只能進行順序查找。
設數組A是具有mainlist類型的一個主表，數組B是具有inde)dist類型的在主表A 上建立的一個索引表，m為索引表B的實際長度，即所含的索引項的個數，KI和K2分別為給定待查找的索引值和關鍵字(當然它們的類型應分別為索引表中索引值域的類型和主表中關鍵字域在索引存儲中，不僅便於查找單個元素，而且更便於查找一個子表中的全部元素。當需要對一個子袁中的全部元素依次處理時，只要從索引表中查找出該子表的開始位
置即可。由此開始位置可以依次取出該子表中的每一個元素，所以整個查找過程的時間復雜度為，若不是採用索引存儲，而是採用順序存儲，即使把它組織成有序表而進行二分查找時，索引查找一個子表中的所有元素與二分查找一個子表中的所有元素相比。
若在主表中的每個子表後都預留有空閑位置，則索引存儲也便於進行插入和刪除運算，因為其運算過程只涉及到索引表和相應的子表，只需要對相應子表中的元素進行比較和移動，與其它任何子表無關，不像順序表那樣需涉及到整個表中的所有元素，即牽一發而動全身。
在線性表的索引存儲結構上進行插入和刪除運算的演算法，也同查找演算法類似，其過程為：首先根據待插入或刪除元素的某個域(假定子表就是按照此域的值劃分的)的值查找索引表，確定出對應的子表，然後再根據待插入或刪除元素的關鍵字，在該子表中做插入或刪除元素的操作。因為每個子表不是順序存儲，就是鏈接存儲，所以對它們做插入或刪除操作都是很簡單的。
4.插入法排序
#define N 10
#include"stdio.h"
main()
{ int i,j,k,t,a[N];
clrscr();
printf("Please input %d numbers:\n",N);
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=1;i<N;i++)
{
for(j=0;j<i;j++)
{if(a[j]>a[i])
{t=a[i];
for(k=i;k>=j;k--)
a[k]=a[k-1];
a[j]=t;
}
}
}
printf("small to big order:\n");
for(i=0;i<N;i++)
printf("%-2d",a[i]);
printf("\n");
getch();
}

⑵ c語言求解：有12升水，怎樣利用一個8升和5升的桶分出2個6升的水，要求列印出分水過程！

倒出桶 倒入桶 12L桶 8L桶 5L桶
12# 8# 4 8 0
8# 5# 4 3 5
5# 12# 9 3 0
8# 5# 9 0 3
12# 8# 1 8 3
8# 5# 1 6 5
5# 12# 6 6 0
真暈了，用printf列印就行了啊

⑶ c語言數組的排序

可以採用冒泡排序的方法。以下給題主一個對既定數組進行升序、降序排序的代碼

#include<stdio.h>
#include<time.h>

#defineelemTypeint/*元素類型*/
#defineLEN100/*數組長度上限*/

#defineASC0/*升序*/
#defineDESC1/*降序*/

/*冒泡排序*/
/*參數說明：*/
/*elemTypearr[]：排序目標數組*/
/*intlen：元素個數*/
/*intorder：排序方式；升序（由小到大）：ASC；降序（由大到小）：DESC*/
voidbubbleSort(elemTypearr[],intlen,intorder){
	inti,j,temp;

	for(i=0;i<len-1;i++)
		for(j=0;j<len-1-i;j++){
			if(order==ASC){/*升序*/
				if(arr[j]>arr[j+1]){
					temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
			elseif(order==DESC){/*降序*/
				if(arr[j]<arr[j+1]){
					temp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=temp;
				}
			}
		}
}

/*列印數組*/
voidprintArr(elemTypearr[],intlen){
	inti;
	for(i=0;i<len;i++)
		printf("%d	",arr[i]);
	putchar('
');
}

intmain(void){
	elemTypearr[LEN]={3,5,1,7,2,9,6,8,10,4};
	intlen;

	len=10;
	
	puts("初始數組：");
	printArr(arr,len);
	putchar('
');
	
	puts("升序排列：");
	bubbleSort(arr,len,ASC);/*升序冒泡排序*/
	printArr(arr,len);
	putchar('
');
	
	puts("降序排列：");
	bubbleSort(arr,len,DESC);/*降序冒泡排序*/
	printArr(arr,len);
	putchar('
');
	
	getch();/*屏幕暫留*/
	return0;
}

運行結果

⑷ 求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語言（簡單的）編寫程序輸入一維整形數組a[10],將其按由小到大排序後輸出

這個應該用起泡法排序演算法。

#include<stdio.h>

intmain(){

inta[10];inti,j,k;

printf("input10numbers: ");

for(i=0;i<10;i++）{//輸入十個數，一次循環輸入10次

scanf("%d",&a[i]);

printf(" ");//換行

for(j=0;j<9;j++)//從小到大換行經典方法四行

for(i=0;i<9;i++)

if(a[i]>a[i+1])

{t=a[i];a[i]=a[i+1];a[i+1]=t;}

printf(」thesortednumbers: 」）；

for（i=0;i<10;i++）

printf("%d",a[i]);

printf(" ");

}

}

結果演示：

⑹ 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語言：除了冒泡排序，其它還有什麼排序（名稱）。分別是怎樣實現排序的。

直接插入排序、希爾排序、選擇排序、堆排序、 冒泡排序、快速排序、歸並排序、分配排序等 如果你真的想仔細了解，自己多看數據結構的書吧， 這么多，一句兩句是說不完的。 排序跟編程語言無關，任何編程語言都可以實現上面所有的排序。 還有好多排序呢，比如桶排序，基數排序。排序網路等

記得採納啊

⑻ C語言排序

//總共給你整理了7種排序演算法：希爾排序，鏈式基數排序，歸並排序
//起泡排序，簡單選擇排序，樹形選擇排序，堆排序,先自己看看吧，
//看不懂可以再問身邊的人或者查資料,既然可以上網，我相信你所在的地方信息流通方式應該還行,所有的程序全部在VC++6.0下編譯通過
//希爾排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
void ShellInsert(SqList &L,int dk)
{ // 對順序表L作一趟希爾插入排序。本演算法是和一趟直接插入排序相比，
// 作了以下修改：
// 1.前後記錄位置的增量是dk,而不是1;
// 2.r[0]只是暫存單元,不是哨兵。當j<=0時,插入位置已找到。演算法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;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]; // 插入
}
}

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]對順序表L作希爾排序。演算法10.5
int k;
for(k=0;k<t;++k)
{
ShellInsert(L,dlta[k]); // 一趟增量為dlta[k]的插入排序
printf("第%d趟排序結果: ",k+1);
print(L);
}
}

#define N 10
#define T 3
void main()
{
RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8},{55,9},{4,10}};
SqList l;
int dt[T]={5,3,1}; // 增量序列數組
for(int i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前: ");
print(l);
ShellSort(l,dt,T);
printf("排序後: ");
print1(l);
}

/*****************************************************************/
//鏈式基數排序
typedef int InfoType; // 定義其它數據項的類型
typedef int KeyType; // 定義RedType類型的關鍵字為整型
struct RedType // 記錄類型(同c10-1.h)
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項
};
typedef char KeysType; // 定義關鍵字類型為字元型
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
#define MAX_NUM_OF_KEY 8 // 關鍵字項數的最大值
#define RADIX 10 // 關鍵字基數，此時是十進制整數的基數
#define MAX_SPACE 1000
struct SLCell // 靜態鏈表的結點類型
{
KeysType keys[MAX_NUM_OF_KEY]; // 關鍵字
InfoType otheritems; // 其它數據項
int next;
};

struct SLList // 靜態鏈表類型
{
SLCell r[MAX_SPACE]; // 靜態鏈表的可利用空間，r[0]為頭結點
int keynum; // 記錄的當前關鍵字個數
int recnum; // 靜態鏈表的當前長度
};

typedef int ArrType[RADIX];
void InitList(SLList &L,RedType D[],int n)
{ // 初始化靜態鏈表L（把數組D中的數據存於L中）
char c[MAX_NUM_OF_KEY],c1[MAX_NUM_OF_KEY];
int i,j,max=D[0].key; // max為關鍵字的最大值
for(i=1;i<n;i++)
if(max<D[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進制整型轉化為字元型,存入c
for(j=strlen(c);j<L.keynum;j++) // 若c的長度<max的位數,在c前補'0'
{
strcpy(c1,"0");
strcat(c1,c);
strcpy(c,c1);
}
for(j=0;j<L.keynum;j++)
L.r[i].keys[j]=c[L.keynum-1-j];
}
}

int ord(char c)
{ // 返回k的映射(個位整數)
return c-'0';
}

void Distribute(SLCell r[],int i,ArrType f,ArrType e) // 演算法10.15
{ // 靜態鍵表L的r域中記錄已按(keys[0],…,keys[i-1])有序。本演算法按
// 第i個關鍵字keys[i]建立RADIX個子表,使同一子表中記錄的keys[i]相同。
// f[0..RADIX-1]和e[0..RADIX-1]分別指向各子表中第一個和最後一個記錄
int j,p;
for(j=0;j<RADIX;++j)
f[j]=0; // 各子表初始化為空表
for(p=r[0].next;p;p=r[p].next)
{
j=ord(r[p].keys[i]); // ord將記錄中第i個關鍵字映射到[0..RADIX-1]
if(!f[j])
f[j]=p;
else
r[e[j]].next=p;
e[j]=p; // 將p所指的結點插入第j個子表中
}
}

int succ(int i)
{ // 求後繼函數
return ++i;
}

void Collect(SLCell r[],ArrType f,ArrType e)
{ // 本演算法按keys[i]自小至大地將f[0..RADIX-1]所指各子表依次鏈接成
// 一個鏈表，e[0..RADIX-1]為各子表的尾指針。演算法10.16
int j,t;
for(j=0;!f[j];j=succ(j)); // 找第一個非空子表，succ為求後繼函數
r[0].next=f[j];
t=e[j]; // r[0].next指向第一個非空子表中第一個結點
while(j<RADIX-1)
{
for(j=succ(j);j<RADIX-1&&!f[j];j=succ(j)); // 找下一個非空子表
if(f[j])
{ // 鏈接兩個非空子表
r[t].next=f[j];
t=e[j];
}
}
r[t].next=0; // t指向最後一個非空子表中的最後一個結點
}

void printl(SLList L)
{ // 按鏈表輸出靜態鏈表
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是採用靜態鏈表表示的順序表。對L作基數排序，使得L成為按關鍵字
// 自小到大的有序靜態鏈表，L.r[0]為頭結點。演算法10.17
int i;
ArrType f,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,f,e); // 第i趟收集
printf("第%d趟收集後:\n",i+1);
printl(L);
printf("\n");
}
}

void print(SLList L)
{ // 按數組序號輸出靜態鏈表
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]為靜態鏈表L的第i個最小記錄的序號
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給出靜態鏈表L的有序次序，即L.r[adr[i]]是第i小的記錄。
// 本演算法按adr重排L.r，使其有序。演算法10.18(L的類型有變)
int i,j,k;
for(i=1;i<L.recnum;++i) // 改此句(類型)
if(adr[i]!=i)
{
j=i;
L.r[0]=L.r[i]; // 暫存記錄L.r[i]
while(adr[j]!=i)
{ // 調整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]={{278,1},{109,2},{63,3},{930,4},{589,5},{184,6},{505,7},{269,8},{8,9},{83,10}};
SLList l;
int *adr;
InitList(l,d,N);
printf("排序前(next域還沒賦值):\n");
print(l);
RadixSort(l);
printf("排序後(靜態鏈表):\n");
print(l);
adr=(int*)malloc((l.recnum)*sizeof(int));
Sort(l,adr);
Rearrange(l,adr);
printf("排序後(重排記錄):\n");
print(l);
}
/*******************************************/
//歸並排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

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<=m&&j<=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]復制到TR
if(j<=n)
for(l=0;l<=n-j;l++)
TR[k+l]=SR[j+l]; // 將剩餘的SR[j..n]復制到TR
}

void MSort(RedType SR[],RedType TR1[],int s, int t)
{ // 將SR[s..t]歸並排序為TR1[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)
{ // 對順序表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]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
MergeSort(l);
printf("排序後:\n");
print(l);
}
/**********************************************/
//起泡排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#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中整數序列重新排列成自小至大有序的整數序列(起泡排序)
int i,j,t;
Status change;
for(i=n-1,change=TRUE;i>1&&change;--i)
{
change=FALSE;
for(j=0;j<i;++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;i<n;i++)
printf("%d ",r[i]);
printf("\n");
}

void main()
{
int d[N]={49,38,65,97,76,13,27,49};
printf("排序前:\n");
print(d,N);
bubble_sort(d,N);
printf("排序後:\n");
print(d,N);
}
/****************************************************/
//簡單選擇排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};
int SelectMinKey(SqList L,int i)
{ // 返回在L.r[i..L.length]中key最小的記錄的序號
KeyType min;
int j,k;
k=i; // 設第i個為最小
min=L.r[i].key;
for(j=i+1;j<=L.length;j++)
if(L.r[j].key<min) // 找到更小的
{
k=j;
min=L.r[j].key;
}
return k;
}

void SelectSort(SqList &L)
{ // 對順序表L作簡單選擇排序。演算法10.9
int i,j;
RedType t;
for(i=1;i<L.length;++i)
{ // 選擇第i小的記錄，並交換到位
j=SelectMinKey(L,i); // 在L.r[i..L.length]中選擇key最小的記錄
if(i!=j)
{ // 與第i個記錄交換
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]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
SelectSort(l);
printf("排序後:\n");
print(l);
}
/************************************************/
//樹形選擇排序
#include<string.h>
#include<ctype.h>
#include<malloc.h> // malloc()等
#include<limits.h> // INT_MAX等
#include<stdio.h> // EOF(=^Z或F6),NULL
#include<stdlib.h> // atoi()
#include<io.h> // eof()
#include<math.h> // floor(),ceil(),abs()
#include<process.h> // exit()
#include<iostream.h> // cout,cin
// 函數結果狀態代碼
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
typedef int Status; // Status是函數的類型,其值是函數結果狀態代碼，如OK等
typedef int Boolean; // Boolean是布爾類型,其值是TRUE或FALSE
typedef int InfoType; // 定義其它數據項的類型
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

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; // 完全二叉樹的層數
k=(int)pow(2,l)-1; // l層完全二叉樹的結點總數
k1=(int)pow(2,l-1)-1; // l-1層完全二叉樹的結點總數
t=(RedType*)malloc(k*sizeof(RedType)); // 二叉樹採用順序存儲結構
for(i=1;i<=n;i++) // 將L.r賦給葉子結點
t[k1+i-1]=L.r[i];
for(i=k1+n;i<k;i++) // 給多餘的葉子的關鍵字賦無窮大
t[i].key=INT_MAX;
j1=k1;
j=k;
while(j1)
{ // 給非葉子結點賦值
for(i=j1;i<j;i+=2)
t[i].key<t[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;i<n;i++)
{
L.r[i+1]=t[0]; // 將當前最小值賦給L.r[i]
j1=0;
for(j=1;j<l;j++) // 沿樹根找結點t[0]在葉子中的序號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; // 序號為j1的結點的雙親結點序號
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]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
SqList l;
int i;
for(i=0;i<N;i++)
l.r[i+1]=d[i];
l.length=N;
printf("排序前:\n");
print(l);
TreeSort(l);
printf("排序後:\n");
print(l);
}
/****************************/
//堆排序
#include<stdio.h>
typedef int InfoType; // 定義其它數據項的類型
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define MAXSIZE 20 // 一個用作示例的小順序表的最大長度
typedef int KeyType; // 定義關鍵字類型為整型
struct RedType // 記錄類型
{
KeyType key; // 關鍵字項
InfoType otherinfo; // 其它數據項，具體類型在主程中定義
};

struct SqList // 順序表類型
{
RedType r[MAXSIZE+1]; // r[0]閑置或用作哨兵單元
int length; // 順序表長度
};

typedef SqList HeapType; // 堆採用順序表存儲表示
void HeapAdjust(HeapType &H,int s,int m) // 演算法10.10
{ // 已知H.r[s..m]中記錄的關鍵字除H.r[s].key之外均滿足堆的定義，本函數
// 調整H.r[s]的關鍵字,使H.r[s..m]成為一個大頂堆(對其中記錄的關鍵字而言)
RedType rc;
int j;
rc=H.r[s];
for(j=2*s;j<=m;j*=2)
{ // 沿key較大的孩子結點向下篩選
if(j<m&<(H.r[j].key,H.r[j+1].key))
++j; // j為key較大的記錄的下標
if(!LT(rc.key,H.r[j].key))
break; // rc應插入在位置s上
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc; // 插入
}

void HeapSort(HeapType &H)
{ // 對順序表H進行堆排序。演算法10.11
RedType t;
int i;
for(i=H.length/2;i>0;--i) // 把H.r[1..H.length]建成大頂堆
HeapAdjust(H,i,H.length);
for(i=H.length;i>1;--i)
{ // 將堆頂記錄和當前未經排序子序列H.r[1..i]中最後一個記錄相互交換
t=H.r[1];
H.r[1]=H.r[i];
H.r[i]=t;
HeapAdjust(H,1,i-1); // 將H.r[1..i-1]重新調整為大頂堆
}
}

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]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};
HeapType h;
int i;
for(i=0;i<N;i++)
h.r[i+1]=d[i];
h.length=N;
printf("排序前:\n");
print(h);
HeapSort(h);
printf("排序後:\n");
print(h);
}

⑼ c語言 K桶排序

d

⑽ 請教C語言：輸入n個100以內的整數，將它們按照從大到小的順序排列後輸出。 說明：分別使用選擇排序和桶排

#include<stdio.h> //對數組進行從小到大排序
void main()
{
int a[100];
int i,j,t;
printf("請 輸 入 十個 整數,按enter鍵結束:\n");
for (i=0;i<10;i++)
scanf("%d",&a[i]);
printf("\n");
for(j=0;j<9;j++)
for (i=0;i<=9-j;i++)
if(a[i]<a[i+1])
{
t=a[i];
a[i]=a[i+1];
a[i+1]=t;

} printf("這一百個數字從大到小輸出如下：\n");
for(i=0;i<10;i++)
printf("%4d",a[i]);
printf("\n");
}

就是這個，希望對你有幫助。