" />

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

Java數(shù)據(jù)結(jié)構(gòu)和算法之冒泡,選擇和插入排序算法

 更新時(shí)間:2022年01月20日 14:35:48   作者:YSOcean  
這篇文章主要為大家介紹了Java冒泡,選擇和插入排序算法 ,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助

1、冒泡排序

這個(gè)名詞的由來(lái)很好理解,一般河水中的冒泡,水底剛冒出來(lái)的時(shí)候是比較小的,隨著慢慢向水面浮起會(huì)逐漸增大,這物理規(guī)律我不作過(guò)多解釋,大家只需要了解即可。

冒泡算法的運(yùn)作規(guī)律如下:

①、比較相鄰的元素。如果第一個(gè)比第二個(gè)大,就交換他們兩個(gè)。

②、對(duì)每一對(duì)相鄰元素作同樣的工作,從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后,最后的元素會(huì)是最大的數(shù)(也就是第一波冒泡完成)。

③、針對(duì)所有的元素重復(fù)以上的步驟,除了最后一個(gè)。

④、持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對(duì)數(shù)字需要比較。

  

  

代碼如下:

package com.ys.sort;
public class BubbleSort {
    public static int[] sort(int[] array){
        //這里for循環(huán)表示總共需要比較多少輪
        for(int i = 1 ; i < array.length; i++){
            //設(shè)定一個(gè)標(biāo)記,若為true,則表示此次循環(huán)沒(méi)有進(jìn)行交換,也就是待排序列已經(jīng)有序,排序已經(jīng)完成。
            boolean flag = true;
            //這里for循環(huán)表示每輪比較參與的元素下標(biāo)
            //對(duì)當(dāng)前無(wú)序區(qū)間array[0......length-i]進(jìn)行排序
            //j的范圍很關(guān)鍵,這個(gè)范圍是在逐步縮小的,因?yàn)槊枯啽容^都會(huì)將最大的放在右邊
            for(int j = 0 ; j < array.length-i ; j++){
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    flag = false;
                }
            }
            if(flag){
                break;
            }
            //第 i輪排序的結(jié)果為
            System.out.print("第"+i+"輪排序后的結(jié)果為:");
            display(array);
        }
        return array;
    }
    //遍歷顯示數(shù)組
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {4,2,8,9,5,7,6,1,3};
        //未排序數(shù)組順序?yàn)?
        System.out.println("未排序數(shù)組順序?yàn)椋?);
        display(array);
        System.out.println("-----------------------");
        array = sort(array);
        System.out.println("-----------------------");
        System.out.println("經(jīng)過(guò)冒泡排序后的數(shù)組順序?yàn)椋?);
        display(array);
    }
}

結(jié)果如下:

  

本來(lái)應(yīng)該是 8 輪排序的,這里我們只進(jìn)行了 7 輪排序,因?yàn)榈?7 輪排序之后已經(jīng)是有序數(shù)組了。

冒泡排序解釋:

冒泡排序是由兩個(gè)for循環(huán)構(gòu)成,第一個(gè)for循環(huán)的變量 i 表示總共需要多少輪比較,第二個(gè)for循環(huán)的變量 j 表示每輪參與比較的元素下標(biāo)【0,1,......,length-i】,因?yàn)槊枯啽容^都會(huì)出現(xiàn)一個(gè)最大值放在最右邊,所以每輪比較后的元素個(gè)數(shù)都會(huì)少一個(gè),這也是為什么 j 的范圍是逐漸減小的。相信大家理解之后快速寫出一個(gè)冒泡排序并不難。

冒泡排序性能分析:

假設(shè)參與比較的數(shù)組元素個(gè)數(shù)為 N,則第一輪排序有 N-1 次比較,第二輪有 N-2 次,如此類推,這種序列的求和公式為:

 ?。∟-1)+(N-2)+...+1 = N*(N-1)/2

當(dāng) N 的值很大時(shí),算法比較次數(shù)約為 N2/2次比較,忽略減1。

