㈠ 基數排序怎麼排
.example-btn{color:#fff;background-color:#5cb85c;border-color:#4cae4c}.example-btn:hover{color:#fff;background-color:#47a447;border-color:#398439}.example-btn:active{background-image:none}div.example{width:98%;color:#000;background-color:#f6f4f0;background-color:#d0e69c;background-color:#dcecb5;background-color:#e5eecc;margin:005px0;padding:5px;border:1pxsolid#d4d4d4;background-image:-webkit-linear-gradient(#fff,#e5eecc100px);background-image:linear-gradient(#fff,#e5eecc100px)}div.example_code{line-height:1.4em;width:98%;background-color:#fff;padding:5px;border:1pxsolid#d4d4d4;font-size:110%;font-family:Menlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;word-break:break-all;word-wrap:break-word}div.example_result{background-color:#fff;padding:4px;border:1pxsolid#d4d4d4;width:98%}div.code{width:98%;border:1pxsolid#d4d4d4;background-color:#f6f4f0;color:#444;padding:5px;margin:0}div.codediv{font-size:110%}div.codediv,div.codep,div.example_codep{font-family:"couriernew"}pre{margin:15pxauto;font:12px/20pxMenlo,Monaco,Consolas,"AndaleMono","lucidaconsole","CourierNew",monospace;white-space:pre-wrap;word-break:break-all;word-wrap:break-word;border:1pxsolid#ddd;border-left-width:4px;padding:10px15px}排序演算法是《數據結構與演算法》中最基本的演算法之一。排序演算法可以分為內部排序和外部排序，內部排序是數據記錄在內存中進行排序，而外部排序是因排序的數據很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內部排序演算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸並排序、快速排序、堆排序、基數排序等。以下是基數排序演算法：
基數排序是一種非比較型整數排序演算法，其原理是將整數按位數切割成不同的數字，然後按每個位數分別比較。由於整數也可以表達字元串（比如名字或日期）和特定格式的浮點數，所以基數排序也不是只能使用於整數。
1.基數排序vs計數排序vs桶排序基數排序有兩種方法：
這三種排序演算法都利用了桶的概念，但對桶的使用方法上有明顯差異：
基數排序：根據鍵值的每位數字來分配桶；計數排序：每個桶只存儲單一鍵值；桶排序：每個桶存儲一定范圍的數值；2.LSD基數排序動圖演示
代碼實現javaScript實例//LSDRadixSortvarcounter=[];functionradixSort(arr,maxDigit){varmod=10;vardev=1;for(vari=0;i<maxDigit;i++,dev*=10,mod*=10){for(varj=0;j<arr.length;j++){varbucket=parseInt((arr[j]%mod)/dev);if(counter[bucket]==null){counter[bucket]=[];}counter[bucket].push(arr[j]);}varpos=0;for(varj=0;j<counter.length;j++){varvalue=null;if(counter[j]!=null){while((value=counter[j].shift())!=null){arr[pos++]=value;}}}}returnarr;}Java實例/***基數排序*考慮負數的情況還可以參考：https://code.i-harness.com/zh-CN/q/e98fa9*/{@Overridepublicint[]sort(int[]sourceArray)throwsException{//對arr進行拷貝，不改變參數內容int[]arr=Arrays.Of(sourceArray,sourceArray.length);intmaxDigit=getMaxDigit(arr);returnradixSort(arr,maxDigit);}/***獲取最高位數*/privateintgetMaxDigit(int[]arr){intmaxValue=getMaxValue(arr);returngetNumLenght(maxValue);}privateintgetMaxValue(int[]arr){intmaxValue=arr[0];for(intvalue:arr){if(maxValue<value){maxValue=value;}}returnmaxValue;}protectedintgetNumLenght(longnum){if(num==0){return1;}intlenght=0;for(longtemp=num;temp!=0;temp/=10){lenght++;}returnlenght;}privateint[]radixSort(int[]arr,intmaxDigit){intmod=10;intdev=1;for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){//考慮負數的情況，這里擴展一倍隊列數，其中[0-9]對應負數，[10-19]對應正數(bucket+10)int[][]counter=newint[mod*2][0];for(intj=0;j<arr.length;j++){intbucket=((arr[j]%mod)/dev)+mod;counter[bucket]=arrayAppend(counter[bucket],arr[j]);}intpos=0;for(int[]bucket:counter){for(intvalue:bucket){arr[pos++]=value;}}}returnarr;}/***自動擴容，並保存數據**@paramarr*@paramvalue*/privateint[]arrayAppend(int[]arr,intvalue){arr=Arrays.Of(arr,arr.length+1);arr[arr.length-1]=value;returnarr;}}php實例functionradixSort($arr,$maxDigit=null){if($maxDigit===null){$maxDigit=max($arr);}$counter=[];for($i=0;$i<$maxDigit;$i++){for($j=0;$j<count($arr);$j++){preg_match_all('/d/',(string)$arr[$j],$matches);$numArr=$matches[0];$lenTmp=count($numArr);$bucket=array_key_exists($lenTmp-$i-1,$numArr)?intval($numArr[$lenTmp-$i-1]):0;if(!array_key_exists($bucket,$counter)){$counter[$bucket]=[];}$counter[$bucket][]=$arr[$j];}$pos=0;for($j=0;$j<count($counter);$j++){$value=null;if($counter[$j]!==null){while(($value=array_shift($counter[$j]))!==null){$arr[$pos++]=$value;}}}}return$arr;}C++實例intmaxbit(intdata[],intn)//輔助函數，求數據的最大位數{intmaxData=data[0];///<最大數///先求出最大數，再求其位數，這樣有原先依次每個數判斷其位數，稍微優化點。for(inti=1;i<n;++i){if(maxData<data[i])maxData=data[i];}intd=1;intp=10;while(maxData>=p){//p*=10;//MaybeoverflowmaxData/=10;++d;}returnd;/*intd=1;//保存最大的位數intp=10;for(inti=0;i<n;++i){while(data[i]>=p){p*=10;++d;}}returnd;*/}voidradixsort(intdata[],intn)//基數排序{intd=maxbit(data,n);int*tmp=newint[n];int*count=newint[10];//計數器inti,j,k;intradix=1;for(i=1;i<=d;i++)//進行d次排序{for(j=0;j<10;j++)count[j]=0;//每次分配前清空計數器for(j=0;j<n;j++){k=(data[j]/radix)%10;//統計每個桶中的記錄數count[k]++;}for(j=1;j<10;j++)count[j]=count[j-1]+count[j];//將tmp中的位置依次分配給每個桶for(j=n-1;j>=0;j--)//將所有桶中記錄依次收集到tmp中{k=(data[j]/radix)%10;tmp[count[k]-1]=data[j];count[k]--;}for(j=0;j<n;j++)//將臨時數組的內容復制到data中data[j]=tmp[j];radix=radix*10;}delete[]tmp;delete[]count;}C實例#include<stdio.h>#defineMAX20//#defineSHOWPASS#defineBASE10voidprint(int*a,intn){inti;for(i=0;i<n;i++){printf("%d ",a[i]);}}voidradixsort(int*a,intn){inti,b[MAX],m=a[0],exp=1;for(i=1;i<n;i++){if(a[i]>m){m=a[i];}}while(m/exp>0){intbucket[BASE]={0};for(i=0;i<n;i++){bucket[(a[i]/exp)%BASE]++;}for(i=1;i<BASE;i++){bucket[i]+=bucket[i-1];}for(i=n-1;i>=0;i--){b[--bucket[(a[i]/exp)%BASE]]=a[i];}for(i=0;i<n;i++){a[i]=b[i];}exp*=BASE;#ifdefSHOWPASSprintf("
PASS:");print(a,n);#endif}}intmain(){intarr[MAX];inti,n;printf("Entertotalelements(n<=%d):",MAX);scanf("%d",&n);n=n<MAX?n:MAX;printf("Enter%dElements:",n);for(i=0;i<n;i++){scanf("%d",&arr[i]);}printf("
ARRAY:");print(&arr[0],n);radixsort(&arr[0],n);printf("
SORTED:");print(&arr[0],n);printf("
");return0;}Lua實例--獲取表中位數localmaxBit=function(tt)localweight=10;--十_制localbit=1;fork,vinpairs(tt)dowhilev>=weightdoweight=weight*10;bit=bit+1;endendreturnbit;end--基數排序localradixSort=function(tt)localmaxbit=maxBit(tt);localbucket={};localtemp={};localradix=1;fori=1,maxbitdoforj=1,10dobucket[j]=0;---清空桶endfork,vinpairs(tt)dolocalremainder=math.floor((v/radix))%10+1;bucket[remainder]=bucket[remainder]+1;--每_桶_量自_增加1endforj=2,10dobucket[j]=bucket[j-1]+bucket[j];--每個桶的數量=以前桶數量和+自個數量end--按照桶的位置，排序--這個是桶式排序，必須使用倒序，因為排序方法是從小到大，順序下來，會出現大的在小的上面清空。fork=#tt,1,-1dolocalremainder=math.floor((tt[k]/radix))%10+1;temp[bucket[remainder]]=tt[k];bucket[remainder]=bucket[remainder]-1;endfork,vinpairs(temp)dott[k]=v;endradix=radix*10;endend;參考地址：
https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/10.radixSort.md
https://zh.wikipedia.org/wiki/%E5%9F%BA%E6%95%B0%E6%8E%92%E5%BA%8F
以下是熱心網友對基數排序演算法的補充，僅供參考：熱心網友提供的補充1：
java代碼里，mod每次循環會乘10，但counter的行數是不需要變的，能包含[-9,9]就可以了。
for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){
//考慮負數的情況，這里擴展一倍隊列數，其中[0-9]對應負數，[10-19]對應正數(bucket+10)
int[][]counter=newint[20][0];
for(intj=0;j<arr.length;j++){
intbucket=((arr[j]%mod)/dev)+10;
counter[bucket]=arrayAppend(counter[bucket],arr[j]);
}
intpos=0;
for(int[]bucket:counter){
for(intvalue:bucket){
arr[pos++]=value;
}
}
}熱心網友提供的補充2：
艾孜爾江補充使用C#基數排序演算法如下:
///基數排序
staticvoidRadixSort(List<int>list)
{
intmaxValue=list.Max();//列表內部方法拿過來用用（在Linq中）
intit=0;//需要幾趟
//maxvalue9-199-2999-3
//10^0<=910^1>9it=1
//10^0<9910^1<9910^2>99it=2
while(Math.Pow(10,it)<=maxValue)
{
List<List<int>>buckets=newList<List<int>>(10);//分10個桶對應0-9
for(inti=0;i<10;i++)
{
buckets.Add(newList<int>());
}//列表初始化大小
for(inti=0;i<list.Count;i++)//入桶
{
//989it=0989/10^it=989989%10=9;
intdigit=(int)((list[i])/(Math.Pow(10,it))%10);//得到對應桶
buckets[digit].Add(list[i]);
}//全部入桶
list.Clear();//依次取出來
for(inti=0;i<buckets.Count;i++)
{
㈡ 選擇排序法復雜度
穩定性比較
插入排序、冒泡排序、二叉樹排序、二路歸並排序及其他線形排序是穩定的。
選擇排序、希爾排序、快速排序、堆排序是不穩定的。
時間復雜性比較
插入排序、冒泡排序最優為O(n),最壞為O(n^2),平均O(n^2）；
快速排序最優為O(nlogn),最壞為O(n^2),平均O(nlogn);
堆排序最優為O(nlogn),最壞為O(nlogn),平均O(nlogn);
線形排序的時間復雜性為O(n)。
輔助空間的比較
線形排序、歸並排序的輔助空間為O(n),快速排序的輔助空間為O(logn),其它排序的輔助空間為O(1)。
其它比較
插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時，這種排序能達到較快的速度。
反而在這種情況下，快速排序反而慢了。當n較小時，對穩定性不作要求時宜用選擇排序，對穩定性有要求時宜用插入或冒泡排序。
若待排序的記錄的關鍵字在一個明顯有限范圍內時,且空間允許時用桶排序。
當n較大時，關鍵字元素比較隨機，對穩定性沒要求宜用快速排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性有要求時，空間允許的情況下宜用歸並排序。
當n較大時，關鍵字元素可能出現本身是有序的，對穩定性沒有要求時宜用堆排序。
演算法描述太長了。
binary seach 二分查找啊。
6 層排序 乘3加1 Shell Sort Times 3 plus 1
7 層排序 乘4 Shell Sort Times 4
層排序？ 看名字是 希爾排序吧。
還有上面的名字也翻譯錯了。。。
這些演算法都很容易搜到的。
給你個網址吧：
http://www.nocow.cn/index.php/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95
不過是用PASCAL語言描述的，部分C++語言描述。
// 直接插入排序
void insertionSort( int *array )
{
int i, j;
int key;
for( i = 1; i < size; ++i )
{
key = array[i];
j = i - 1;
while( j >= 0 && array[j] > key )
{
array[j+1] = array[j];
--j;
}
array[j+1] = key;
}
}
// 折半插入排序
void binary_insertiont_sort( int *array )
{
for( int i = 1; i < size; ++i )
{
int key = array[i];
int low = 0;
int high = i - 1;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else
low = mid + 1;
}
for( int j = i - 1; j > high + 1; --j )
array[j+1] = array[j];
array[j] = key;
}
}
// 選擇排序
void selectSort( int *array )
{
int i, j, k;
for( i = 0; i < size - 1; ++i )
{
k = i;
for( j = i + 1; j < size; ++j )
if( array[k] > array[j] )
k = j;
if( k != i )
{
j = array[k];
array[k] = array[i];
array[i] = j;
}
}
}
// 二分查找法
void binarySeach( int *array, int key )
{
int low = 0;
int high = n - 1; // n是array的長度
int flag = 0;
while( low <= high )
{
int mid = ( low + high ) / 2;
if( array[mid] > key )
high = mid - 1;
else if( array[mid] < key )
low = mid + 1;
else
{
printf( "%d\n", mid+1 );
flag = 1;
break;
}
}
if( !flag )
printf( "NOFOUND!\n" );
}
其他的還沒寫。。