面試時(shí)的Java數(shù)據(jù)結(jié)構(gòu)與算法及面試評估表及評估標(biāo)準(zhǔn)

PAGE2 第19頁面試時(shí)的Java數(shù)據(jù)結(jié)構(gòu)與算法查找和排序算法是算法的入門知識，其經(jīng)典思想可以用于很多算法當(dāng)中。因?yàn)槠鋵?shí)現(xiàn)代碼較短，應(yīng)用較常見。所以在面試中經(jīng)常會(huì)問到排序算法及其相關(guān)的問題。但萬變不離其宗，只要熟悉了思想，靈活運(yùn)用也不是難事。一般在面試中最?？嫉氖强焖倥判蚝蜌w并排序，并且經(jīng)常有面試官要求現(xiàn)場寫出這兩種排序的代碼。對這兩種排序的代碼一定要信手拈來才行。還有插入排序、冒泡排序、堆排序、基數(shù)排序、桶排序等。面試官對于這些排序可能會(huì)要求比較各自的優(yōu)劣、各種算法的思想及其使用場景。還有要會(huì)分析算法的時(shí)間和空間復(fù)雜度。通常查找和排序算法的考察是面試的開始，如果這些問題回答不好，估計(jì)面試官都沒有繼續(xù)面試下去的興趣都沒了。所以想開個(gè)好頭就要把常見的排序算法思想及其特點(diǎn)要熟練掌握，有必要時(shí)要熟練寫出代碼。接下來我們就分析一下常見的排序算法及其使用場景。限于篇幅，某些算法的詳細(xì)演示和圖示請自行尋找詳細(xì)的參考。冒泡排序冒泡排序是最簡單的排序之一了，其大體思想就是通過與相鄰元素的比較和交換來把小的數(shù)交換到最前面。這個(gè)過程類似于水泡向上升一樣，因此而得名。舉個(gè)栗子，對5,3,8,6,4這個(gè)無序序列進(jìn)行冒泡排序。首先從后向前冒泡，4和6比較，把4交換到前面，序列變成5,3,8,4,6。同理4和8交換，變成5,3,4,8,6,3和4無需交換。5和3交換，變成3,5,4,8,6,3.這樣一次冒泡就完了，把最小的數(shù)3排到最前面了。對剩下的序列依次冒泡就會(huì)得到一個(gè)有序序列。冒泡排序的時(shí)間復(fù)雜度為O(n^2)。實(shí)現(xiàn)代碼：/***@Description:冒泡排序算法實(shí)現(xiàn)*@author王旭*/publicclassBubbleSort{publicstaticvoidbubbleSort(int[]arr){if(arr==null||arr.length==0)return;for(inti=0;i){for(intj=arr.length-1;j>i;j--){if(arr[j]]){swap(arr,j-1,j);}}}}publicstaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}選擇排序選擇排序的思想其實(shí)和冒泡排序有點(diǎn)類似，都是在一次排序后把最小的元素放到最前面。但是過程不同，冒泡排序是通過相鄰的比較和交換。而選擇排序是通過對整體的選擇。舉個(gè)栗子，對5,3,8,6,4這個(gè)無序序列進(jìn)行簡單選擇排序，首先要選擇5以外的最小數(shù)來和5交換，也就是選擇3和5交換，一次排序后就變成了3,5,8,6,4.對剩下的序列一次進(jìn)行選擇和交換，最終就會(huì)得到一個(gè)有序序列。其實(shí)選擇排序可以看成冒泡排序的優(yōu)化，因?yàn)槠淠康南嗤皇沁x擇排序只有在確定了最小數(shù)的前提下才進(jìn)行交換，大大減少了交換的次數(shù)。選擇排序的時(shí)間復(fù)雜度為O(n^2)。實(shí)現(xiàn)代碼：/***@Description:簡單選擇排序算法的實(shí)現(xiàn)*@author王旭*/publicclassSelectSort{publicstaticvoidselectSort(int[]arr){if(arr==null||arr.length==0)return;intminIndex=0;for(inti=0;i//只需要比較n-1次minIndex=i;for(intj=i+1;j//從i+1開始比較，因?yàn)閙inIndex默認(rèn)為i了，i就沒必要比了。if(arr[j]arr[minIndex]){minIndex=j;}}if(minIndex!=i){//如果minIndex不為i，說明找到了更小的值，交換之。swap(arr,i,minIndex);}}}publicstaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}插入排序插入排序不是通過交換位置而是通過比較找到合適的位置插入元素來達(dá)到排序的目的的。相信大家都有過打撲克牌的經(jīng)歷，特別是牌數(shù)較大的。在分牌時(shí)可能要整理自己的牌，牌多的時(shí)候怎么整理呢？就是拿到一張牌，找到一個(gè)合適的位置插入。這個(gè)原理其實(shí)和插入排序是一樣的。舉個(gè)栗子，對5,3,8,6,4這個(gè)無序序列進(jìn)行簡單插入排序，首先假設(shè)第一個(gè)數(shù)的位置時(shí)正確的，想一下在拿到第一張牌的時(shí)候，沒必要整理。然后3要插到5前面，把5后移一位，變成3,5,8,6,4.想一下整理牌的時(shí)候應(yīng)該也是這樣吧。然后8不用動(dòng)，6插在8前面，8后移一位，4插在5前面，從5開始都向后移一位。注意在插入一個(gè)數(shù)的時(shí)候要保證這個(gè)數(shù)前面的數(shù)已經(jīng)有序。簡單插入排序的時(shí)間復(fù)雜度也是O(n^2)。實(shí)現(xiàn)代碼：/***@Description:簡單插入排序算法實(shí)現(xiàn)*@author王旭*/publicclassInsertSort{publicstaticvoidinsertSort(int[]arr){if(arr==null||arr.length==0)return;for(inti=1;i//假設(shè)第一個(gè)數(shù)位置時(shí)正確的；要往后移，必須要假設(shè)第一個(gè)。intj=i;inttarget=arr[i];//待插入的//后移while(j>0&target]){arr[j]=arr[j-1];j--;}//插入arr[j]=target;}}}快速排序快速排序一聽名字就覺得很高端，在實(shí)際應(yīng)用當(dāng)中快速排序確實(shí)也是表現(xiàn)最好的排序算法?？焖倥判螂m然高端，但其實(shí)其思想是來自冒泡排序，冒泡排序是通過相鄰元素的比較和交換把最小的冒泡到最頂端，而快速排序是比較和交換小數(shù)和大數(shù)，這樣一來不僅把小數(shù)冒泡到上面同時(shí)也把大數(shù)沉到下面。舉個(gè)栗子：對5,3,8,6,4這個(gè)無序序列進(jìn)行快速排序，思路是右指針找比基準(zhǔn)數(shù)小的，左指針找比基準(zhǔn)數(shù)大的，交換之。5,3,8,6,4用5作為比較的基準(zhǔn)，最終會(huì)把5小的移動(dòng)到5的左邊，比5大的移動(dòng)到5的右邊。5,3,8,6,4首先設(shè)置i,j兩個(gè)指針分別指向兩端，j指針先掃描（思考一下為什么？）4比5小停止。然后i掃描，8比5大停止。交換i,j位置。5,3,4,6,8然后j指針再掃描，這時(shí)j掃描4時(shí)兩指針相遇。停止。然后交換4和基準(zhǔn)數(shù)。4,3,5,6,8一次劃分后達(dá)到了左邊比5小，右邊比5大的目的。之后對左右子序列遞歸排序，最終得到有序序列。上面留下來了一個(gè)問題為什么一定要j指針先動(dòng)呢？首先這也不是絕對的，這取決于基準(zhǔn)數(shù)的位置，因?yàn)樵谧詈髢蓚€(gè)指針相遇的時(shí)候，要交換基準(zhǔn)數(shù)到相遇的位置。一般選取第一個(gè)數(shù)作為基準(zhǔn)數(shù)，那么就是在左邊，所以最后相遇的數(shù)要和基準(zhǔn)數(shù)交換，那么相遇的數(shù)一定要比基準(zhǔn)數(shù)小。所以j指針先移動(dòng)才能先找到比基準(zhǔn)數(shù)小的數(shù)。快速排序是不穩(wěn)定的，其時(shí)間平均時(shí)間復(fù)雜度是O(nlgn)。實(shí)現(xiàn)代碼：/***@Description:實(shí)現(xiàn)快速排序算法*@author王旭*/publicclassQuickSort{//一次劃分publicstaticintpartition(int[]arr,intleft,intright){intpivotKey=arr[left];intpivotPointer=left;while(leftright){while(left=pivotKey)right--;while(leftpivotKey)left++;swap(arr,left,right);//把大的交換到右邊，把小的交換到左邊。}swap(arr,pivotPointer,left);//最后把pivot交換到中間returnleft;}publicstaticvoidquickSort(int[]arr,intleft,intright){if(left>=right)return;intpivotPos=partition(arr,left,right);quickSort(arr,left,pivotPos-1);quickSort(arr,pivotPos+1,right);}publicstaticvoidsort(int[]arr){if(arr==null||arr.length==0)return;quickSort(arr,0,arr.length-1);}publicstaticvoidswap(int[]arr,intleft,intright){inttemp=arr[left];arr[left]=arr[right];arr[right]=temp;}}其實(shí)上面的代碼還可以再優(yōu)化，上面代碼中基準(zhǔn)數(shù)已經(jīng)在pivotKey中保存了，所以不需要每次交換都設(shè)置一個(gè)temp變量，在交換左右指針的時(shí)候只需要先后覆蓋就可以了。這樣既能減少空間的使用還能降低賦值運(yùn)算的次數(shù)。優(yōu)化代碼如下：/***@Description:實(shí)現(xiàn)快速排序算法*@author王旭*/publicclassQuickSort{/***劃分*@paramarr*@paramleft*@paramright*@return*/publicstaticintpartition(int[]arr,intleft,intright){intpivotKey=arr[left];while(leftright){while(left=pivotKey)right--;arr[left]=arr[right];//把小的移動(dòng)到左邊while(leftpivotKey)left++;arr[right]=arr[left];//把大的移動(dòng)到右邊}arr[left]=pivotKey;//最后把pivot賦值到中間returnleft;}/***遞歸劃分子序列*@paramarr*@paramleft*@paramright*/publicstaticvoidquickSort(int[]arr,intleft,intright){if(left>=right)return;intpivotPos=partition(arr,left,right);quickSort(arr,left,pivotPos-1);quickSort(arr,pivotPos+1,right);}publicstaticvoidsort(int[]arr){if(arr==null||arr.length==0)return;quickSort(arr,0,arr.length-1);}}總結(jié)快速排序的思想：冒泡+二分+遞歸分治，慢慢體會(huì)。。。堆排序堆排序是借助堆來實(shí)現(xiàn)的選擇排序，思想同簡單的選擇排序，以下以大頂堆為例。注意：如果想升序排序就使用大頂堆，反之使用小頂堆。原因是堆頂元素需要交換到序列尾部。首先，實(shí)現(xiàn)堆排序需要解決兩個(gè)問題：如何由一個(gè)無序序列鍵成一個(gè)堆？如何在輸出堆頂元素之后，調(diào)整剩余元素成為一個(gè)新的堆？第一個(gè)問題，可以直接使用線性數(shù)組來表示一個(gè)堆，由初始的無序序列建成一個(gè)堆就需要自底向上從第一個(gè)非葉元素開始挨個(gè)調(diào)整成一個(gè)堆。第二個(gè)問題，怎么調(diào)整成堆？首先是將堆頂元素和最后一個(gè)元素交換。然后比較當(dāng)前堆頂元素的左右孩子節(jié)點(diǎn)，因?yàn)槌水?dāng)前的堆頂元素，左右孩子堆均滿足條件，這時(shí)需要選擇當(dāng)前堆頂元素與左右孩子節(jié)點(diǎn)的較大者（大頂堆）交換，直至葉子節(jié)點(diǎn)。我們稱這個(gè)自堆頂自葉子的調(diào)整成為篩選。從一個(gè)無序序列建堆的過程就是一個(gè)反復(fù)篩選的過程。若將此序列看成是一個(gè)完全二叉樹，則最后一個(gè)非終端節(jié)點(diǎn)是n/2取底個(gè)元素，由此篩選即可。舉個(gè)栗子：49,38,65,97,76,13,27,49序列的堆排序建初始堆和調(diào)整的過程如下：實(shí)現(xiàn)代碼：/***@Description:堆排序算法的實(shí)現(xiàn)，以大頂堆為例。*@author王旭*/publicclassHeapSort{/***堆篩選，除了start之外，start~end均滿足大頂堆的定義。*調(diào)整之后start~end稱為一個(gè)大頂堆。*@paramarr待調(diào)整數(shù)組*@paramstart起始指針*@paramend結(jié)束指針*/publicstaticvoidheapAdjust(int[]arr,intstart,intend){inttemp=arr[start];for(inti=2*start+1;i){//左右孩子的節(jié)點(diǎn)分別為2*i+1,2*i+2//選擇出左右孩子較小的下標(biāo)if(i]){i++;}if(temp>=arr[i]){break;//已經(jīng)為大頂堆，=保持穩(wěn)定性。}arr[start]=arr[i];//將子節(jié)點(diǎn)上移start=i;//下一輪篩選}arr[start]=temp;//插入正確的位置}publicstaticvoidheapSort(int[]arr){if(arr==null||arr.length==0)return;//建立大頂堆for(inti=arr.length/2;i>=0;i--){heapAdjust(arr,i,arr.length-1);}for(inti=arr.length-1;i>=0;i--){swap(arr,0,i);heapAdjust(arr,0,i-1);}}publicstaticvoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}}希爾排序希爾排序是插入排序的一種高效率的實(shí)現(xiàn)，也叫縮小增量排序。簡單的插入排序中，如果待排序列是正序時(shí)，時(shí)間復(fù)雜度是O(n)，如果序列是基本有序的，使用直接插入排序效率就非常高。希爾排序就利用了這個(gè)特點(diǎn)?；舅枷胧牵合葘⒄麄€(gè)待排記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個(gè)序列中的記錄基本有序時(shí)再對全體記錄進(jìn)行一次直接插入排序。舉個(gè)栗子：從上述排序過程可見，希爾排序的特點(diǎn)是，子序列的構(gòu)成不是簡單的逐段分割，而是將某個(gè)相隔某個(gè)增量的記錄組成一個(gè)子序列。如上面的例子，第一堂排序時(shí)的增量為5，第二趟排序的增量為3。由于前兩趟的插入排序中記錄的關(guān)鍵字是和同一子序列中的前一個(gè)記錄的關(guān)鍵字進(jìn)行比較，因此關(guān)鍵字較小的記錄就不是一步一步地向前挪動(dòng)，而是跳躍式地往前移，從而使得進(jìn)行最后一趟排序時(shí)，整個(gè)序列已經(jīng)做到基本有序，只要作記錄的少量比較和移動(dòng)即可。因此希爾排序的效率要比直接插入排序高。希爾排序的分析是復(fù)雜的，時(shí)間復(fù)雜度是所取增量的函數(shù)，這涉及一些數(shù)學(xué)上的難題。但是在大量實(shí)驗(yàn)的基礎(chǔ)上推出當(dāng)n在某個(gè)范圍內(nèi)時(shí)，時(shí)間復(fù)雜度可以達(dá)到O(n^1.3)。實(shí)現(xiàn)代碼：/***@Description:希爾排序算法實(shí)現(xiàn)*@author王旭*/publicclassShellSort{/***希爾排序的一趟插入*@paramarr待排數(shù)組*@paramd增量*/publicstaticvoidshellInsert(int[]arr,intd){for(inti=d;i){intj=i-d;inttemp=arr[i];//記錄要插入的數(shù)據(jù)while(j>=0&arr[j]>temp){//從后向前，找到比其小的數(shù)的位置arr[j+d]=arr[j];//向后挪動(dòng)j-=d;}if(j!=i-d)//存在比其小的數(shù)arr[j+d]=temp;}}publicstaticvoidshellSort(int[]arr){if(arr==null||arr.length==0)return;intd=arr.length/2;while(d>=1){shellInsert(arr,d);d/=2;}}}歸并排序歸并排序是另一種不同的排序方法，因?yàn)闅w并排序使用了遞歸分治的思想，所以理解起來比較容易。其基本思想是，先遞歸劃分子問題，然后合并結(jié)果。把待排序列看成由兩個(gè)有序的子序列，然后合并兩個(gè)子序列，然后把子序列看成由兩個(gè)有序序列。。。。。倒著來看，其實(shí)就是先兩兩合并，然后四四合并。。。最終形成有序序列?？臻g復(fù)雜度為O(n)，時(shí)間復(fù)雜度為O(nlogn)。舉個(gè)栗子：實(shí)現(xiàn)代碼：/***@Description:歸并排序算法的實(shí)現(xiàn)*@author王旭*/publicclassMergeSort{publicstaticvoidmergeSort(int[]arr){mSort(arr,0,arr.length-1);}/***遞歸分治*@paramarr待排數(shù)組*@paramleft左指針*@paramright右指針*/publicstaticvoidmSort(int[]arr,intleft,intright){if(left>=right)return;intmid=(left+right)/2;mSort(arr,left,mid);//遞歸排序左邊mSort(arr,mid+1,right);//遞歸排序右邊merge(arr,left,mid,right);//合并}/***合并兩個(gè)有序數(shù)組*@paramarr待合并數(shù)組*@paramleft左指針*@parammid中間指針*@paramright右指針*/publicstaticvoidmerge(int[]arr,intleft,intmid,intright){//[left,mid][mid+1,right]int[]temp=newint[right-left+1];//中間數(shù)組inti=left;intj=mid+1;intk=0;while(iright){if(arr[i]arr[j]){temp[k++]=arr[i++];}else{temp[k++]=arr[j++];}}while(imid){temp[k++]=arr[i++];}while(jright){temp[k++]=arr[j++];}for(intp=0;p){arr[left+p]=temp[p];}}}計(jì)數(shù)排序如果在面試中有面試官要求你寫一個(gè)O(n)時(shí)間復(fù)雜度的排序算法，你千萬不要立刻說：這不可能！雖然前面基于比較的排序的下限是O(nlogn)。但是確實(shí)也有線性時(shí)間復(fù)雜度的排序，只不過有前提條件，就是待排序的數(shù)要滿足一定的范圍的整數(shù)，而且計(jì)數(shù)排序需要比較多的輔助空間。其基本思想是，用待排序的數(shù)作為計(jì)數(shù)數(shù)組的下標(biāo)，統(tǒng)計(jì)每個(gè)數(shù)字的個(gè)數(shù)。然后依次輸出即可得到有序序列。實(shí)現(xiàn)代碼：/***@Description:計(jì)數(shù)排序算法實(shí)現(xiàn)*@author王旭*/publicclassCountSort{publicstaticvoidcountSort(int[]arr){if(arr==null||arr.length==0)return;intmax=max(arr);int[]count=newint[max+1];Arrays.fill(count,0);for(inti=0;i){count[arr[i]]++;}intk=0;for(inti=0;i){for(intj=0;j){arr[k++]=i;}}}publicstaticintmax(int[]arr){intmax=Integer.MIN_VALUE;for(intele:rr){if(ele>max)max=ele;}returnmax;}}桶排序桶排序算是計(jì)數(shù)排序的一種改進(jìn)和推廣，但是網(wǎng)上有許多資料把計(jì)數(shù)排序和桶排序混為一談。其實(shí)桶排序要比計(jì)數(shù)排序復(fù)雜許多。桶排序的基本思想：假設(shè)有一組長度為N的待排關(guān)鍵字序列K[1….n]。首先將這個(gè)序列劃分成M個(gè)的子區(qū)間(桶)。然后基于某種映射函數(shù)，將待排序列的關(guān)鍵字k映射到第i個(gè)桶中(即桶數(shù)組B的下標(biāo)i)，那么該關(guān)鍵字k就作為B[i]中的元素(每個(gè)桶B[i]都是一組大小為N/M的序列)。接著對每個(gè)桶B[i]中的所有元素進(jìn)行比較排序(可以使用快排)。然后依次枚舉輸出B[0]….B[M]中的全部內(nèi)容即是一個(gè)有序序列。bindex=f(key)其中，bindex為桶數(shù)組B的下標(biāo)(即第bindex個(gè)桶),k為待排序列的關(guān)鍵字。桶排序之所以能夠高效，其關(guān)鍵在于這個(gè)映射函數(shù)，它必須做到：如果關(guān)鍵字k1舉個(gè)栗子：假如待排序列K={49、38、35、97、76、73、27、49}。這些數(shù)據(jù)全部在1—100之間。因此我們定制10個(gè)桶，然后確定映射函數(shù)f(k)=k/10。則第一個(gè)關(guān)鍵字49將定位到第4個(gè)桶中(49/10=4)。依次將所有關(guān)鍵字全部堆入桶中，并在每個(gè)非空的桶中進(jìn)行快速排序后得到如圖所示。只要順序輸出每個(gè)B[i]中的數(shù)據(jù)就可以得到有序序列了。桶排序分析：桶排序利用函數(shù)的映射關(guān)系，減少了幾乎所有的比較工作。實(shí)際上，桶排序的f(k)值的計(jì)算，其作用就相當(dāng)于快排中劃分，希爾排序中的子序列，歸并排序中的子問題，已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對桶中的少量數(shù)據(jù)做先進(jìn)的比較排序即可。對N個(gè)關(guān)鍵字進(jìn)行桶排序的時(shí)間復(fù)雜度分為兩個(gè)部分：(1)循環(huán)計(jì)算每個(gè)關(guān)鍵字的桶映射函數(shù)，這個(gè)時(shí)間復(fù)雜度是O(N)。(2)利用先進(jìn)的比較排序算法對每個(gè)桶內(nèi)的所有數(shù)據(jù)進(jìn)行排序，其時(shí)間復(fù)雜度為∑O(Ni*logNi)。其中Ni為第i個(gè)桶的數(shù)據(jù)量。很顯然，第(2)部分是桶排序性能好壞的決定因素。盡量減少桶內(nèi)數(shù)據(jù)的數(shù)量是提高效率的唯一辦法(因?yàn)榛诒容^排序的最好平均時(shí)間復(fù)雜度只能達(dá)到O(N*logN)了)。因此，我們需要盡量做到下面兩點(diǎn)：(1)映射函數(shù)f(k)能夠?qū)個(gè)數(shù)據(jù)平均的分配到M個(gè)桶中，這樣每個(gè)桶就有[N/M]個(gè)數(shù)據(jù)量。(2)盡量的增大桶的數(shù)量。極限情況下每個(gè)桶只能得到一個(gè)數(shù)據(jù)，這樣就完全避開了桶內(nèi)數(shù)據(jù)的“比較”排序操作。當(dāng)然，做到這一點(diǎn)很不容易，數(shù)據(jù)量巨大的情況下，f(k)函數(shù)會(huì)使得桶集合的數(shù)量巨大，空間浪費(fèi)嚴(yán)重。這就是一個(gè)時(shí)間代價(jià)和空間代價(jià)的權(quán)衡問題了。對于N個(gè)待排數(shù)據(jù)，M個(gè)桶，平均每個(gè)桶[N/M]個(gè)數(shù)據(jù)的桶排序平均時(shí)間復(fù)雜度為：O(N)+O(M(N/M)log(N/M))=O(N+N(logN-logM))=O(N+NlogN-N*logM)當(dāng)N=M時(shí)，即極限情況下每個(gè)桶只有一個(gè)數(shù)據(jù)時(shí)。桶排序的最好效率能夠達(dá)到O(N)。總結(jié)：桶排序的平均時(shí)間復(fù)雜度為線性的O(N+C)，其中C=N*(logN-logM)。如果相對于同樣的N，桶數(shù)量M越大，其效率越高，最好的時(shí)間復(fù)雜度達(dá)到O(N)。當(dāng)然桶排序的空間復(fù)雜度為O(N+M)，如果輸入數(shù)據(jù)非常龐大，而桶的數(shù)量也非常多，則空間代價(jià)無疑是昂貴的。此外，桶排序是穩(wěn)定的。實(shí)現(xiàn)代碼：/***@Description:桶排序算法實(shí)現(xiàn)*@author王旭*/publicclassBucketSort{publicstaticvoidbucketSort(int[]arr){if(arr==null&arr.length==0)return;intbucketNums=10;//這里默認(rèn)為10，規(guī)定待排數(shù)[0,100)List>buckets=newArrayList>();//桶的索引for(inti=0;i){buckets.add(newLinkedList());//用鏈表比較合適}//劃分桶for(inti=0;i){buckets.get(f(arr[i])).add(arr[i]);}//對每個(gè)桶進(jìn)行排序for(inti=0;i){if(!buckets.get(i).isEmpty()){Collections.sort(buckets.get(i));//對每個(gè)桶進(jìn)行快排}}//還原排好序的數(shù)組intk=0;for(Listbucket:buckets){for(intele:bucket){arr[k++]=ele;}}}/***映射函數(shù)*@paramx*@return*/publicstaticintf(intx){returnx/10;}}基數(shù)排序基數(shù)排序又是一種和前面排序方式不同的排序方式，基數(shù)排序不需要進(jìn)行記錄關(guān)鍵字之間的比較。基數(shù)排序是一種借助多關(guān)鍵字排序思想對單邏輯關(guān)鍵字進(jìn)行排序的方法。所謂的多關(guān)鍵字排序就是有多個(gè)優(yōu)先級不同的關(guān)鍵字。比如說成績的排序，如果兩個(gè)人總分相同，則語文高的排在前面，語文成績也相同則數(shù)學(xué)高的排在前面。。。如果對數(shù)字進(jìn)行排序，那么個(gè)位、十位、百位就是不同優(yōu)先級的關(guān)鍵字，如果要進(jìn)行升序排序，那么個(gè)位、十位、百位優(yōu)先級一次增加。基數(shù)排序是通過多次的收分配和收集來實(shí)現(xiàn)的，關(guān)鍵字優(yōu)先級低的先進(jìn)行分配和收集。舉個(gè)栗子：實(shí)現(xiàn)代碼：/***@Description:基數(shù)排序算法實(shí)現(xiàn)*@author王旭*/publicclassRadixSort{publicstaticvoidradixSort(int[]arr){if(arr==null&arr.length==0)return;intmaxBit=getMaxBit(arr);for(inti=1;i){List>buf=distribute(arr,i);//分配collecte(arr,buf);//收集}}/***分配*@paramarr待分配數(shù)組*@paramiBit要分配第幾位*@return*/publicstaticList>distribute(int[]arr,intiBit){List>buf=newArrayList>();for(intj=0;j){buf.add(newLinkedList());}for(inti=0;i){buf.get(getNBit(arr[i],iBit)).add(arr[i]);}returnbuf;}/***收集*@paramarr把分配的數(shù)據(jù)收集到arr中*@parambuf*/publicstaticvoidcollecte(int[]arr,List>buf){intk=0;for(Listbucket:buf){for(intele:bucket){arr[k++]=ele;}}}/***獲取最大位數(shù)*@paramx*@return*/publicstaticintgetMaxBit(int[]arr){intmax=Integer.MIN_VALUE;for(intele:arr){intlen=(ele+"").length();if(len>max)max=len;}returnmax;}/***獲取x的第n位，如果沒有則為0.*@paramx*@paramn*@return*/publicstaticintgetNBit(intx,intn){Stringsx=x+"";if(sx.length()n)return0;elsereturnsx.charAt(sx.length()-n)-'0';}}總結(jié)在前面的介紹和分析中我們提到了冒泡排序、選擇排序、插入排序三種簡單的排序及其變種快速排序、堆排序、希爾排序三種比較高效的排序。后面我們又分析了基于分治遞歸思想的歸并排序還有計(jì)數(shù)排序、桶排序、基數(shù)排序三種線性排序。我們可以知道排序算法要么簡單有效，要么是利用簡單排序的特點(diǎn)加以改進(jìn)，要么是以空間換取時(shí)間在特定情況下的高效排序。但是這些排序方法都不是固定不變的，需要結(jié)合具體的需求和場景來選擇甚至組合使用。才能達(dá)到高效穩(wěn)定的目的。沒有最好的排序，只有最適合的排序。下面就總結(jié)一下排序算法的各自的使用場景和適用場合。從平均時(shí)間來看，快速排序是效率最高的，但快速排序在最壞情況下的時(shí)間性能不如堆排序和歸并排序。而后者相比較的結(jié)果是，在n較大時(shí)歸并排序使用時(shí)間較少，但使用輔助空間較多。上面說的簡單排序包括除希爾排序之外的所有冒泡排序、插入排序、簡單選擇排序。其中直接插入排序最簡單，但序列基本有序或者n較小時(shí)，直接插入排序是好的方法，因此常將它和其他的排序方法，如快速排序、歸并排序等結(jié)合在一起使用?；鶖?shù)排序的時(shí)間復(fù)雜度也可以寫成O(d*n)。因此它最使用于n值很大而關(guān)鍵字較小的的序列。若關(guān)鍵字也很大，而序列中大多數(shù)記錄的最高關(guān)鍵字均不同，則亦可先按最高關(guān)鍵字不同，將序列分成若干小的子序列，而后進(jìn)行直接插入排序。從方法的穩(wěn)定性來比較，基數(shù)排序是穩(wěn)定的內(nèi)排方法，所有時(shí)間復(fù)雜度為O(n^2)的簡單排序也是穩(wěn)定的。但是快速排序、堆排序、希爾排序等時(shí)間性能較好的排序方法都是不穩(wěn)定的。穩(wěn)定性需要根據(jù)具體需求選擇。上面的算法實(shí)現(xiàn)大多數(shù)是使用線性存儲結(jié)構(gòu)，像插入排序這種算法用鏈表實(shí)現(xiàn)更好，省去了移動(dòng)元素的時(shí)間。具體的存儲結(jié)構(gòu)在具體的實(shí)現(xiàn)版本中也是不同的。附：基于比較排序算法時(shí)間下限為O(nlogn)的證明：基于比較排序下限的證明是通過決策樹證明的，決策樹的高度Ω（nlgn），這樣就得出了比較排序的下限。首先要引入決策樹。首先決策樹是一顆二叉樹，每個(gè)節(jié)點(diǎn)表示元素之間一組可能的排序，它予以京進(jìn)行的比較相一致，比較的結(jié)果是樹的邊。先來說明一些二叉樹的性質(zhì)，令T是深度為d的二叉樹，則T最多有2^片樹葉。具有L片樹葉的二叉樹的深度至少是logL。所以，對n個(gè)元素排序的決策樹必然有n!片樹葉（因?yàn)閚個(gè)數(shù)有n!種不同的大小關(guān)系），所以決策樹的深度至少是log(n!)，即至少需要log(n!)次比較。而log(n!)=logn+log(n-1)+log(n-2)+…+log2+log1>=logn+log(n-1)+log(n-2)+…+log(n/2)>=(n/2)log(n/2)>=(n/2)logn-n/2=O(nlogn)所以只用到比較的排序算法最低時(shí)間復(fù)雜度是O(nlogn)。面試評估表應(yīng)聘者姓名：_______________________應(yīng)聘職能/崗位：______________________1、盡職敬業(yè)及適應(yīng)力_____優(yōu)異_____優(yōu)_____良______中______差______未考核意見及提醒下一輪面試官或人力資源部注意的事項(xiàng)（如個(gè)人期望，某方面拿不準(zhǔn)的評估、地域靈活性等方面）部門負(fù)責(zé)人意見（如有非部門負(fù)責(zé)人擔(dān)當(dāng)面試官，可由面試官填寫意見，但需兩人同時(shí)簽名確認(rèn)）：_____________________________________面試官簽名/日期面試評估決定：□通過，進(jìn)入下一輪；□不通過。人力資源部意見：_____________________________________面試官簽名/日期面試評估決定：□通過，進(jìn)入下一輪；□不通過。推薦的職能、崗位、級別及地區(qū)：總經(jīng)理意見：_____________________________________面試官簽名/日期2、思考及解決問題能力_____優(yōu)異_____優(yōu)_____良______中______差3、協(xié)作領(lǐng)導(dǎo)能力_____優(yōu)異_____優(yōu)_____良______中______差______未考核4、職位所需專業(yè)經(jīng)驗(yàn)及水平（用人部門考核）_____優(yōu)異_____優(yōu)_____良______中______差5、學(xué)習(xí)創(chuàng)新能力_____優(yōu)異_____優(yōu)_____良______中______差______未考核6、溝通影響能力_____優(yōu)異_____優(yōu)_____良______中______差7、職能素質(zhì)（工程：工程師精神；研發(fā)設(shè)計(jì)：導(dǎo)演能力、研究精神；銷售管理：結(jié)果導(dǎo)向、突破常規(guī)、激情及抗壓能力；策劃推廣：市場敏銳度、導(dǎo)演能力；造價(jià)采購：忠誠自律、嚴(yán)密性/懷疑性；行政：效率/條理性）_____優(yōu)異_____優(yōu)_____良______中______差______未考核評估標(biāo)準(zhǔn)優(yōu)異優(yōu)良中差1、盡職敬業(yè)/適應(yīng)力有明確的事業(yè)心，目標(biāo)堅(jiān)定并堅(jiān)持不懈善于自我否定、突破和更新能帶動(dòng)周邊人員運(yùn)用高標(biāo)準(zhǔn)主動(dòng)引導(dǎo)組織層面的變革高度投入，充滿熱情有強(qiáng)烈的上進(jìn)心并向事業(yè)心轉(zhuǎn)化能主動(dòng)發(fā)現(xiàn)并自主設(shè)立利于組織發(fā)展的目標(biāo)并采取行動(dòng)勇于承擔(dān)挑戰(zhàn)自身局限的職責(zé)在變革中起到骨干作用有高度的責(zé)任心且有主動(dòng)性，對工作質(zhì)量、效率堅(jiān)持高標(biāo)準(zhǔn)能夠承擔(dān)額外的職責(zé)，能穩(wěn)定保持對工作的熱情有自知之明，有明確、合理的職業(yè)發(fā)展方向，且能平衡好公司利益與個(gè)人利益不斷給自己設(shè)定更高標(biāo)準(zhǔn)，積極要求進(jìn)步具備責(zé)任心能達(dá)到基本質(zhì)量標(biāo)準(zhǔn)及崗位期望值需他人幫助來維護(hù)工作熱情注重個(gè)人的發(fā)展，有基本的上進(jìn)心，但經(jīng)常不能平衡好個(gè)人發(fā)展與集體、公司發(fā)展的關(guān)系缺乏工作熱情，得過且過缺乏基本的責(zé)任心，時(shí)常導(dǎo)致缺位及責(zé)任事故極少主動(dòng)承擔(dān)額外職責(zé)既不關(guān)心公司發(fā)展，也不關(guān)心個(gè)人發(fā)展2、思考及解決問題能從全局高度分析解決多個(gè)相互交錯(cuò)的復(fù)雜問題善于尋找和整合內(nèi)外資源能夠在價(jià)值觀指導(dǎo)下工作能夠在高度不確定性及模糊性的環(huán)境中輕松工作能運(yùn)用建立在知識、實(shí)踐基礎(chǔ)上的直覺進(jìn)行重大判斷能夠管理復(fù)雜的組織變革能在原則指導(dǎo)下工作，舉一反三在達(dá)成工作主要目標(biāo)的基礎(chǔ)上創(chuàng)造附加價(jià)值能獨(dú)立地、系統(tǒng)地解決問題善于抓住根本原因有處理復(fù)雜問題的成功實(shí)例擅于平衡運(yùn)用數(shù)據(jù)、經(jīng)驗(yàn)、直覺能夠處理不斷變化的問題能夠在不確定性及模糊中工作善于復(fù)雜問題簡單化始終把握工作目的：結(jié)果導(dǎo)向且客戶導(dǎo)向能多角度看待同一個(gè)問題，有獨(dú)立的系統(tǒng)分析能力能在復(fù)雜的信息中抓住要點(diǎn)善于運(yùn)用組織內(nèi)資源解決問題能同時(shí)處理多個(gè)重點(diǎn)工作能夠自主設(shè)定系統(tǒng)的工作計(jì)劃能夠在方向指導(dǎo)下工作，且能理解和接受工作、期望中的不確定性及模糊性能夠在計(jì)劃和規(guī)范指導(dǎo)下工作，解決常規(guī)問題能夠跟進(jìn)落實(shí)，注重關(guān)鍵細(xì)節(jié)在無指導(dǎo)下容易喪失結(jié)果導(dǎo)向及客戶導(dǎo)向有邏輯思維能力，但需他人幫助才能進(jìn)行系統(tǒng)分析判斷能尋求他人幫助解決問題無法接受模糊性及不確定性想不清楚，缺乏邏輯需要他人幫助進(jìn)行邏輯判斷及解決常規(guī)問題沒有詳細(xì)、具體的指令就會(huì)出錯(cuò)不會(huì)主動(dòng)尋求他人幫助不能主動(dòng)跟進(jìn)落實(shí)3、協(xié)作及領(lǐng)導(dǎo)能夠培養(yǎng)他人的事業(yè)心及使命感能夠創(chuàng)造并利用差異能夠產(chǎn)生其他領(lǐng)導(dǎo)者能做出痛苦而正確的決定能夠主導(dǎo)團(tuán)隊(duì)的氛圍，統(tǒng)一團(tuán)隊(duì)的價(jià)值觀能夠利用差異，用好不同的人能有效授權(quán)能夠創(chuàng)造團(tuán)結(jié)、高效的工作氛圍有高質(zhì)量的團(tuán)隊(duì)管理經(jīng)驗(yàn)?zāi)芴幚韱T工低績效接受差異，能主動(dòng)與不同人建立雙贏關(guān)系能與棘手的人協(xié)作有發(fā)展他人的實(shí)際行動(dòng)和能力在團(tuán)隊(duì)中總能貢獻(xiàn)有價(jià)值的意見及行為善于主動(dòng)補(bǔ)位以及敦促上下游能夠承認(rèn)、尊重差異，但在關(guān)系處理中處于被動(dòng)能與一般人順暢合作，但難以與棘手的人協(xié)作能接受甚至尋求他人意見反饋難于與其他人合作消極避免沖突或經(jīng)常被人利用在協(xié)作中找不準(zhǔn)自己的角色4、學(xué)習(xí)創(chuàng)新善于創(chuàng)造學(xué)習(xí)創(chuàng)新的氛圍能夠在學(xué)習(xí)和總結(jié)中形成實(shí)質(zhì)性、規(guī)律性認(rèn)識能指導(dǎo)他人進(jìn)行創(chuàng)新能系統(tǒng)性保持創(chuàng)新結(jié)果勇于突破舊的規(guī)制，建立新規(guī)則有過成功創(chuàng)新的事例善于主動(dòng)淘汰過時(shí)的觀念、方法、技能能將知識迅速轉(zhuǎn)換成新方法能比較熟練順暢地進(jìn)行創(chuàng)新要素的組合主動(dòng)尋找多種學(xué)習(xí)資源能夠?qū)W以致用主動(dòng)改進(jìn)工作方法、流程在工作中是有心人，不斷捕捉自己和別人哪怕稍縱即逝的火花能夠及時(shí)主動(dòng)總結(jié)經(jīng)驗(yàn)教訓(xùn)有主動(dòng)淘汰過時(shí)的觀念技能的意識有學(xué)習(xí)方向，注重不斷學(xué)習(xí)能應(yīng)用他人行之有效的方法在指導(dǎo)下可以進(jìn)行小的改進(jìn)能夠按照要求進(jìn)行總結(jié)反思被動(dòng)學(xué)習(xí)沒有明確學(xué)習(xí)方向不能提出新主意5、溝通影響善于宣傳鼓動(dòng)，爭取支持能夠迅速建立信任形成自己的獨(dú)特影響風(fēng)格和人格影響力能夠處理棘手的影響對象能夠敏銳地感知他人的需求能簡單易懂地講解復(fù)雜問題能在壓力條件下進(jìn)行溝通影響能夠通過溝通影響激發(fā)行動(dòng)能夠在目標(biāo)執(zhí)行中及時(shí)有效地與相關(guān)人員保持必要的溝通能根據(jù)對象調(diào)整個(gè)人溝通方式能夠調(diào)動(dòng)他人的溝通興趣能與溝通技能不足的人溝通有主動(dòng)影響的意識能夠清楚表達(dá)及接收信息能夠抓住溝通要點(diǎn)如對方溝通技能也不足，難以達(dá)成溝通效果當(dāng)需要時(shí)，能夠被動(dòng)進(jìn)行關(guān)鍵的溝通表達(dá)不清晰、無條理我行我素，很少與人溝通經(jīng)常跑題對別人的意見和需求不敏感6、客戶導(dǎo)向?qū)⒖蛻糇優(yōu)榛锇槟軌蛞龑?dǎo)客戶的需要能夠分析挖掘客戶潛在需要能夠理性分析客戶需要能夠管理客戶期望能主動(dòng)、系統(tǒng)挖掘客戶的需要主動(dòng)去滿足客戶的需要，甚至改變自己的行為方式或工作重點(diǎn)能夠準(zhǔn)確定義內(nèi)外客戶尊重客戶需要，能夠傾聽客戶的需要不知道誰是客戶不關(guān)心客戶需求職能素質(zhì)在所在職能內(nèi)是出類拔萃的（90分位以上）優(yōu)于職能內(nèi)大多數(shù)員工（70分位以上）與職能內(nèi)大多數(shù)員工相類似不如職能內(nèi)大多數(shù)員工（30分位以下）在職能人員中落后的（10分位以下）專業(yè)能力是所從事專業(yè)領(lǐng)域的高手或?qū)＜夷芙淌诤桶l(fā)展他人在所從事專業(yè)領(lǐng)域的知識和技能能用所從事專業(yè)領(lǐng)域的知識和技能獨(dú)立而有效地工作具有所從事專業(yè)領(lǐng)域的基礎(chǔ)知識和基本技能尚不具有所從事專業(yè)領(lǐng)域的基礎(chǔ)知識和基本技能文化適應(yīng)度在某些價(jià)值觀或原則領(lǐng)域，是公司文化的典型體現(xiàn)者，捍衛(wèi)者直至發(fā)展者個(gè)人行為與公司倡導(dǎo)的文化和價(jià)值觀沒有明顯的分歧；個(gè)人在公司文化環(huán)境里能有一定的歸屬感。理解、認(rèn)同公司倡導(dǎo)的文化和價(jià)值觀，但在持續(xù)體現(xiàn)上有較大差距或在個(gè)別價(jià)值觀或原則上有比較明顯分歧與公司倡導(dǎo)的文化格格不入，不能完全理解公司的文化和價(jià)值觀正面行為與負(fù)面行為盡職敬業(yè)正面行為負(fù)面行為對自己的崗位職責(zé)表現(xiàn)出高度的熱情和投入沒有自知之明也不主動(dòng)提高自我認(rèn)知勇于承擔(dān)有挑戰(zhàn)性的工作職責(zé)為不承擔(dān)責(zé)任尋找種種借口對承諾的事情積極、及時(shí)落實(shí)，不能按時(shí)實(shí)現(xiàn)時(shí)及早溝通在涉及利益沖突的情況下，公私不分明即使時(shí)間緊迫或有其他壓力，也堅(jiān)持保證工作的質(zhì)量不計(jì)成本、不講發(fā)展階段、不顧大局的精益求精為了達(dá)到更高質(zhì)量的結(jié)果，愿意付出額外的努力說一套做一套，言行不一致對簡單重復(fù)性的工作及小事每次都堅(jiān)持做好畫地為牢，不愿承擔(dān)新的職責(zé)敢于提出有建設(shè)性但不一定受歡迎的意見對批評和建議采取防御或推諉的態(tài)度以積極的態(tài)度接受批評和建議并采取行動(dòng)只把自己喜歡做的、習(xí)慣做的工作做好主動(dòng)做好自己崗位職責(zé)與上下游的銜接迎合領(lǐng)導(dǎo)的意見想法，明知行不通還表示支持或不表達(dá)意見主動(dòng)梳理本職崗位的工作流程及作業(yè)指導(dǎo)書隨意承諾但又不去兌現(xiàn)承諾建立與團(tuán)隊(duì)目標(biāo)相一致的個(gè)人績效目標(biāo)因急于求成而忽略了很多細(xì)節(jié)對自己的崗位職責(zé)有清晰的理解和認(rèn)知只關(guān)注對上級的承諾而忘記了對客戶的承諾不斷給自己設(shè)定更高的工作質(zhì)量標(biāo)準(zhǔn)看不到激情和活力，每天總是打不起精神通過各種途徑尋求他人反饋以不斷了解自己的優(yōu)點(diǎn)和不足在自我認(rèn)知的基礎(chǔ)上不斷明確自己的職業(yè)發(fā)展方向在預(yù)見或遇到風(fēng)險(xiǎn)時(shí)主動(dòng)向相關(guān)人員匯報(bào)及咨詢在公司內(nèi)外主動(dòng)維護(hù)公司的聲譽(yù)和品牌在工作中不斷探究提高工作效率