假設(shè)數(shù)據(jù)是隨機(jī)的,那么每次比較可能要交換位置,可能不會(huì)交換,假設(shè)概率為50%,那么交換次數(shù)為N2/4。不過(guò)如果是最壞的情況,初始數(shù)據(jù)是逆序的,那么每次比較都要交換位置。

交換和比較次數(shù)都和N2 成正比。由于常數(shù)不算大 O 表示法中,忽略 2 和 4,那么冒泡排序運(yùn)行都需要 O(N2) 時(shí)間級(jí)別。

其實(shí)無(wú)論何時(shí),只要看見(jiàn)一個(gè)循環(huán)嵌套在另一個(gè)循環(huán)中,我們都可以懷疑這個(gè)算法的運(yùn)行時(shí)間為 O(N2)級(jí),外層循環(huán)執(zhí)行 N 次,內(nèi)層循環(huán)對(duì)每一次外層循環(huán)都執(zhí)行N次(或者幾分之N次)。這就意味著大約需要執(zhí)行N2次某個(gè)基本操作?! ?/p>

2、選擇排序

選擇排序是每一次從待排序的數(shù)據(jù)元素中選出最小的一個(gè)元素,存放在序列的起始位置,直到全部待排序的數(shù)據(jù)元素排完。

分為三步:

  • ①、從待排序序列中,找到關(guān)鍵字最小的元素
  • ②、如果最小元素不是待排序序列的第一個(gè)元素,將其和第一個(gè)元素互換
  • ③、從余下的 N - 1 個(gè)元素中,找出關(guān)鍵字最小的元素,重復(fù)(1)、(2)步,直到排序結(jié)束

  

  

代碼如下:

