Java超詳細(xì)整理講解各種排序
穩(wěn)定性
兩個(gè)相等的數(shù)據(jù),如果經(jīng)過(guò)排序后,排序算法能保證其相對(duì)位置不發(fā)生變化,則我們稱該算法是具備穩(wěn)定性的排序算法。
直接插入排序
直接插入排序就是每次選擇無(wú)序區(qū)間的第一個(gè)元素,在有序區(qū)間內(nèi)選擇合適的位置插入。
從數(shù)組下標(biāo)為1開(kāi)始,將下標(biāo)為1上的值取出來(lái)放在tmp中,然后它和前面的下標(biāo)j上的值進(jìn)行比較,如果前面下標(biāo)j上的值比它大,則前面下標(biāo)j上的值往后走一步,直到比到j(luò)回退到了-1或者j下標(biāo)上的值比tmp小為止,然后把tmp插入到下標(biāo)為[j+1]的位置上。然后i就繼續(xù)往后走,繼續(xù)比較,直到i走到數(shù)組的最后。
代碼示例:
/** *直接插入排序 *時(shí)間復(fù)雜度 O(N^2) *空間復(fù)雜度 O(1) *穩(wěn)定性 :穩(wěn)定(看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換,如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序) * 一個(gè)穩(wěn)定的排序,可以實(shí)現(xiàn)為不穩(wěn)定的排序 * 但是一個(gè)本身就不穩(wěn)定的排序,是不可以變成穩(wěn)定的排序的 * 經(jīng)常使用在數(shù)據(jù)量不多且整體數(shù)據(jù)趨于有序了 */ public static void insertSort(int[] array) { for(int i=1;i<array.length;i++) { int tmp = array[i]; int j = 0; for (j = i - 1; j >= 0; j--) { if (tmp < array[j]) { array[j + 1] = array[j]; } else { break; } } array[j + 1] = tmp; } }
希爾排序
希爾排序是對(duì)直接插入排序的優(yōu)化。將數(shù)據(jù)進(jìn)行相應(yīng)的分組,分為gap組,然后按照直接插入排序的方法排序。 當(dāng)gap > 1時(shí)都是預(yù)排序,目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí),數(shù)組已經(jīng)接近有序的了,這樣就會(huì)很快。這樣整體而言,可以達(dá)到優(yōu)化的效果。
/** * 時(shí)間復(fù)雜度(和增量有關(guān)系的):O(n^1.3 - n^1.5) * 空間復(fù)雜度:O(1) * 穩(wěn)定性:不穩(wěn)定的 * 看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換,如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序 */ public static void shellSort(int[] array) { int gap=array.length-1; while(gap>1){ shell(array,gap); gap/=2; } shell(array,1);//保證最后是1組 } public static void shell(int[] array,int gap) { for(int i=gap;i< array.length;i++){ int tmp=array[i]; int j=i-gap; for (j = i-gap; j >=0; j=j-gap) { if(tmp<array[j]){ array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } }
選擇排序
每一次從無(wú)序區(qū)間選出最大(或最小)的一個(gè)元素,存放在無(wú)序區(qū)間的最后(或最前),直到全部待排序的數(shù)據(jù)元素排完 。
代碼示例:
/** *選擇排序 *空間復(fù)雜度:O(N^2) * 時(shí)間復(fù)雜度:O(1) * 穩(wěn)定性:不穩(wěn)定 * 看在比較的過(guò)程當(dāng)中是否發(fā)生了跳躍式的交換,如果發(fā)生了跳躍式的交換那么就是不穩(wěn)定的排序 */ public static void selectSort(int[] array){ for(int i=0;i<array.length;i++){ for(int j=i+1;j< array.length;j++){ if(array[j]<array[i]){ swap(array,i,j); } } } } public static void swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; } //選擇排序還可以找到最小值下標(biāo)再交換 public static void selectSort1(int[] array) { for (int i = 0; i < array.length; i++) { int minIndex = i; for (int j = i+1; j < array.length; j++) { //找到最小值下標(biāo) if(array[j] < array[minIndex]) { minIndex = j; } } swap(array,i,minIndex); }
堆排序
基本原理也是選擇排序,只是不在使用遍歷的方式查找無(wú)序區(qū)間的最大的數(shù),而是通過(guò)堆來(lái)選擇無(wú)序區(qū)間的最大的數(shù)。
注意: 排升序要建大堆;排降序要建小堆。 (在堆那里有提過(guò))
代碼示例:
/** * 堆排序 * 時(shí)間復(fù)雜度:O(N*log2^N) * 空間復(fù)雜度:O(1) * 穩(wěn)定性:不穩(wěn)定 */ public static void heapSort(int[] array){ creatHeap(array);//先創(chuàng)建堆 int end=array.length-1; //交換后調(diào)整(N*log2^N) while(end>0){ swap(array,0,end); shiftDown(array,0,end); end--; } } //建堆 public static void creatHeap(int[] array){ for(int parent=(array.length-1-1)/2;parent>=0;parent--){ shiftDown(array,parent,array.length); } } //調(diào)整 public static void shiftDown(int[] array,int parent,int len){ int child=2*parent+1;//左孩子下標(biāo) while(child<len){ //左右孩子比較 if(child+1<len && array[child]<array[child+1]){ child++; } if(array[child]>array[parent]){ swap(array,child,parent); parent=child; child=parent*2-1; }else{ break; } } }
冒泡排序
在無(wú)序區(qū)間,通過(guò)相鄰數(shù)的比較,將最大的數(shù)冒泡到無(wú)序區(qū)間的最后,持續(xù)這個(gè)過(guò)程,直到數(shù)組整體有序。
代碼示例:
/** * 冒泡排序 * 時(shí)間復(fù)雜度:O(N^2) * 空間復(fù)雜度:O(1) * 穩(wěn)定性:穩(wěn)定 * i為需要排的次數(shù) * j為每次需要比較的開(kāi)始到結(jié)束位置 */ public static void bubbleSort(int[] array){ for (int i = 0; i < array.length-1; i++) { for (int j = 0; j < array.length-1-i; j++) { if(array[j+1]<array[j]){ swap(array,j,j+1); } } } } public static void swap(int[] array,int i,int j){ int tmp=array[i]; array[i]=array[j]; array[j]=tmp; }
快速排序
1、 從待排序區(qū)間選擇一個(gè)數(shù),作為基準(zhǔn)值 (pivot) ;
2、 partition: 遍歷整個(gè)待排序區(qū)間,將比基準(zhǔn)值小的(可以包含相等的)放到基準(zhǔn)值的左邊,將比基準(zhǔn)值大的(可以包含相等的)放到基準(zhǔn)值的右邊;
3、 采用分治思想,對(duì)左右兩個(gè)小區(qū)間按照同樣的方式處理,直到小區(qū)間的長(zhǎng)度 == 1 ,代表已經(jīng)有序,或者小區(qū)間的長(zhǎng)度 == 0 ,代表沒(méi)有數(shù)據(jù)。 代碼示例:
/** * 時(shí)間復(fù)雜度: * 最好(每次可以均勻的分割待排序序列):O(N*log2^n)log以2為底的N次方 * 最壞:數(shù)據(jù)有序或者逆序的情況 O(N^2) * 空間復(fù)雜度: * 最好:O(log2^n) * 最壞:O(n) 單分支的一棵樹(shù) * 穩(wěn)定性:不穩(wěn)定的排序 */ //遞歸方式實(shí)現(xiàn) public static void quickSort(int[] array){ quick(array,0,array.length-1); } public static void quick(int[] array,int left,int right){ if(left>=right){ return; } //找基準(zhǔn)值,然后基準(zhǔn)值左邊右邊分別按同樣的方式處理 int pivot=partition(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); } //找基準(zhǔn)點(diǎn)(兩邊開(kāi)始找) public static int partition(int[] array,int start,int end){ int tmp=array[start]; while(start<end){ while(start<end && array[end]>=tmp){ end--; } array[start]=array[end]; while(start<end && array[start]<=tmp){ start++; } array[end]=array[start]; } array[start]=tmp;//start==end時(shí),找到了基準(zhǔn)點(diǎn) return end; }
上面代碼還有待優(yōu)化,如果我們是一個(gè)有序數(shù)組,我們?cè)谡一鶞?zhǔn)值進(jìn)行相應(yīng)處理的時(shí)候可能會(huì)出現(xiàn)單分支情況,這時(shí)候我們可以讓start下標(biāo)的值為中間值,這樣可以避免出現(xiàn)單分支情況。
代碼示例:
public static void quickSort(int[] array){ quick(array,0,array.length-1); } public static void quick(int[] array,int left,int right){ if(left>=right){ return; } //優(yōu)化--找基準(zhǔn)前,先找到中間值,三數(shù)取中法(防止有序情況下出現(xiàn)單分支) int minValIndex=findValINdex(array,left,right); swap(array,minValIndex,left); int pivot=partition(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); } //三數(shù)取中 private static int findValINdex(int[] array,int start,int end){ int mid=start+((end-start)>>>1); //(start+end)/2 if(array[start]<array[end]){ if(array[mid]>array[end]){ return end; } else if (array[mid]<array[start]) { return start; }else{ return mid; } }else{ if(array[mid]>array[start]) { return start; }else if(array[mid]<array[end]){ return end; }else{ return mid; } } }
當(dāng)排序數(shù)據(jù)過(guò)多時(shí)還能繼續(xù)優(yōu)化,如果區(qū)間內(nèi)的數(shù)據(jù),在排序的過(guò)程當(dāng)中,小于某個(gè)范圍了,可以使用直接插入排序。
代碼示例:
public static void quickSort(int[] array){ quick(array,0,array.length-1); } //遞歸,找到了基準(zhǔn)點(diǎn),分別再對(duì)基準(zhǔn)點(diǎn)左邊和基準(zhǔn)點(diǎn)右邊找 public static void quick(int[] array,int left,int right){ if(left>=right){ return; } //優(yōu)化--如果區(qū)間內(nèi)的數(shù)據(jù),在排序的過(guò)程當(dāng)中,小于某個(gè)范圍了,可以使用直接插入排序 if(right-left+1<150){ insertSort1(array,left,right); return; } //優(yōu)化--找基準(zhǔn)前,先找到中間值,三數(shù)取中法(防止有序情況下出現(xiàn)單分支) int minValIndex=findValINdex(array,left,right); swap(array,minValIndex,left); int pivot=partition(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); } private static void insertSort1(int[] array,int start,int end){ for (int i = 1; i <= end; i++) { int tmp=array[i]; int j=i-1; for(j=i-1;j>=start;j--){ if(array[j]>tmp){ array[j+1]=array[j]; }else{ //array[j+1]=tmp; break; } } array[j+1]=tmp; } }
非遞歸實(shí)現(xiàn):
public static void quickSort1(int[] array){ int left=0; int right=array.length-1; Stack<Integer> stack=new Stack<>(); int pivot=partition(array,left,right); //如果左邊或者右邊只剩下一個(gè)數(shù)據(jù)了,那就已經(jīng)有序了,不需要在排序 if(left+1<pivot){ //左邊至少有兩個(gè)元素 stack.push(left); stack.push(pivot-1); } if(right-1>pivot){ //右邊至少有兩個(gè)元素 stack.push(right); stack.push(pivot+1); } while(!stack.isEmpty()){ left=stack.pop(); right=stack.pop(); pivot=partition(array,left,right); if(left+1<pivot){ //左邊至少有兩個(gè)元素 stack.push(left); stack.push(pivot-1); } if(right-1>pivot){ //右邊至少有兩個(gè)元素 stack.push(right); stack.push(pivot+1); } } }
歸并排序
歸并排序 是建立在歸并操作上的一種有效的排序算法 , 將已有序的子序列合并,得到完全有序的序列。即先使每個(gè)子序列有序,再使子 序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,稱為二路歸并。
代碼示例:
/** * 歸并排序--遞歸 * 時(shí)間復(fù)雜度:O(N*log2^N) * 空間復(fù)雜度:O(N) * 穩(wěn)定性:穩(wěn)定 * 學(xué)過(guò)的排序:穩(wěn)定的只有三個(gè) * 冒泡 插入 歸并 */ //遞歸方式實(shí)現(xiàn) public static void mergeSort(int[] array){ mergeSortInternal(array,0,array.length-1); } public static void mergeSortInternal(int[] array,int left,int right){ if(left>=right){ return; } int mid=left+((right-left)>>>1); //mid=(left+right)/2; //左邊 mergeSortInternal(array,left,mid); //右邊 mergeSortInternal(array,mid+1,right); //合并 merge(array,left,mid,right); } public static void merge(int[] array,int start,int mid,int end) { int s1 = start; int e1 = mid; int s2 = mid+1; int e2 = end; int i = 0; int[] tmp = new int[array.length]; while (s1 <= e1 && s2 <= e2) { if (array[s1] <=array[s2]) { tmp[i] = array[s1]; //tmp[i++]=array1[s1++]; i++; s1++; } else { tmp[i] = array[s2]; i++; s2++; } } while(s1<=e1){ tmp[i++]=array[s1++]; } while(s2<=e2){ tmp[i++]=array[s2++]; } for (int j = 0; j < i; j++) { array[j+start]=tmp[j]; } }
非遞歸方式--分組歸并(先tmp個(gè)元素有序然后在合并)
//tmp:代表組內(nèi)元素個(gè)數(shù) public static void mergeSort1(int[] array){ int tmp=1; while(tmp<array.length-1){ //數(shù)組每次都要進(jìn)行遍歷,確定要?dú)w并的區(qū)間 for (int i = 0; i < array.length; i+=tmp*2) { int left=i; int mid=left+tmp-1; //防止越界 if(mid>=array.length){ mid=array.length-1; } int right=mid+tmp; //防止越界 if(right>=array.length){ right=array.length-1; } //下標(biāo)確定之后進(jìn)行合并 merge(array,left,mid,right); } tmp=tmp*2; } }
計(jì)數(shù)排序
以上排序都是通過(guò)比較的排序,接下來(lái)介紹一種不需要比較的排序--計(jì)數(shù)排序。
代碼示例:
/** * 計(jì)數(shù)排序: * 時(shí)間復(fù)雜度:O(N) * 空間復(fù)雜度:O(M) M:代表當(dāng)前數(shù)據(jù)的范圍 * 穩(wěn)定性:當(dāng)前代碼是不穩(wěn)定的,但是本質(zhì)是穩(wěn)定的 * 一般適用于有n個(gè)數(shù),數(shù)據(jù)范圍是0-n之間的 */ public static void countingSort(int[] array) { int minVal=array[0]; int maxVal=array[0]; for(int i=0;i<array.length;i++){ if(array[i]<minVal){ minVal=array[i]; } if(array[i]>maxVal){ maxVal=array[i]; } } int[] count=new int[maxVal-minVal+1];//下標(biāo)默認(rèn)從0開(kāi)始 for (int i=0;i<array.length;i++){ //統(tǒng)計(jì)array數(shù)組當(dāng)中,每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù) int index=array[i]; //為了空間的合理使用 這里需要index-minVal 防止623-600 count[index-minVal]++; } //說(shuō)明,在計(jì)數(shù)數(shù)組當(dāng)中,已經(jīng)把a(bǔ)rray數(shù)組當(dāng)中,每個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)已經(jīng)統(tǒng)計(jì)好了 //接下來(lái),只需要,遍歷計(jì)數(shù)數(shù)組,把數(shù)據(jù)寫(xiě)回array int indexArray=0; for(int i=0;i<count.length;i++){ while (count[i]>0){ array[indexArray]=i+minVal; count[i]--; indexArray++; } } }
到此這篇關(guān)于Java超詳細(xì)整理講解各種排序的文章就介紹到這了,更多相關(guān)Java排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
Java畢業(yè)設(shè)計(jì)實(shí)戰(zhàn)之食品溯源系統(tǒng)的實(shí)現(xiàn)
這是一個(gè)使用了java+Springboot+Maven+mybatis+Vue+mysql+wd開(kāi)發(fā)的食品溯源系統(tǒng),是一個(gè)畢業(yè)設(shè)計(jì)的實(shí)戰(zhàn)練習(xí),具有食品溯源該有的所有功能,感興趣的朋友快來(lái)看看吧2022-01-01JAVA中的函數(shù)式接口Function和BiFunction詳解
這篇文章主要介紹了JAVA中的函數(shù)式接口Function和BiFunction詳解,JDK的函數(shù)式接口都加上了@FunctionalInterface注解進(jìn)行標(biāo)識(shí),但是無(wú)論是否加上該注解只要接口中只有一個(gè)抽象方法,都是函數(shù)式接口,需要的朋友可以參考下2024-01-01Java之next()、nextLine()區(qū)別及問(wèn)題解決
這篇文章主要介紹了Java之next()、nextLine()區(qū)別及問(wèn)題解決,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08Java 多線程并發(fā)AbstractQueuedSynchronizer詳情
這篇文章主要介紹了Java 多線程并發(fā)AbstractQueuedSynchronizer詳情,文章圍繞主題展開(kāi)想象的內(nèi)容介紹,具有一定的參考價(jià)值,感興趣的小伙伴可以參考一下2022-06-06Springmvc如何實(shí)現(xiàn)向前臺(tái)傳遞數(shù)據(jù)
這篇文章主要介紹了Springmvc如何實(shí)現(xiàn)向前臺(tái)傳遞數(shù)據(jù),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07