Java常用的7大排序算法

本文格式為Word版，下載可任意編輯——Java常用的7大排序算法Java常用的7大排序算法

Java是一門面向對象編程語言，以下總結了下java中常用的七大排序算法，夢想對大家有扶助！

1.插入排序算法

插入排序的根本思想是在遍歷數組的過程中，假設在序號i之前的元素即[0..i-1]都已經排好序，本趟需要找到i對應的元素x的正確位置k，并且在探索這個位置k的過程中逐個將對比過的元素往后移一位，為元素x“騰位置”，結果將k對應的元素值賦為x，一般處境下，插入排序的時間繁雜度和空間繁雜度分別為On2和O1。

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortInsertint[]array

forinti=1;iarray.length;i++

inttemp=array[i];

intj;

forj=i-1;j=0temparray[j];j--

array[j+1]=array[j];

array[j+1]=temp;

returnarray;

2.選擇排序算法

選擇排序的根本思想是遍歷數組的過程中，以i代表當前需要排序的序號，那么需要在剩余的[i…n-1]中找出其中的最小值，然后將找到的最小值與i指向的值舉行交換。由于每一趟確定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間繁雜度和空間繁雜度分別為On2和O1。

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortSelectint[]arr

forinti=0;iarr.length;i++

intminiPost=i;

forintm=i+1;marr.length;m++

ifarr[m]arr[miniPost]

miniPost=m;

ifarr[i]arr[miniPost]

inttemp;

temp=arr[i];

arr[i]=arr[miniPost];

arr[miniPost]=temp;

returnarr;

3.冒泡排序算法

冒泡排序是將比較大的數字沉在最下面，較小的浮在上面

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortBubbleint[]array

inttemp;

//第一層循環(huán):說明對比的次數,譬如length個元素,對比次數為length-1次（斷定不需和自己比）

forinti=0;iarray.length-1;i++

forintj=array.length-1;ji;j--

ifarray[j]array[j-1]

temp=array[j];

array[j]=array[j-1];

array[j-1]=temp;

returnarray;

4.快速排序算法

通過一趟排序將待排記錄分割成獨立的兩片面,其中一片面記錄的關鍵字均比另一片面的關鍵字小,那么可以分別對這兩片面記錄持續(xù)舉行排序,已達成整個序列有序的目的，本質就是,找一個基位樞軸,分水嶺,作用是左邊的都比它小,右邊的都比它大。

可隨機,取名base，首先從序列最右邊開頭找比base小的.,假設小,換位置,從而base移到方才右邊對比時比base小的位置記為臨時的high位,這樣base右邊的都比base大。然后,從序列的最左邊開頭找比base大的，假設大,換位置,從而base移動到方才左邊對比時比base大的位置記為臨時的low位,這樣base左邊的都比base小，循環(huán)以上兩步,直到low==heigh,這使才真正的找到了樞軸,分水嶺.返回這個位置,分水嶺左邊和右邊的序列,分別再來遞歸。

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortQuickint[]array

returnquickSortarray,0,array.length-1;

privateint[]quickSortint[]arr,intlow,intheigh

iflowheigh

intpision=partitionarr,low,heigh;

quickSortarr,low,pision-1;

quickSortarr,pision+1,heigh;

returnarr;

//分水嶺,基位,左邊的都比這個位置小,右邊的都大

privateintpartitionint[]arr,intlow,intheigh

intbase=arr[low];//用子表的第一個記錄做樞軸分水嶺記錄

whilelowheigh//從表的兩端交替向中間掃描

whilelowheigharr[heigh]=base

heigh--;

//base賦值給當前heigh位,base挪到互換到了這里,heigh位右邊的都比base大

swaparr,heigh,low;

whilelowheigharr[low]=base

low++;

//遇到左邊比base值大的了,換位置

swaparr,heigh,low;

//nowlow=heigh;

returnlow;

privatevoidswapint[]arr,inta,intb

inttemp;

temp=arr[a];

