Java實(shí)現(xiàn)基本排序算法的示例代碼
1. 概述
排序概念:就是將一串記錄按照其中某個(gè)或某些關(guān)鍵字的大小,遞增或遞減的排列起來(lái)的操作。
穩(wěn)定性:通俗的將就是數(shù)據(jù)元素不發(fā)生有間隔的交換,例如:
內(nèi)部排序:數(shù)據(jù)元素全部放在內(nèi)存中的排序
外部排序:數(shù)據(jù)元素太多不能一次加載到內(nèi)存中,根據(jù)排序過(guò)程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
注意:以下的排序默認(rèn)排升序。默認(rèn)待排序列為:2,5,1,3,8,6,9,4,7,0,6
2. 插入排序
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中,直到所有的記錄插入完為止,得到一個(gè)新的有序序列
2.1 直接插入排序
1. 思想:
對(duì)于一個(gè)元素,將其與前面元素進(jìn)行比較,將其插入到合適的位置。
排升序:將待排元素依次與序列中元素從右往左比,若待排元素小,則繼續(xù)往前比,找到合適位置插入,原來(lái)元素的位置按順序往后搬移。
2. 畫(huà)圖說(shuō)明:
說(shuō)明:第一個(gè)元素默認(rèn)它有序,所以從第二個(gè)元素開(kāi)始進(jìn)行比較然后插入,5比2大,繼續(xù)下一個(gè),將1依次比較插入2前面,將3依次比較插入5前面,8比5大,不用管,繼續(xù)下一個(gè),將6依次比較插在8面,9比8大,不用管,將7依次比較,插在8前面,將0依次比較插在1前面,將6依次比較插在7前面,插入完成。
3.代碼展示:
public class InsertSort { public static void insertSort(int[] array){ for(int i = 1;i < array.length;i++){ //讓從1下標(biāo)開(kāi)始,因?yàn)槿绻挥幸粋€(gè)元素,它自己默認(rèn)有序 int key = array[i]; //從數(shù)組中的第二個(gè)元素開(kāi)始比較,進(jìn)行插入 int end = i-1; //end的位置是要插入元素的前一個(gè)位置 while(end >= 0 && key < array[end]){ //end不能越界,找待插入的位置,此處注意:key不能小于等于array[end],否則為不穩(wěn)定 array[end+1] = array[end]; end--; } array[end+1] = key; //找到位置進(jìn)行插入,因?yàn)樯厦鎒nd--了,所以這里要插入的位置為end+1 } } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; insertSort(array); for(int i : array){ System.out.print(i+" "); } } }
結(jié)果:
4.特性總結(jié):
時(shí)間復(fù)雜度:循環(huán)嵌套,O(N^2),最優(yōu)情況:當(dāng)序列接近有序,插入的元素比較少,為O(N)
空間復(fù)雜度:不借助輔助空間,O(1)
穩(wěn)定性:數(shù)據(jù)元素不發(fā)生有間隔的交換,穩(wěn)定
應(yīng)用場(chǎng)景:數(shù)據(jù)量小,接近有序
2.2 希爾排序(縮小增量排序)
1. 思想:
選一個(gè)整數(shù)為數(shù)據(jù)元素的間隔,將間隔相同的數(shù)據(jù)元素分為一組,分別對(duì)這些組進(jìn)行插入排序,間隔減小,重復(fù)上述操作,當(dāng)間隔減少到1的時(shí)候,數(shù)據(jù)元素即排好序了。
2. 畫(huà)圖說(shuō)明:
說(shuō)明:gap為間隔,這里依次將gap=4,2,1,先把間隔為4的數(shù)據(jù)元素用插入排序排好序,再利用插入排序排gap=2 的數(shù)據(jù)元素,依次重復(fù)上述操作,即可。
3. 代碼展示:
public class ShellSort { public static void shellSort(int[] array){ int gap = array.length; while(gap > 1){ gap = gap/3+1; for(int i = gap;i < array.length;i++){ //跟插入排序一樣,都從一組數(shù)的第二個(gè)元素開(kāi)始,因?yàn)榈谝粋€(gè)數(shù)默認(rèn)有序 int key = array[i]; int end = i - gap; //end的位置也是代排數(shù)的前一個(gè),但這里間隔為gap,所以前一個(gè)位置為i-gap while(end >= 0 && key < array[end]){ //與插入排序保持不變,找待插入的位置 array[end+gap] = array[end]; // key小于前一個(gè)數(shù),讓end位置的元素往后移一位, end -= gap; //end每次向左走的時(shí)候一次走gap的間隔 } array[end+gap] = key; //找到待排位置將key插入相應(yīng)位置 } } } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; shellSort(array); for(int i : array){ System.out.print(i+" "); } } }
結(jié)果:
4. 特性總結(jié):
希爾排序是對(duì)直接插入排序的優(yōu)化。
當(dāng)gap>1時(shí)都是預(yù)排序,目的是讓數(shù)組元素接近有序,當(dāng)gap==1時(shí),數(shù)組已經(jīng)接近有序了,這樣插入排序?qū)?huì)很快,整體而言,達(dá)到了優(yōu)化的效果。
希爾排序的時(shí)間復(fù)雜度不好計(jì)算,因?yàn)間ap的取值方法很多,導(dǎo)致很難去計(jì)算。
gap的取法有多種,最初shell提出取gap=n/2,gap=gap/2,直到gap=1,后來(lái),Kunth提出取gap = [gap/3]+1。在Kunth所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第3卷中,利用大量的實(shí)驗(yàn)統(tǒng)計(jì)資料得出,當(dāng)n很大時(shí),關(guān)鍵碼的平均比較次數(shù)和對(duì)象平均移動(dòng)次數(shù)大約在n^1.25到1.6n^1.25范圍內(nèi),這是利用直接插入排序作為子序列排序方法的情況下得到的。
故時(shí)間復(fù)雜度暫記為:O(N^1.25)~O(1.6N^1.25)
空間復(fù)雜度:沒(méi)有借助輔助空間,O(1)
穩(wěn)定性:數(shù)據(jù)元素發(fā)生了有間隔的交換,不穩(wěn)定
應(yīng)用場(chǎng)景:數(shù)據(jù)比較隨機(jī)
3. 選擇排序
每一次從待排數(shù)據(jù)元素中選出最?。ㄗ畲螅┑脑兀娣旁谛蛄械钠鹗迹┪玻┪恢?,直到全部待排序的數(shù)據(jù)元素全部排完。
3.1 直接選擇排序
1. 思想:
思路1:
找出序列中的最大的元素,若它不在序列的末尾,將它與末尾元素交換位置,依次循環(huán)。
思路2:
每次找元素的時(shí)候,找一個(gè)最大的和一個(gè)最小的,最大的和最后一個(gè)交換位置,最小的和第一個(gè)交換位置,依次循環(huán)
2. 畫(huà)圖說(shuō)明:
思路1:
說(shuō)明:先找到序列的最大元素與序列最后一個(gè)元素交換,序列的最后的位置朝前移一個(gè),再找新序列的最大元素再與最后一個(gè)交換位置,依次循環(huán)。
思路2:
說(shuō)明:這種方法是一次找兩個(gè)元素,跟上面那種本質(zhì)上一樣,只是一次交換了兩個(gè)元素,將最大的與最后一個(gè)交換,將最小的與第一個(gè)交換
3. 代碼展示:
public class SelectSort { public static void selectSort1(int[] array){ int size = array.length; for(int i = 0;i < size-1;i++){ //選擇的趟數(shù),size-1是因?yàn)楫?dāng)選擇到序列剩一個(gè)元素時(shí)就不用選了 int pos = 0; //pos標(biāo)記最大元素的位置,剛開(kāi)始是默認(rèn)為第一個(gè)位置 for(int j = 1;j < size-i;j++){ //j=1是因?yàn)槟J(rèn)第一個(gè)元素的位置為最大元素的位置,所以從第二個(gè)元素的位置開(kāi)始比較 //size-i是因?yàn)槊刻诉x擇完后,序列都要減少一個(gè) if(array[j] > array[pos]){ pos = j; //找到最大元素位置,更新pos } } if(pos != size-i-1){ //如果最大元素的位置剛好是最后一個(gè)位置,則不需要交換,反之進(jìn)行交換 swap(array,pos,size-i-1); } } } public static void selectSort2(int[] array){ int left = 0; //序列的左邊界 int right = array.length-1; //序列的右邊界 while(left < right){ //當(dāng)序列中至少存在倆元素時(shí) int minPos = left; //剛開(kāi)始將最小元素的位置設(shè)定為序列的第一個(gè)位置 int maxPos = left; //剛開(kāi)始將最大元素的位置也設(shè)定為序列的第一個(gè)位置 int index = left+1; //從序列的第二個(gè)元素開(kāi)始找最大元素和最小元素的位置 //找最大元素和最小元素的位置 while(index <= right){ if(array[index] < array[minPos]){ minPos = index; } if(array[index] > array[maxPos]){ maxPos = index; } index++; } if(minPos != left){ //當(dāng)最小的元素不在序列的最左端時(shí)交換位置 swap(array,minPos,left); } //這里我是先交換最小的元素,但是如果最大的元素在最左側(cè),那么會(huì)將maxPos位置的元素更新為最小的元素,導(dǎo)致后面 //交換最大元素的時(shí)候maxPos標(biāo)記的元素不準(zhǔn)確,所以下面將maxPos的位置更新了一下 //注意:如果是先交換最大的元素,則更新minPos的位置 if(maxPos == left){ maxPos = minPos; } // if(minPos == right){ // minPos = maxPos; // } if(maxPos != right){ //當(dāng)最大元素不在序列的最右端時(shí)交換位置 swap(array,maxPos,right); } left++; //左邊界+1 right--; //右邊界-1 } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {9,5,1,3,8,6,2,4,7,6,0}; selectSort1(array); for(int i : array){ System.out.print(i+" "); } System.out.println(); selectSort2(array); for(int i : array){ System.out.print(i+" "); } } }
4:特性總結(jié):
時(shí)間復(fù)雜度:找元素,交換元素是循環(huán)嵌套,O(N^2)
空間復(fù)雜度:沒(méi)有借助輔助空間,O(1)
穩(wěn)定性:數(shù)據(jù)元素存在有間隔的交換,不穩(wěn)定
缺陷:找最大元素或者最小元素的時(shí)候重復(fù)比較
3.2 堆排序
1. 思想:
堆排序是利用堆積樹(shù)(堆)這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)的一種算法,它是選擇排序的一種,它是通過(guò)堆來(lái)進(jìn)行選擇數(shù)據(jù)。
注意:排升序,建大根堆,排降序,建小根堆。
堆排序分為兩部分:建堆,利用向下調(diào)整建堆,再利用堆刪除的思想排序。
向下調(diào)整:
前提:要調(diào)整的節(jié)點(diǎn)的兩個(gè)左右子樹(shù)都已滿足堆的特性
方法:建大堆,將根的元素與左右孩子較大的元素交換,建小堆,將根的元素與左右孩子較小的元素交換
堆刪除思想:
將堆頂元素與最后一個(gè)元素交換位置
堆中有效元素減少一個(gè)
再對(duì)堆頂元素向下調(diào)整
2. 畫(huà)圖說(shuō)明:
因?yàn)閿?shù)據(jù)元素多,二叉樹(shù)的圖看著不太清晰,所以我用以下序列:0,5,3,4,1,2
建堆:
利用堆刪除思想排序:
3. 代碼展示:
public class HeapSort { //向下調(diào)整 public static void shiftDown(int[] array,int parent,int size){ int child = parent*2+1; //默認(rèn)將左孩子設(shè)為parent的孩子,因?yàn)椴恢烙疫吅⒆邮欠翊嬖? while(child<size){ if(child+1<size && array[child+1]>array[child]){ //如果右孩子存在,比較哪個(gè)孩子值大 child += 1; //將child設(shè)為較大的孩子 } if(array[parent]<array[child]){ //如果parent小,將parent與child交換 swap(array,parent,child); parent = child; //更新parent child = parent*2+1; //更新child }else{ //如果已經(jīng)滿足堆特性則直接返回 return; } } } //堆排序 public static void heapSort(int[] array){ //建堆 int size = array.length; int lastLeaf = ((size-1)-1)/2; //找到倒數(shù)第一個(gè)非葉子節(jié)點(diǎn) for(int root=lastLeaf;root>=0;root--){ //從該結(jié)點(diǎn)開(kāi)始,依次向下調(diào)整直到根節(jié)點(diǎn) shiftDown(array,root,size); } //利用堆刪除思想排序,從最后一個(gè)元素開(kāi)始與堆頂元素交換,然后對(duì)堆頂元素進(jìn)行向下調(diào)整 int end = size-1; while(end>0){ swap(array,0,end); shiftDown(array,0,end); end--; } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; heapSort(array); for(int i : array){ System.out.print(i+" "); } } }
結(jié)果:
4. 特性總結(jié):
時(shí)間復(fù)雜度:n個(gè)元素進(jìn)行比較,而且太向下調(diào)整,調(diào)整的深度為完全二叉樹(shù)的深度,故時(shí)間復(fù)雜度為:O(NlogN),logN是log以2為底的N
空間復(fù)雜度:沒(méi)有借助輔助空間,O(1)
穩(wěn)定性:元素發(fā)生了有間隔的交換,不穩(wěn)定
應(yīng)用場(chǎng)景:求前k個(gè)最小或者最大,可以和其他排序結(jié)合起來(lái)增加效率
4. 交換排序
基本思想就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來(lái)交換這兩個(gè)記錄在序列中的位置,交換排序的特點(diǎn)是:將鍵值較大的記錄向序列的尾部移動(dòng),鍵值較小的記錄向序列的前部移動(dòng)
4.1 冒泡排序
1. 思想:
依次將序列元素進(jìn)行比較,若array[i]>array[i+1],交換兩個(gè)元素的位置,直到最后一個(gè)元素,從中可以得出,每躺冒泡只能確定一個(gè)元素的位置,若序列有n個(gè)元素,則需要進(jìn)行n-1躺冒泡,因?yàn)樾蛄凶詈笠粋€(gè)元素的位置不用確定。
從比較的次數(shù)可以看出:第一躺比較的次數(shù)為n-1,第二躺的比較次數(shù)為n-2.....即每趟冒泡比較的次數(shù)在遞減,即比較次數(shù)是為n-1-i,i為冒泡的趟數(shù)。
2. 畫(huà)圖說(shuō)明:
3. 冒泡排序的優(yōu)化:
從上圖可以看出第10躺冒泡沒(méi)有進(jìn)行,因?yàn)樾蛄幸呀?jīng)有序,即數(shù)據(jù)元素不在發(fā)生交換。
優(yōu)化:在每趟進(jìn)行的開(kāi)始給一個(gè)標(biāo)記isChage=false,如果該躺冒泡發(fā)生了元素交換,將isChange=true,在每趟冒泡完進(jìn)行判斷,如果是Change==false,即沒(méi)有發(fā)生交換,說(shuō)明序列已經(jīng)有序,即不用在繼續(xù)冒泡,直接返回即可。
4. 代碼展示:
public class BubbleSort { public static void bubbleSort(int[] array){ int size = array.length; for(int i = 0;i < size-1;i++){ boolean isChange = false; //為了優(yōu)化冒泡排序給的標(biāo)記,當(dāng)元素不發(fā)生交換的時(shí)候說(shuō)明已經(jīng)有序 for(int j = 0;j < size-1-i;j++){ if(array[j+1] < array[j]){ swap(array,j,j+1); isChange = true; } } if(isChange == false){ //如果元素不發(fā)生交換,直接返回 return; } } } public static void swap(int[] array,int a,int b){ int t = array[a]; array[a] = array[b]; array[b] = t; } public static void main(String[] args) { int[] array = {2,5,1,3,8,6,9,4,7,0,6}; bubbleSort(array); for(int i : array){ System.out.print(i+" "); } } }
結(jié)果:
5. 特性總結(jié):
時(shí)間復(fù)雜度:冒泡的趟數(shù),每趟的比較次數(shù),O(N^2)
空間復(fù)雜度:不借助輔助空間,O(1)
穩(wěn)定性:數(shù)據(jù)元素雖然發(fā)生了交換,但是沒(méi)有間隔交換,穩(wěn)定
4.2 快速排序
4.2.1. 思想
快速排序是Hoare提出的一種二叉樹(shù)結(jié)構(gòu)的交換排序方法。
基本思想為:任取待排元素序列中的某個(gè)元素作為基準(zhǔn)值(這里我們?nèi)∽钣覀?cè)元素為基準(zhǔn)值),按照該基準(zhǔn)值將序列劃分為兩個(gè)區(qū)間,左側(cè)比基準(zhǔn)值小,右側(cè)比基準(zhǔn)值大,再分別用快速排序遞歸排左區(qū)間和右區(qū)間。
參考代碼:
public static void quickSort(int[] array,int left,int right){ //左閉右開(kāi) if(right-left > 1){ //遞歸的返回條件,區(qū)間最少得有兩個(gè)元素 int div = partition(array,left,right); quickSort(array,left,div); //遞歸排左側(cè) quickSort(array,div+1,right); //遞歸排右側(cè) } }
故只要實(shí)現(xiàn)分割方法即可。
4.2.2 三種分割方式
1. Hoare法
思想:在左邊找比基準(zhǔn)值大的,右邊找比基準(zhǔn)值小的,兩個(gè)交換位置,最后將較大一側(cè)的第一個(gè)元素與基準(zhǔn)值交換位置。
畫(huà)圖說(shuō)明:
參考代碼:
//分割區(qū)間方法1:hoare:左邊找比基準(zhǔn)值大的,右邊找比基準(zhǔn)值小的,兩個(gè)交換位置,最后再將基準(zhǔn)值放到中間的位置 public static int partition1(int[] array,int left,int right){ int key = array[right-1]; //找基準(zhǔn)值,以最右側(cè)元素為基準(zhǔn)值 int begin = left; //在左側(cè)找的下標(biāo) int end = right-1; //在右側(cè)找的下標(biāo) while(begin < end){ while(array[begin] <= key && begin < end){ //左側(cè)找大的,不能越界 begin++; } while(array[end] >= key && end > begin){ //右側(cè)找小的,不能越界 end--; } if(begin != end){ swap(array,begin,end); //begin與end不在同一位置的時(shí)候交換,否則沒(méi)有交換的必要 } } if(begin != right-1){ swap(array,begin,right-1); //將基準(zhǔn)值與begin位置的元素交換,begin或者end都行 } return end; //將分割的位置返回,begin與end都可以 }
2. 挖坑法
思想:將基準(zhǔn)值存入key中,基準(zhǔn)值的位置為第一個(gè)坑位,在左側(cè)找比基準(zhǔn)值大的,放到第一個(gè)坑位上,此時(shí)這個(gè)元素的原始位置又形成了一個(gè)新的坑位,再?gòu)挠覀?cè)找比基準(zhǔn)值小的,放到前面的坑位上,依次循環(huán),即將序列分割為兩部分。
畫(huà)圖說(shuō)明:
參考代碼:
//分割區(qū)間方法二:挖坑法:基準(zhǔn)值是一個(gè)坑位,左側(cè)找大的放到基準(zhǔn)值的坑位上,此時(shí)形成了新的坑位,再在右側(cè)找小的放到上一個(gè)坑位,依次循環(huán) public static int partition2(int[] array,int left,int right){ int key = array[right-1]; //取最右側(cè)元素為基準(zhǔn)值,end的位置形成了第一個(gè)坑位 int begin = left; int end = right-1; while(begin < end){ while(begin < end && key >= array[begin]){ //在左側(cè)找比基準(zhǔn)值大的 begin++; } if(begin < end){ array[end] = array[begin]; //填end坑位,重新生成begin坑位 } while(begin < end && key <= array[end]){ //在右側(cè)找比基準(zhǔn)值小的 end--; } if(begin < end){ array[begin] = array[end]; //填begin坑位,重新生成end坑位 } } array[begin] = key; //將基準(zhǔn)值填充在最后一個(gè)坑位 return end; }
3. 前后標(biāo)記法
思想:給兩個(gè)標(biāo)記cur,pre,pre標(biāo)記cur的前一個(gè),cur開(kāi)始標(biāo)記第一個(gè)元素,依次往后走,cur小于區(qū)間的右邊界,如果cur小于基準(zhǔn)值并且++pre不等于cur交換cur與pre位置的元素,最后交換++pre與基準(zhǔn)值位置的元素。
畫(huà)圖說(shuō)明:
參考代碼:
//分割區(qū)間方法三:前后標(biāo)記法 public static int partition3(int[] array,int left,int right){ int key = array[right-1]; int cur = left; int pre = cur-1; while(cur < right){ if(array[cur] < key && ++pre != cur){ //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre!=cur的時(shí)候,交換 swap(array,cur,pre); } cur++; } if(++pre != right-1){ //++pre為與基準(zhǔn)值交換的位置,所以當(dāng)++pre!=right-1的時(shí)候,交換基準(zhǔn)值的位置 swap(array,pre,right-1); } return pre; }
4.2.3 快速排序的優(yōu)化
快速排序的優(yōu)化:對(duì)基準(zhǔn)值的選取進(jìn)行優(yōu)化,這樣做是為了選取的基準(zhǔn)值盡可能的將區(qū)間的左右側(cè)分的均勻一點(diǎn)兒。
優(yōu)化方法:三數(shù)取中法取基準(zhǔn)值,三數(shù):區(qū)間的中間元素,最左側(cè)元素,最右側(cè)元素,取它們?nèi)齻€(gè)的中間值。
參考代碼:
//快排優(yōu)化:三數(shù)取中法來(lái)取基準(zhǔn)值,左側(cè),右側(cè),中間這三個(gè)數(shù)的中間值來(lái)作為基準(zhǔn)值,這里返回的是基準(zhǔn)值下標(biāo) public static int getIndexOfMid(int[] array,int left,int right){ int mid = left+((right-left)>>1); if(array[left] < array[right-1]){ //最右側(cè)的下標(biāo)為right-1 if(array[mid] < array[left]){ return left; }else if(array[mid] > array[right-1]){ return right-1; }else{ return mid; } }else{ if(array[mid] < array[right-1]){ return right-1; }else if(array[mid] > array[left]){ return left; }else{ return mid; } } }
具體與之前代碼結(jié)合方式,我這里選取一種分割方法來(lái)進(jìn)行優(yōu)化:
參考代碼:
//分割區(qū)間方法三:前后標(biāo)記法 public static int partition3(int[] array,int left,int right){ int index = getIndexOfMid(array,left,right); //用三數(shù)取中法獲得基準(zhǔn)值的下標(biāo) if(index != right-1){ swap(array,index,right-1); //如果下表不在最右側(cè)就交換 } int key = array[right-1]; int cur = left; int pre = cur-1; while(cur < right){ if(array[cur] < key && ++pre != cur){ //當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre!=cur的時(shí)候,交換 swap(array,cur,pre); } cur++; } if(++pre != right-1){ //++pre為與基準(zhǔn)值交換的位置,所以當(dāng)++pre!=right-1的時(shí)候,交換基準(zhǔn)值的位置 swap(array,pre,right-1); } return pre; }
4.2.4 快速排序的非遞歸方式
非遞歸的快速排序借助棧這一數(shù)據(jù)結(jié)構(gòu)
參考代碼:
//非遞歸的快速排序,利用棧來(lái)保存分割的區(qū)間,傳參只需要傳數(shù)組即可 public static void quickSort(int[] array){ Stack<Integer> s = new Stack<>(); s.push(array.length); s.push(0); while(!s.empty()){ int left = s.pop(); int right = s.pop(); if(right - left == 0){ continue; } int div = partition(array,left,right); s.push(right); s.push(div+1); s.push(div); s.push(left); } }
4.2.5 快速排序的特性總結(jié)
時(shí)間復(fù)雜度:有比較,遞歸,O(NlogN)
空間復(fù)雜度:存在遞歸,遞歸的深度為完全二叉樹(shù)的深度,O(logN)
穩(wěn)定性:數(shù)據(jù)元素發(fā)生有間隔的交換,不穩(wěn)定
應(yīng)用場(chǎng)景:數(shù)據(jù)凌亂且隨機(jī)
5. 歸并排序
1. 思想:
歸并排序是將兩個(gè)有序序列進(jìn)行合并,但是我們拿到是一個(gè)數(shù)組,所以得先將數(shù)組遞歸均分為兩部分,再將兩部分進(jìn)行合并。
2. 畫(huà)圖說(shuō)明:
遞歸均分:
從下往上合并:
3. 代碼展示:
public class MergeSort { public static void mergeSort(int[] array,int left,int right,int[] temp){ if(right - left > 1){ int mid = left+((right-left)>>1); mergeSort(array,left,mid,temp); //遞歸均分左側(cè) mergeSort(array,mid,right,temp); //遞歸均分右側(cè) mergeData(array,left,mid,right,temp); //合并兩個(gè)序列,[left,mid) , [mid,right) System.arraycopy(temp,left,array,left,right-left); //拷貝到原數(shù)組,源,起始位置,新,起始位置,長(zhǎng)度 } } public static void mergeData(int[] array,int left,int mid,int right,int[] temp){ //[begin1,end1),[begin2,end2),為兩個(gè)合并的區(qū)間 int begin1 = left; int end1 = mid; int begin2 = mid; int end2 = right; int index = left; //輔助數(shù)組的下標(biāo) while(begin1 < end1 && begin2 < end2){ if(array[begin1] <= array[begin2]){ temp[index++] = array[begin1++]; }else{ temp[index++] = array[begin2++]; } } while(begin1 < end1){ temp[index++] = array[begin1++]; } while(begin2 < end2){ temp[index++] = array[begin2++]; } } //重新包裝一下,便于用戶傳參 public static void mergeSort(int[] array){ int[] temp = new int[array.length]; mergeSort(array,0,array.length,temp); } }
4. 非遞歸的歸并排序
給一個(gè)間隔,用間隔來(lái)表示區(qū)間
參考代碼:
//非遞歸的歸并排序 public static void mergeSortNor(int[] array){ int size = array.length; int[] temp = new int[size]; int gap = 1; //先每?jī)蓚€(gè)元素歸并 while(gap < size){ for(int i = 0;i < size;i+=gap*2){ int left = i; int mid = i+gap; int right = mid+gap; if(mid > size){ //防止mid越界 mid = size; } if(right > size){ //防止right越界 right = size; } mergeData(array,left,mid,right,temp); } System.arraycopy(temp,0,array,0,size); gap <<= 1; } }
5. 特性總結(jié):
時(shí)間復(fù)雜度:O(NlogN)
空間復(fù)雜度:借助了輔助空間,為輔助數(shù)組的大小,O(N)
穩(wěn)定性:數(shù)據(jù)元素不發(fā)生有間隔的交換,穩(wěn)定
應(yīng)用場(chǎng)景:適合外部排序
6. 計(jì)數(shù)排序(非比較類型的排序)
1. 思想:
計(jì)數(shù)排序又稱鴿巢原理,是對(duì)哈希直接定址法的變形應(yīng)用
步驟:
統(tǒng)計(jì)相同元素出現(xiàn)次數(shù)
根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來(lái)的序列中
2. 畫(huà)圖說(shuō)明:
3. 代碼展示:
public class CountSort { public static void countSort(int[] array){ //找出數(shù)組的最大值與最小值 int maxNum = array[0]; int minNum = array[0]; for(int i = 1;i < array.length;i++){ if(array[i] > maxNum){ maxNum = array[i]; } if(array[i] < minNum){ minNum = array[i]; } } int range = maxNum - minNum + 1; //序列元素的范圍大小 int[] count = new int[range]; //new一個(gè)范圍大小的數(shù)組 for(int i = 0;i < array.length;i++){ count[array[i]-minNum]++; //讀取 } int index = 0; //存入原數(shù)組的下標(biāo) for(int i = 0;i < range;i++){ while(count[i] > 0){ array[index] = i + minNum; index++; count[i]--; } } } }
4. 性能總結(jié):
時(shí)間復(fù)雜度:O(N)
空間復(fù)雜度:O(M),M為數(shù)據(jù)范圍的大小
穩(wěn)定性:數(shù)據(jù)元素沒(méi)有進(jìn)行有間隔的交換,穩(wěn)定
應(yīng)用場(chǎng)景:數(shù)據(jù)元素集中在某個(gè)范圍
7. 排序算法總結(jié)
排序方法 | 最好 | 平均 | 最壞 | 空間復(fù)雜度 | 穩(wěn)定性 |
插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩(wěn)定 |
選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩(wěn)定 |
堆排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(1) | 不穩(wěn)定 |
冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩(wěn)定 |
快速排序 | O(n*log(n)) | O(n*log(n)) | O(n^2) | O(log(n)) | 不穩(wěn)定 |
歸并排序 | O(n*log(n)) | O(n*log(n)) | O(n*log(n)) | O(n) | 穩(wěn)定 |
以上就是Java實(shí)現(xiàn)基本排序算法的示例代碼的詳細(xì)內(nèi)容,更多關(guān)于Java排序算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
相關(guān)文章
Springboot啟動(dòng)報(bào)錯(cuò)時(shí)實(shí)現(xiàn)異常定位
這篇文章主要介紹了Springboot啟動(dòng)報(bào)錯(cuò)時(shí)實(shí)現(xiàn)異常定位,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06java 字符串相減(很簡(jiǎn)單的一個(gè)方法)
本篇文章是對(duì)java中關(guān)于字符串相減的一個(gè)簡(jiǎn)單的方法進(jìn)行了介紹,需要的朋友參考下2013-07-07MyBatis實(shí)現(xiàn)動(dòng)態(tài)SQL更新的代碼示例
本文博小編將帶領(lǐng)大家學(xué)習(xí)如何利用 MyBatis 攔截器機(jī)制來(lái)優(yōu)雅的實(shí)現(xiàn)這個(gè)需求,文中通過(guò)代碼示例介紹的非常詳細(xì),具有一定的參考價(jià)值,需要的朋友可以參考下2023-07-07Java關(guān)鍵字詳解之final static this super的用法
this用來(lái)調(diào)用目前類自身的成員變量,super多用來(lái)調(diào)用父類的成員,final多用來(lái)定義常量用的,static定義靜態(tài)變量方法用的,靜態(tài)變量方法只能被類本身調(diào)用,下文將詳細(xì)介紹,需要的朋友可以參考下2021-10-10RateLimit-使用guava來(lái)做接口限流代碼示例
這篇文章主要介紹了RateLimit-使用guava來(lái)做接口限流代碼示例,具有一定借鑒價(jià)值,需要的朋友可以參考下2018-01-01教你怎么用java實(shí)現(xiàn)客戶端與服務(wù)器一問(wèn)一答
這篇文章主要介紹了教你怎么用java實(shí)現(xiàn)客戶端與服務(wù)器一問(wèn)一答,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下2021-04-04