欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java實(shí)現(xiàn)基本排序算法的示例代碼

 更新時(shí)間:2022年07月13日 14:54:58   作者:XH學(xué)Java  
排序就是將一串記錄按照其中某個(gè)或某些關(guān)鍵字的大小,遞增或遞減的排列起來(lái)的操作。本文將用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)異常定位

    這篇文章主要介紹了Springboot啟動(dòng)報(bào)錯(cuò)時(shí)實(shí)現(xiàn)異常定位,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-06-06
  • java 中Buffer源碼的分析

    java 中Buffer源碼的分析

    這篇文章主要介紹了java 中Buffer源碼的分析的相關(guān)資料,需要的朋友可以參考下
    2017-06-06
  • java 字符串相減(很簡(jiǎn)單的一個(gè)方法)

    java 字符串相減(很簡(jiǎn)單的一個(gè)方法)

    本篇文章是對(duì)java中關(guān)于字符串相減的一個(gè)簡(jiǎn)單的方法進(jìn)行了介紹,需要的朋友參考下
    2013-07-07
  • java中的connection reset 異常處理分析

    java中的connection reset 異常處理分析

    本文主要介紹了java中的connection reset 異常處理分析的相關(guān)資料,具有很好的參考價(jià)值。下面跟著小編一起來(lái)看下吧
    2017-04-04
  • 使用Java實(shí)現(xiàn)文件夾的遍歷操作指南

    使用Java實(shí)現(xiàn)文件夾的遍歷操作指南

    網(wǎng)上大多采用java遞歸的方式遍歷文件夾下的文件,這里我不太喜歡遞歸的風(fēng)格,這篇文章主要給大家介紹了關(guān)于使用Java實(shí)現(xiàn)文件夾的遍歷操作的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2023-05-05
  • Spring使用@responseBody與序列化詳解

    Spring使用@responseBody與序列化詳解

    這篇文章主要介紹了Spring使用@responseBody與序列化詳解,@responseBody注解的作用是將controller的方法返回的對(duì)象通過(guò)適當(dāng)?shù)霓D(zhuǎn)換器轉(zhuǎn)換為指定的格式之后,寫(xiě)入到response對(duì)象的body區(qū),通常用來(lái)返回JSON數(shù)據(jù)或者是XML數(shù)據(jù),需要的朋友可以參考下
    2023-08-08
  • MyBatis實(shí)現(xiàn)動(dòng)態(tài)SQL更新的代碼示例

    MyBatis實(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-07
  • Java關(guān)鍵字詳解之final static this super的用法

    Java關(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-10
  • RateLimit-使用guava來(lái)做接口限流代碼示例

    RateLimit-使用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)一答

    這篇文章主要介紹了教你怎么用java實(shí)現(xiàn)客戶端與服務(wù)器一問(wèn)一答,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有非常好的幫助,需要的朋友可以參考下
    2021-04-04

最新評(píng)論