桶式排序的代碼實作

1.關于單趟桶式排序的介紹以及問題所在
介紹一個簡單的情況，假如我們有若干個整數（各不相同)，這些整數的范圍在0-99內，如何排好這若干個整數呢？
按照桶式排序的方法，我們可以設定一個陣列int barrel[100]，每個元素代表一個桶，每個桶的下標代表這個桶里裝的數字，比如數字18，我們就把它裝進barrel[18]里面去，所以，不難得到，如果待排序的數字序列有40個數字，那么我們只需要花費40次把數字裝進桶里的時間就可以了，
問題在于，如果數字序列中只有2個數字，可由于不知道到底是0-99中的哪兩個，所以仍然需要開辟100個元素的陣列空間用來當桶，這就造成了空間的浪費，所以我們考慮桶越少越好，
另外，我們上面考慮的是數字序列中的數字各不相同的情況，如果考慮重復的話，我們可能需要陣列來表示桶，才能裝得下重復的數字，就拿上面的例子舉例，假設待排序列中只有2個數（范圍在0-99間），由于每個桶都有可能裝這兩個數，所以每個桶都應該是大小為2的陣列，又因為要設定100個桶，所以空間花費就為2×100個元素型別的空間，當待排序列中有n個數時，空間花費將變成n×100，而且要知道真正裝有數字的空間只有n個，所以有大量的空間因為沒有裝數字所以導致了巨大的浪費，于是我們考慮每個桶用鏈表來表示，有就分配，沒有就不分配，從而避免不必要的空間浪費，
2.解釋多趟桶式排序
多趟桶式排序的每一趟就是對某一個位進行桶式排序，每一趟把某個數按照某一位上的數字放入桶中，
究竟是從低位到高位，還是從高位到低位呢？
首先我們要知道每趟把數字放入桶里后要做什么，當我們將數字依次放入桶里后，我們要將桶里的數字“倒出來”，就是把它按順序覆寫原來的數字序列，作為下一趟的待處理數字序列，“倒出來”的程序中，數字不同的桶好處理，只要按照桶的編號從小到大倒就可以了，但是一個桶里的不同數字如何處理呢？
不難得出，此時我們應該把同一個桶里的數字按照次位的數字大小排好序，小的放在這個桶的前面，大的放在這個桶的后面，然后只需要在倒桶的時候按照從前到后的順序倒出去就ok了，而由于同一個桶中某兩個數字的先后順序是由處理這個兩個數字的先后順序決定的（就是先處理的先放，后處理的后放），而處理的順序就是這個兩個數字在本趟的待處理序列中的先后順序，也就意味著，本趟的待處理序列必須已經按照次位的順序排好了，于是就要求我們的多趟桶式排序應該是從低位到高位一趟一趟來，
下面舉個例子來展示上面的解釋，便于理解：

3.桶式排序的代碼實作

#include "List.h"
void Initial(List barral[])
{
	int i = 0;
	for (i = 0; i < 10; i++)
		barral[i] = MakeList();
}

void PrintNum(List L)
{
	Position islast=Last(L);
	Position P = L->next;
	while (P != islast)
	{
		printf("%d ", P->number);
		P = P->next;
	}
}

