#include"stdio.h"
#include"stdlib.h"
#include"string.h"
#include <malloc.h>
#include "time.h"
//#include <conio.h>	// getch
#include <dos.h>   //getime()


#define MAX_NUM_OF_KEY 8            //關鍵字項數的最大基數，本設計中只用到5
#define RADIX 10                    //關鍵字基數，此時是十進制整數的基數
#define MAX_SPACE 10000

typedef int KyeType;
#define CHINESE 1      //語文
#define MATH 2         //數學
#define ENGLISH 3      //英語
#define XX 4           //x科  
#define TOTAL 5        //總分

typedef struct{
	char name[4];
	KyeType keys[MAX_NUM_OF_KEY+1];            //關鍵字
	int next;                                  //
}SLCell;                                       //靜態鏈表的節點類型

typedef struct{
	SLCell r[MAX_SPACE+1];
	int keynum;                                //記錄的當前關鍵字個數，這里是科目
	int recnum;                                //靜態鏈表的當前長度
}SLList;                                       //靜態鏈表類型  

typedef int ArrType[RADIX];                    //指針數組內容 

clock_t start,end; //時間變量，精確到ms！


SLList L, copy;               //用L創建一個副本copy，用來回復被排序的L，



void InitSLList(SLList &L,int num)             //num為關鍵字個數
{
	L.recnum=num;
	L.keynum=5;
}

//////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////內部穩定簡單選擇排序//////////////////////////////////////////////
int SelectMaxKey(SLList L,int key,int i)     //用于簡單排序
{
	int k,max=i;

	for( k=i; k<=L.recnum; k++ )
	{
		if(L.r[k].keys[key] > L.r[max].keys[key])
		{
			max=k;
		}
	}
	return max;
}
void SteadySort(SLList &L, int key)          //穩定排序  選擇關鍵字key排序    
{
	int i,j;
	SLCell T;
	for( i=1; i<=L.recnum; ++i )                //簡單選擇排序
    {
		j=SelectMaxKey(L,key,i);
		if(i!=j) 
		{
			T=L.r[i]; L.r[i]=L.r[j]; L.r[j]=T;		
		}
	}
}

/////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////　基數排序　　LSD　///////////////////////////////////////////////
int ord(int score , int i)
{
	int j;
	if(i==1) j=score%100%10;
	else 
		if(i==2) j=score%100/10;
		else j=score/100;
	return j;
}

void Distribute(SLCell r[], int i,ArrType &f, ArrType &e, int key)
{
	int j,p;
	for(j=0; j<RADIX; j++){ f[j]=0; e[j] = 0 ; }
	for(p=r[0].next; p; p=r[p].next)           //最后r[L.recnum].next是以0結束的
	{		
		j=ord(r[p].keys[key],i);
		if(!f[j]) f[j]=p;
		else 
		r[e[j]].next=p;

		e[j]=p;
	}
}

int succ(ArrType f,int &j)
{	

	while( !f[j] && j<RADIX ) 
	{j++;} 
	return j;
}

void Collect(SLCell r[], int i, ArrType f, ArrType e)
{
	int j=0,t=0;
	for(j=RADIX-1; j>=0 ; j-- )
	{
		if(f[j])
		{
			r[t].next=f[j];
			t=e[j];
		}
	}
	r[t].next=0;

/*	j=succ(f,j);   //找到第一個非空子表，succ為求后記函數  這種方法不好，麻煩 效率沒有上面的高！
    printf("\tjjj=%d\n",j);	
	r[0].next=f[j]; t=e[j];                    //r[0].next指向第一個非空子表中第一個節點
	printf("r[0].next=%d\t",r[0].next);
	while( j<RADIX )
	{	
		j++;

		for(j=succ(f,j); j<RADIX-1&&!f[j]; j=succ(f,j)) ;  //找到下一個非空子表
		if(f[j]) 
		{
			r[t].next=f[j];
			printf("r[%d].next=%d\tf[%d]=%d\n",t,r[t].next,j,f[j]);
			t=e[j]; 
		}
	}
*/
}

void RadixSort(SLList &L,short key)              // 用基數排序“分配”和“收集”
{
	ArrType f,e; 
	int i;
	for( i=1; i<=3; i++ )
	{	
		Distribute(L.r,i,f,e,key);
		Collect(L.r,i,f,e);
	}
}