package com.ys.sort;
public class ChoiceSort {
    public static int[] sort(int[] array){
        //總共要經(jīng)過(guò)N-1輪比較
        for(int i = 0 ; i < array.length-1 ; i++){
            int min = i;
            //每輪需要比較的次數(shù)
            for(int j = i+1 ; j < array.length ; j++){
                if(array[j]<array[min]){
                    min = j;//記錄目前能找到的最小值元素的下標(biāo)
                }
            }
            //將找到的最小值和i位置所在的值進(jìn)行交換
            if(i != min){
                int temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }
            //第 i輪排序的結(jié)果為
            System.out.print("第"+(i+1)+"輪排序后的結(jié)果為:");
            display(array);
        }
        return array;
    }
    //遍歷顯示數(shù)組
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args){
        int[] array = {4,2,8,9,5,7,6,1,3};
        //未排序數(shù)組順序?yàn)?
        System.out.println("未排序數(shù)組順序?yàn)椋?);
        display(array);
        System.out.println("-----------------------");
        array = sort(array);
        System.out.println("-----------------------");
        System.out.println("經(jīng)過(guò)選擇排序后的數(shù)組順序?yàn)椋?);
        display(array);
    }
}

運(yùn)行結(jié)果:  

選擇排序性能分析:

選擇排序和冒泡排序執(zhí)行了相同次數(shù)的比較:N*(N-1)/2,但是至多只進(jìn)行了N次交換。

當(dāng) N 值很大時(shí),比較次數(shù)是主要的,所以和冒泡排序一樣,用大O表示是O(N2) 時(shí)間級(jí)別。但是由于選擇排序交換的次數(shù)少,所以選擇排序無(wú)疑是比冒泡排序快的。當(dāng) N 值較小時(shí),如果交換時(shí)間比選擇時(shí)間大的多,那么選擇排序是相當(dāng)快的。

3、插入排序

直接插入排序基本思想是每一步將一個(gè)待排序的記錄,插入到前面已經(jīng)排好序的有序序列中去,直到插完所有元素為止。

插入排序還分為直接插入排序、二分插入排序、鏈表插入排序、希爾排序等等,這里我們只是以直接插入排序講解,后面講高級(jí)排序的時(shí)候會(huì)將其他的。

  

代碼如下:

package com.ys.sort;
public class InsertSort {
    public static int[] sort(int[] array){
        int j;
        //從下標(biāo)為1的元素開(kāi)始選擇合適的位置插入,因?yàn)橄聵?biāo)為0的只有一個(gè)元素,默認(rèn)是有序的
        for(int i = 1 ; i < array.length ; i++){
            int tmp = array[i];//記錄要插入的數(shù)據(jù)
            j = i;
            while(j > 0 && tmp < array[j-1]){//從已經(jīng)排序的序列最右邊的開(kāi)始比較,找到比其小的數(shù)
                array[j] = array[j-1];//向后挪動(dòng)
                j--;
            }
            array[j] = tmp;//存在比其小的數(shù),插入
        }
        return array;
    }
    //遍歷顯示數(shù)組
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[] args){
        int[] array = {4,2,8,9,5,7,6,1,3};
        //未排序數(shù)組順序?yàn)?
        System.out.println("未排序數(shù)組順序?yàn)椋?);
        display(array);
        System.out.println("-----------------------");
        array = sort(array);
        System.out.println("-----------------------");
        System.out.println("經(jīng)過(guò)插入排序后的數(shù)組順序?yàn)椋?);
        display(array);
    }
}

運(yùn)行結(jié)果:  

插入排序性能分析:

在第一輪排序中,它最多比較一次,第二輪最多比較兩次,一次類推,第N輪,最多比較N-1次。因此有1+2+3+...+N-1 =N*(N-1)/2。

假設(shè)在每一輪排序發(fā)現(xiàn)插入點(diǎn)時(shí),平均只有全體數(shù)據(jù)項(xiàng)的一半真的進(jìn)行了比較,我們除以2得到:N*(N-1)/4。用大O表示法大致需要需要 O(N2) 時(shí)間級(jí)別。

復(fù)制的次數(shù)大致等于比較的次數(shù),但是一次復(fù)制與一次交換的時(shí)間耗時(shí)不同,所以相對(duì)于隨機(jī)數(shù)據(jù),插入排序比冒泡快一倍,比選擇排序略快。

這里需要注意的是,如果要進(jìn)行逆序排列,那么每次比較和移動(dòng)都會(huì)進(jìn)行,這時(shí)候并不會(huì)比冒泡排序快。

4、總結(jié)

上面講的三種排序,冒泡、選擇、插入用大 O 表示法都需要O(N2) 時(shí)間級(jí)別。一般不會(huì)選擇冒泡排序,雖然冒泡排序書寫是最簡(jiǎn)單的,但是平均性能是沒(méi)有選擇排序和插入排序好的。

選擇排序把交換次數(shù)降低到最低,但是比較次數(shù)還是挺大的。當(dāng)數(shù)據(jù)量小,并且交換數(shù)據(jù)相對(duì)于比較數(shù)據(jù)更加耗時(shí)的情況下,可以應(yīng)用選擇排序。

在大多數(shù)情況下,假設(shè)數(shù)據(jù)量比較小或基本有序時(shí),插入排序是三種算法中最好的選擇。

后面我們會(huì)講解高級(jí)排序,大O表示法的時(shí)間級(jí)別將比O(N2)小?!?/p>

本篇文章就到這里了,希望能夠給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • Java構(gòu)建高效結(jié)果緩存方法示例

    Java構(gòu)建高效結(jié)果緩存方法示例

    這篇文章主要介紹了Java構(gòu)建高效結(jié)果緩存方法示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-04-04
  • IDEA啟動(dòng)Springboot報(bào)錯(cuò):無(wú)效的目標(biāo)發(fā)行版:17 的解決辦法

    IDEA啟動(dòng)Springboot報(bào)錯(cuò):無(wú)效的目標(biāo)發(fā)行版:17 的解決辦法

    這篇文章主要給大家介紹了IDEA啟動(dòng)Springboot報(bào)錯(cuò):無(wú)效的目標(biāo)發(fā)行版:17 的解決辦法,文中通過(guò)代碼示例和圖文講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下
    2024-02-02
  • Springboot工具類ReflectionUtils使用教程

    Springboot工具類ReflectionUtils使用教程

    這篇文章主要介紹了Springboot內(nèi)置的工具類之ReflectionUtils的使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)吧
    2022-12-12
  • Java超詳細(xì)精講數(shù)據(jù)結(jié)構(gòu)之bfs與雙端隊(duì)列

    Java超詳細(xì)精講數(shù)據(jù)結(jié)構(gòu)之bfs與雙端隊(duì)列

    廣搜BFS的基本思想是: 首先訪問(wèn)初始點(diǎn)v并將其標(biāo)志為已經(jīng)訪問(wèn)。接著通過(guò)鄰接關(guān)系將鄰接點(diǎn)入隊(duì)。然后每訪問(wèn)過(guò)一個(gè)頂點(diǎn)則出隊(duì)。按照順序,訪問(wèn)每一個(gè)頂點(diǎn)的所有未被訪問(wèn)過(guò)的頂點(diǎn)直到所有的頂點(diǎn)均被訪問(wèn)過(guò)。廣度優(yōu)先遍歷類似與層次遍歷
    2022-07-07
  • SpringBoot整合mybatis-plus實(shí)現(xiàn)分頁(yè)查詢功能

    SpringBoot整合mybatis-plus實(shí)現(xiàn)分頁(yè)查詢功能

    這篇文章主要介紹了SpringBoot整合mybatis-plus實(shí)現(xiàn)分頁(yè)查詢功能,pringBoot分頁(yè)查詢的兩種寫法,一種是手動(dòng)實(shí)現(xiàn),另一種是使用框架實(shí)現(xiàn),現(xiàn)在我將具體的實(shí)現(xiàn)流程分享一下,需要的朋友可以參考下
    2023-11-11
  • springboot 配置日志 打印不出來(lái)sql的解決方法

    springboot 配置日志 打印不出來(lái)sql的解決方法

    這篇文章主要介紹了springboot 配置日志 打印不出來(lái)sql的解決方法,幫助大家更好的理解和使用springboot框架,感興趣的朋友可以了解下
    2020-11-11
  • Java?SpringBoot?@Async實(shí)現(xiàn)異步任務(wù)的流程分析

    Java?SpringBoot?@Async實(shí)現(xiàn)異步任務(wù)的流程分析

    這篇文章主要介紹了Java?SpringBoot?@Async實(shí)現(xiàn)異步任務(wù),主要包括@Async?異步任務(wù)-無(wú)返回值,@Async?異步任務(wù)-有返回值,@Async?+?自定義線程池的操作代碼,需要的朋友可以參考下
    2022-12-12
  • Springboot?內(nèi)部服務(wù)調(diào)用方式

    Springboot?內(nèi)部服務(wù)調(diào)用方式

    這篇文章主要介紹了Springboot?內(nèi)部服務(wù)調(diào)用方式,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-03-03
  • ZooKeeper開(kāi)發(fā)實(shí)際應(yīng)用案例實(shí)戰(zhàn)

    ZooKeeper開(kāi)發(fā)實(shí)際應(yīng)用案例實(shí)戰(zhàn)

    這篇文章主要為大家介紹了ZooKeeper開(kāi)發(fā)的實(shí)際應(yīng)用案例實(shí)戰(zhàn),文中附含詳細(xì)開(kāi)發(fā)應(yīng)用源碼,有需要的朋友可以借鑒參考下,希望能夠有所幫助
    2022-01-01
  • springboot通過(guò)jar包啟動(dòng)中文日志亂碼問(wèn)題及解決

    springboot通過(guò)jar包啟動(dòng)中文日志亂碼問(wèn)題及解決

    這篇文章主要介紹了springboot通過(guò)jar包啟動(dòng)中文日志亂碼問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-06-06

最新評(píng)論