int main()
{
	int addone;
	int i, j;
	Position P;
	/*
		設定木桶，每個桶是一個鏈表，下面是對木桶含義的解釋：
		確定一位（個位、十位或者百位），10個元素分別代表10個木桶，每一個木桶用來裝在這位上數字相同的三位數.
		如：個位設定10個木桶，假設有116和226這兩個數字，則我們把它們裝在這10個桶中的6號桶（barrel[6])里
	*/
	List barral[10] = { 0 };
	Initial(barral);
	
	//創建一個鏈表用來裝待排序的數字
	List number=MakeList();
	printf("請輸入多個三位數以內的數字，我們將為你排序:>\n");
	//ctrl+z結束輸入
	while (scanf("%d", &addone) != EOF)
	{
		//將待排序的數字插入number這個鏈表中
		Insert(number, Last(number), addone);
	}
	//j表示當前處理的位，從個位先開始（j=1：個位、j=2：十位、j=3：百位）將每個待排序的數字按照當前位上的數字，裝進這個位中的10個桶中的一個
	for (j = 1; j <= 3;j++)
	{
		//遍歷處理每一個number中的待排序數字
		for (P = number->next; P != NULL; P = P->next)
		{
			//m表示當前處理位的權重（如：j=1表示個位，那么個位權重就是1，即m=1)
			int m=(int)pow(10,j-1);
			//i表示這個待處理的三位數在當前位上的數字
			int i = ((P->number) / m)%10;
			//將其放到當前位對應的桶里面去（放到對應桶的末尾）
			Insert(barral[i], Last(barral[i]), P->number);
		}
		/*
			至此所有數字都按照當前位的數字放入了當前位的10個桶中對應的某一個桶里去了，接下來更新裝有待排序的三位數的number鏈表的順序
		*/
		
		//首先將舊的number鏈表清空
		MakeEmpty(number);

		//然后把木桶里按照當前位的數字大小裝好的三位數按從小到大依次放入number鏈表中，作為下一次回圈的待排序數字序列
		
		//這里的i指的是當前位數字為i的木桶，這里是遍歷i，將每個i對應的木桶里的三位數放入number鏈表中
		for (i = 0; i < 10; i++)
		{
			P = barral[i]->next;
			while (P)
			{
				Insert(number, Last(number), P->number);
				P = P->next;
			}
			/*
				barral[i]這個木桶里的三位數都放到number里去后，就把它清空以供下一次回圈使用（下一個回圈中，作為裝下一位數字為i的三位數的桶）
				比如：barral[1]在當前這個外層回圈中表示個位數字為1的桶，等到下一個外層回圈后，barral[1]便作為十位數字為1的桶了
			*/
			MakeEmpty(barral[i]);
		}
	}
	//等到個位十位百位依次排序后，最后number中的順序就是從小到大的順序了
	PrintNum(number);
	return 0;
}

List.h和List.c

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>

#ifndef LIST_H
#define LIST_H
struct Node;
typedef struct Node* ptrNode;
typedef ptrNode Position;
typedef ptrNode List;


List MakeList();
void MakeEmpty(List L);
int IsEmpty(List L);
int Find(List L, Position P);
Position FindPositon(List L, int x);
Position FindPrevious(List L, int check);
Position First(List L);
Position Last(List L);
void Insert(List L, Position P,int addone);
void Delete(List L, int popone);

struct Node{
	int number;
	Position next;
};

#endif

#include "List.h"

List MakeList()
{
	List L = (List)malloc(sizeof(struct Node));
	L->next = NULL;
	return L;
}

void MakeEmpty(List L)
{
	Position P=L->next;
	Position tmp;
	L->next = NULL;
	while (P)
	{
		tmp = P;
		P = P->next;
		free(tmp);
	}
}

int IsEmpty(List L)
{
	return (!L->next)?1:0;
}

Position First(List L)
{
	return L->next;
}

Position Last(List L)
{
	Position P = L;
	while (P->next!=NULL)
		P = P->next;
	return P;
}

int Find(List L, Position P)
{
	Position tmp = L->next;
	while (tmp != NULL&&tmp != P)
		P = P->next;
	if (tmp)
		return 1;
	else
		return 0;
}

Position FindPosition(List L, int x)
{
	int i=1;
	Position P = L->next;
	while (P && i != x)
	{
		P = P->next;
		x++;
	}
	return P;
}

Position FindPrevious(List L, int check)
{
	Position P = L;
	while ( P->next && P->next->number != check)
		P = P->next;
	if (!P->next)
		return NULL;
	else
		return P;
}

void Insert(List L, Position P, int addone)
{
	Position tmp;
	tmp = malloc(sizeof(struct Node));
	if (tmp != NULL)
	{
		tmp->next = P->next;
		tmp->number = addone;
		P->next = tmp;
	}
}

void Delete(List L, int popone)
{
	Position P = FindPrevious(L, popone);
	if (P)
	{
		Position tmp = P->next;
		P->next = tmp->next;
		free(tmp);
	}
}