【移動應(yīng)用開發(fā)技術(shù)】經(jīng)常被問到今天講解下排序算法七大步

由于這段時間在家辦公，所有有很多的時間來整理思路。今天主要簡單講解一下幾個排序算法剛好復(fù)工了，就到所謂的“金三銀四”了希望這段時間大家好好的整理下頭緒，爭取能拿到好的offer

相關(guān)內(nèi)容后續(xù)GitHub更新,想沖擊金三銀四的小伙伴可以找找看看，歡迎star（順手留下GitHub鏈接，需要獲取相關(guān)面試等內(nèi)容的可以自己去找）/xiangjiana/Android-MS(VX：m

相關(guān)內(nèi)容后續(xù)GitHub更新,想沖擊金三銀四的小伙伴可以找找看看，歡迎star（順手留下GitHub鏈接，需要獲取相關(guān)面試等內(nèi)容的可以自己去找）/xiangjiana/Android-MS(VX：m比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。針對所有的元素重復(fù)以上的步驟，除了最后一個。持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。Java實現(xiàn)加入標(biāo)記狀態(tài)flag若在一次冒泡中，沒有交換則說明可以停止減少運行時publicstaticvoidbubbleSort(int[]numbers){

inttemp=0;

intsize=numbers.length;

booleanflag=true;

for(inti=0;i<size-1&&flag;i++){

flag=false;

for(intj=0;j<size-1-i;j++){

if(numbers[j]>numbers[j+1])//交換兩數(shù)位置

{

temp=numbers[j];

numbers[j]=numbers[j+1];

numbers[j+1]=temp;

flag=true;

}

}

}

}在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止。Java實現(xiàn)publicstaticvoidselectSort(int[]numbers){

intsize=numbers.length;//數(shù)組長度

inttemp=0;//中間變量

for(inti=0;i<size-1;i++){

intk=i;//待確定的位置

//選擇出應(yīng)該在第i個位置的數(shù)

for(intj=size-1;j>i;j--){

if(numbers[j]<numbers[k]){

k=j;

}

}

//交換兩個數(shù)

temp=numbers[i];

numbers[i]=numbers[k];

numbers[k]=temp;

}

}時間復(fù)雜度O(n*n)性能上優(yōu)于冒泡排序交換次數(shù)少每步將一個待排序的記錄，按其順序碼大小插入到前面已經(jīng)排序的字序列的合適位置（從后向前找到合適位置后），直到全部插入排序完為止。Java實現(xiàn)publicstaticvoidinsertSort(int[]numbers){

intsize=numbers.length;

inttemp=0;

intj=0;

for(inti=1;i<size;i++){

temp=numbers[i];

//假如temp比前面的值小，則將前面的值后移

for(j=i;j>0&&temp<numbers[j-1];j--){

numbers[j]=numbers[j-1];

}

numbers[j]=temp;

}

}時間復(fù)雜度O(n*n)性能上優(yōu)于冒泡排序和選擇排序先將整個待排序的記錄序列分割成為若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行依次直接插入排序。Java實現(xiàn)/**

*希爾排序的原理:根據(jù)需求，如果你想要結(jié)果從小到大排列，它會首先將數(shù)組進行分組，然后將較小值移到前面，較大值

*移到后面，最后將整個數(shù)組進行插入排序，這樣比起一開始就用插入排序減少了數(shù)據(jù)交換和移動的次數(shù)，

*可以說希爾排序是加強版的插入排序拿數(shù)組5,2,8,9,1,3，4來說，數(shù)組長度為7，當(dāng)increment為3時，數(shù)組分為兩個序列

*5，2，8和9，1，3，4，第一次排序，9和5比較，1和2比較，3和8比較，4和比其下標(biāo)值小increment的數(shù)組值相比較

*此例子是按照從小到大排列，所以小的會排在前面，第一次排序后數(shù)組為5,1,3,4,2,8，9

*第一次后increment的值變?yōu)?/2=1,此時對數(shù)組進行插入排序，實現(xiàn)數(shù)組從大到小排

*/

publicstaticvoidshellSort(int[]data){

intj=0;

inttemp=0;

//每次將步長縮短為原來的一半

for(intincrement=data.length/2;increment>0;increment/=2){

for(inti=increment;i<data.length;i++){

temp=data[i];

for(j=i;j>=increment;j-=increment){

if(temp<data[j-increment])//從小到大排

{

data[j]=data[j-increment];

}else{

break;

}

}

data[j]=temp;

}

}堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進。堆的定義下：具有n個元素的序列（h2,h3,...,hn),當(dāng)且僅當(dāng)滿足（hi>=h3i,hi>=h3i+1）或（hi<=h3i,hi<=h3i+1）(i=1,2,...,n/2)時稱之為堆。在這里只討論滿足前者條件的堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最大項（大頂堆）。完全二叉樹可以很直觀地表示堆的結(jié)構(gòu)。堆頂為根，其它為左子樹、右子樹。思想:初始時把要排序的數(shù)的序列看作是一棵順序存儲的二叉樹，調(diào)整它們的存儲序，使之成為一個堆，這時堆的根節(jié)點的數(shù)最大。然后將根節(jié)點與堆的最后一個節(jié)點交換。然后對前面(n-1)個數(shù)重新調(diào)整使之成為堆。依此類推，直到只有兩個節(jié)點的堆，并對它們作交換，最后得到有n個節(jié)點的有序序列。從算法描述來看，堆排序需要兩個過程，一是建立堆，二是堆頂與堆的最后一個元素交換位置。所以堆排序有兩個函數(shù)組成。一是建堆的***函數(shù)，二是反復(fù)調(diào)用***函數(shù)實現(xiàn)排序的函數(shù)。Java實現(xiàn)publicstaticvoidheapSort(int[]a){

intarrayLength=a.length;

//循環(huán)建堆

for(inti=0;i<arrayLength-1;i++){

//建堆

buildMaxHeap(a,arrayLength-1-i);

//交換堆頂和最后一個元素

swap(a,0,arrayLength-1-i);

System.out.println(Arrays.toString(a));

}

}

//對data數(shù)組從0到lastIndex建大頂堆

publicstaticvoidbuildMaxHeap(int[]data,intlastIndex){

//從lastIndex處節(jié)點（最后一個節(jié)點）的父節(jié)點開始

for(inti=(lastIndex-1)/2;i>=0;i--){

//k保存正在判斷的節(jié)點

intk=i;

//如果當(dāng)前k節(jié)點的子節(jié)點存在

while(k*2+1<=lastIndex){

//k節(jié)點的左子節(jié)點的索引

intbiggerIndex=2*k+1;

//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k節(jié)點的右子節(jié)點存在

if(biggerIndex<lastIndex){

//若果右子節(jié)點的值較大

if(data[biggerIndex]<data[biggerIndex+1]){

//biggerIndex總是記錄較大子節(jié)點的索引

biggerIndex++;

}

}

//如果k節(jié)點的值小于其較大的子節(jié)點的值

if(data[k]<data[biggerIndex]){

//交換他們

swap(data,k,biggerIndex);

//將biggerIndex賦予k，開始while循環(huán)的下一次循環(huán)，重新保證k節(jié)點的值大于其左右子節(jié)點的值

k=biggerIndex;

}else{

break;

}

}

}

}

//交換

privatestaticvoidswap(int[]data,inti,intj){

inttmp=data[i];

data[i]=data[j];

data[j]=tmp;

}通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分關(guān)鍵字小，則分別對這兩部分繼續(xù)進行排序，直到整個序列有序。Java實現(xiàn)/**

*快速排序

*

*@paramnumbers

*帶排序數(shù)組

*/

publicstaticvoidquick(int[]numbers){

if(numbers.length>0)//查看數(shù)組是否為空

{

quickSort(numbers,0,numbers.length-1);

}

}

/**

*

*@paramnumbers

*帶排序數(shù)組

*@paramlow

*開始位置

*@paramhigh

*結(jié)束位置

*/

publicstaticvoidquickSort(int[]numbers,intlow,inthigh){

if(low>=high){

return;

}

intmiddle=getMiddle(numbers,low,high);//將numbers數(shù)組進行一分為二

quickSort(numbers,low,middle-1);//對低字段表進行遞歸排序

quickSort(numbers,middle+1,high);//對高字段表進行遞歸排序

}

/**

*查找出中軸（默認是最低位low）的在numbers數(shù)組排序后所在位置

*

*@paramnumbers

*帶查找數(shù)組

*@paramlow

*開始位置

*@paramhigh

*結(jié)束位置

*@return中軸所在位置

*/

publicstaticintgetMiddle(int[]numbers,intlow,inthigh){

inttemp=numbers[low];//數(shù)組的第一個作為中軸

while(low<high){

while(low<high&&numbers[high]>temp){

high--;

}

numbers[low]=numbers[high];//比中軸小的記錄移到低端

while(low<high&&numbers[low]<temp){

low++;

}

numbers[high]=numbers[low];//比中軸大的記錄移到高端

}

numbers[low]=temp;//中軸記錄到尾

returnlow;//返回中軸的位置

}快速排序在序列中元素很少時，效率將比較低，不如插入排序，因此一般在序列中元素很少時使用插入排序，這樣可以提高整體效率。歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。Java實現(xiàn)/**

*歸并排序

*簡介:將兩個（或兩個以上）有序表合并成一個新的有序表即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列

*時間復(fù)雜度為O(nlogn)

*穩(wěn)定排序方式

*@paramnums待排序數(shù)組

*@return輸出有序數(shù)組

*/

publicstaticint[]sort(int[]nums,intlow,inthigh){

intmid=(low+high)/2;

if(low<high){

//左邊

sort(nums,low,mid);

//右邊

sort(nums,mid+1,high);

//左右歸并

merge(nums,low,mid,high);

}

returnnums;

}

/**

*將數(shù)組中l(wèi)ow到high位置的數(shù)進行排序

*@paramnums待排序數(shù)組

*@paramlow待排的開始位置

*@parammid待排中間位置

*@paramhigh待排結(jié)束位置

*/

publicstaticvoidmerge(int[]nums,intlow,intmid,inthigh){

int[]temp=newint[high-low+1];

int