arr[a]=arr[b];

arr[b]=temp;

5.合并排序算法

歸并排序采用的是遞歸來實現，屬于“分而治之”，將目標數組從中間一分為二，之后分別對這兩個數組舉行排序，排序完畢之后再將排好序的兩個數組“歸并”到一起，歸并排序最重要的也就是這個“歸并”的過程，歸并的過程中需要額外的跟需要歸并的兩個數組長度一致的空間

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

privateint[]sortint[]nums,intlow,inthigh

intmid=low+high/2;

iflowhigh

//左邊

sortnums,low,mid;

//右邊

sortnums,mid+1,high;

//左右歸并

mergenums,low,mid,high;

returnnums;

privatevoidmergeint[]nums,intlow,intmid,inthigh

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

inti=low;//左指針

intj=mid+1;//右指針

intk=0;

//把較小的數先移到新數組中

whilei=midj=high

ifnums[i]nums[j]

temp[k++]=nums[i++];

else

temp[k++]=nums[j++];

//把左邊剩余的數移入數組

whilei=mid

temp[k++]=nums[i++];

//把右邊邊剩余的數移入數組

whilej=high

temp[k++]=nums[j++];

//把新數組中的數籠罩nums數組

forintk2=0;k2temp.length;k2++

nums[k2+low]=temp[k2];

publicint[]sortMergeint[]array

returnsortarray,0,array.length-1;

6.希爾排序算法

希爾排序的誕生是由于插入排序在處理大規(guī)模數組的時候會遇到需要移動太多元素的問題。希爾排序的思想是將一個大的數組“分而治之”，劃分為若干個小的數組。

以gap來劃分，譬如數組[1,2,3,4,5,6,7,8]，假設以gap=2來劃分，可以分為[1,3,5,7]和[2,4,6,8]兩個數組（對應的，如gap=3，那么劃分的數組為：[1,4,7]、[2,5,8]、[3,6]）然后分別對劃分出來的數組舉行插入排序，待各個子數組排序完畢之后再減小gap值重復舉行之前的步驟，直至gap=1，即對整個數組舉行插入排序。

此時的數組已經根本上快排好序了，所以需要移動的元素會很小很小，解決了插入排序在處理大規(guī)模數組時較多移動次數的問題，希爾排序是插入排序的提升版，在數據量大的時候對效率的提升扶助很大，數據量小的時候建議直接使用插入排序就好了。

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortShellint[]array

//取增量

intstep=array.length/2;

whilestep=1

forinti=step;iarray.length;i++

inttemp=array[i];

intj=0;

//跟插入排序的識別就在這里

forj=i-step;j=0temparray[j];j-=step

array[j+step]=array[j];

array[j+step]=temp;

step/=2;

returnarray;

7.堆排序算法

本質就是先構造一個大頂堆,parent比children大,root節(jié)點就是最大的節(jié)點把最大的節(jié)點root與尾節(jié)點結果一個節(jié)點,對比小位置互換，剩下結果的尾節(jié)點,現在最大,其余的,從第一個元素開頭到尾節(jié)點前一位,構造大頂堆遞歸。

/**

*@paramint[]未排序數組

*@returnint[]排完序數組

*/

publicint[]sortHeapint[]array

buildHeaparray;//構建堆

intn=array.length;

inti=0;

fori=n-1;i=1;i--

swaparray,0,i;

heapifyarray,0,i;

returnarray;

privatevoidbuildHeapint[]array

intn=array.length;//數組中元素的個數

forinti=n/2-1;i=0;i--

heapifyarray,i,n;

privatevoidheapifyint[]A,intidx,intmax

intleft=2*idx+1;//左孩子的下標（假設存在的話）

intright=2*idx+2;//左孩子的下標（假設存在的話）

intlargest=0;//探索3個節(jié)點中最大值節(jié)點的下標

ifleftmaxA[left]A[idx]

largest=left;

else

largest=idx;

ifrightmaxA[right]A[largest]

largest=right;

iflarges