基數排序
原理
基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數排序法是屬于穩定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數，而m為堆數，在某些時候，基數排序法的效率高于其它的穩定性排序法，
//演算法8.11 歸并排序
#include <iostream>
using namespace std;
#define MAXSIZE 20 //順序表的最大長度
typedef struct
{
int key;
char *otherinfo;
}RedType;
typedef struct
{
RedType *r;
int length;
}SqList;
void Create_Sq(SqList &L)
{
int i,n;
cout<<"請輸入資料個數，不超過"<<MAXSIZE<<"個，"<<endl;
cin>>n; //輸入個數
cout<<"請輸入待排序的資料:\n";
while(n>MAXSIZE)
{
cout<<"個數超過上限，不能超過"<<MAXSIZE<<"，請重新輸入"<<endl;
cin>>n;
}
for(i=1;i<=n;i++)
{
cin>>L.r[i].key;
L.length++;
}
}
//用演算法8.10 相鄰兩個有序子序列的歸并
void Merge(RedType R[],RedType T[],int low,int mid,int high)
{
//將有序表R[low..mid]和R[mid+1..high]歸并為有序表T[low..high]
int i,j,k;
i=low; j=mid+1;k=low;
while(i<=mid&&j<=high)
{
//將R中記錄由小到大地并入T中
if(R[i].key<=R[j].key) T[k++]=R[i++];
else T[k++]=R[j++];
}
while(i<=mid) //將剩余的R[low..mid]復制到T中
T[k++]=R[i++];
while(j<=high) //將剩余的R[j.high]復制到T中
T[k++]=R[j++];
}//Merge
void MSort(RedType R[],RedType T[],int low,int high)
{
//R[low..high]歸并排序后放入T[low..high]中
int mid;
RedType *S=new RedType[MAXSIZE];
if(low==high) T[low]=R[low];
else
{
mid=(low+high)/2; //將當前序列一分為二，求出分裂點mid
MSort(R,S,low,mid); //對子序列R[low..mid] 遞回歸并排序，結果放入S[low..mid]
MSort(R,S,mid+1,high); //對子序列R[mid+1..high] 遞回歸并排序，結果放入S[mid+1..high]
Merge(S,T,low,mid,high); //將S[low..mid]和S [mid+1..high]歸并到T[low..high]
}//else
}// MSort
void MergeSort(SqList &L)
{
//對順序表L做歸并排序
MSort(L.r,L.r,1,L.length);
}//MergeSort
void show(SqList L)
{
int i;
for(i=1;i<=L.length;i++)
cout<<L.r[i].key<<endl;
}
void main()
{
SqList R;
R.r=new RedType[MAXSIZE+1];
R.length=0;
Create_Sq(R);
MergeSort(R);
cout<<"排序后的結果為："<<endl;
show(R);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/115754.html
標籤：其他
上一篇：排序-歸并排序