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

java 排序算法之選擇排序

 更新時間:2021年09月01日 15:47:10   投稿:lan00zi  
本文主要講解了java 排序算法之選擇排序,選擇排序是最簡單直觀的一種算法,想要了解相關(guān)知識的朋友快來看一看這篇文章吧

基本介紹

選擇排序(select sorting)也屬于內(nèi)部排序法,是從欲排序的數(shù)據(jù)中,按指定的規(guī)則選出來某個元素,再依規(guī)定交換位置后達到排序的目的。

它的工作原理:首先在未排序序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?,然后,再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?,然后放到已排序序列的末尾。以此類推,直到所有元素均排序完畢。

基本思想

選擇排序(select sorting)也是一種簡單直觀的排序方法。

基本思想為:

注:n 是數(shù)組大小

  • 第一次從 arr[0]~arr[n-1] 中選取最小值,與 arr[0] 交換
  • 第二次從 arr[1]~arr[n-1] 中選取最小值,與 arr[1] 交換
  • 第 i 次從 arr[i-1]~arr[n-1] 中選取最小值,與 arr[i-1] 交換
  • 依次類推,總共通過 n - 1 次,得到一個按排序碼從小到大排列的有序序列

思路分析

動圖:

說明:

1.選擇排序一共有數(shù)組大小 - 1 輪排序

2.每 1 輪排序,又是一個循環(huán),循環(huán)的規(guī)則

①先假定當前這輪循環(huán)的第一個數(shù)是最小數(shù)

②然后和后面每個數(shù)進行比較,如果發(fā)現(xiàn)有比當前數(shù)更小的數(shù),則重新確定最小數(shù),并得到下標

③當遍歷到數(shù)組的最后時,就得到本輪最小的數(shù)

④和當前循環(huán)的第一個數(shù)進行交換

代碼實現(xiàn)

要求:假設(shè)有一群牛,顏值分別是 101,34,119,1 ,請使用選中排序從低到高進行排序

演變過程

使用逐步推導(dǎo)的方式,進行講解排序,容易理解。

推導(dǎo)每一步的演變過程,便于理解。

​ 這是一個很重要的思想:
​ 一個算法:先簡單 --> 做復(fù)雜:
​ 就是可以把一個復(fù)雜的算法,拆分成簡單的問題 -> 逐步解決

    @Test
    public void processDemo() {
        int arr[] = {101, 34, 119, 1};
        System.out.println("原始數(shù)組:" + Arrays.toString(arr));
        processSelectSort(arr);
    }

    public void processSelectSort(int[] arr) {
        // 第 1 輪:
        // 原始數(shù)組:101, 34, 119, 1
        // 排序后:  1, 34, 119, 101
        int min = arr[0]; // 先假定第一個數(shù)為最小值
        int minIndex = 0;
        for (int j = 0 + 1; j < arr.length; j++) {
            // 挨個與最小值對比,如果小于,則進行交換
            if (min > arr[j]) {
                // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 1 輪結(jié)束后,得到了最小值
        // 將這個最小值與 arr[0] 交換
        arr[minIndex] = arr[0];
        arr[0] = min;
        System.out.println("第 1 輪排序后:" + Arrays.toString(arr));

        // 第 2 輪
        // 當前數(shù)組:1, 34, 119, 101
        // 排序后:  1, 34, 119, 101
        min = arr[1];
        minIndex = 1;
        // 第二輪,與第 3 個數(shù)開始比起
        for (int j = 0 + 2; j < arr.length; j++) {
            // 挨個與最小值對比,如果小于,則進行交換
            if (min > arr[j]) {
                // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 2 輪結(jié)束后,得到了最小值
        // 將這個最小值與 arr[1] 交換
        arr[minIndex] = arr[1];
        arr[1] = min;
        System.out.println("第 2 輪排序后:" + Arrays.toString(arr));

        // 第 3 輪
        // 當前數(shù)組:1, 34, 119, 101
        // 排序后:  1, 34, 101, 119
        min = arr[2];
        minIndex = 2;
        // 第二輪,與第 4 個數(shù)開始比起
        for (int j = 0 + 3; j < arr.length; j++) {
            // 挨個與最小值對比,如果小于,則進行交換
            if (min > arr[j]) {
                // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                min = arr[j];
                minIndex = j;
            }
        }
        // 第 3 輪結(jié)束后,得到了最小值
        // 將這個最小值與 arr[2] 交換
        arr[minIndex] = arr[2];
        arr[2] = min;
        System.out.println("第 3 輪排序后:" + Arrays.toString(arr));
    }

測試輸出

原始數(shù)組:[101, 34, 119, 1]
第 1 輪排序后:[1, 34, 119, 101]
第 2 輪排序后:[1, 34, 119, 101]
第 3 輪排序后:[1, 34, 101, 119]

從上述的演變過程來看,發(fā)現(xiàn)了規(guī)律:循環(huán)體都是相同的,只是每一輪排序所假定的最小值的下標在遞增。因此可以改寫成如下方式

	  @Test
    public void processDemo2() {
        int arr[] = {101, 34, 119, 1};
        System.out.println("原始數(shù)組:" + Arrays.toString(arr));
        processSelectSort2(arr);
    }

    public void processSelectSort2(int[] arr) {
        // 把之前假定當前最小值的地方,使用變量 i 代替了
        // 由于需要 arr.length -1 輪,所以使用外層一個循環(huán),就完美的解決了這個需求
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i]; // 先假定第一個數(shù)為最小值
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 挨個與最小值對比,如果小于,則進行交換
                if (min > arr[j]) {
                    // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 第 i 輪結(jié)束后,得到了最小值
            // 將這個最小值與 arr[i] 交換
            arr[minIndex] = arr[i];
            arr[i] = min;
            System.out.println("第 " + (i + 1) + " 輪排序后:" + Arrays.toString(arr));
        }
    }

測試輸出

原始數(shù)組:[101, 34, 119, 1]
第 1 輪排序后:[1, 34, 119, 101]
第 2 輪排序后:[1, 34, 119, 101]
第 3 輪排序后:[1, 34, 101, 119]

由此可以得到,選擇排序的時間復(fù)雜度是 o(n²),因為是一個嵌套 for 循環(huán)

結(jié)果是一樣的,但是你會發(fā)現(xiàn),在第 1 輪和第 2 輪的序列是一樣的,但是代碼中目前也進行了交換,可以優(yōu)化掉這一個點

優(yōu)化

    public void processSelectSort2(int[] arr) {
        // 把之前假定當前最小值的地方,使用變量 i 代替了
        // 由于需要 arr.length -1 輪,所以使用外層一個循環(huán),就完美的解決了這個需求
        for (int i = 0; i < arr.length - 1; i++) {
            int min = arr[i]; // 先假定第一個數(shù)為最小值
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                // 挨個與最小值對比,如果小于,則進行交換
                if (min > arr[j]) {
                    // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                    min = arr[j];
                    minIndex = j;
                }
            }
            // 第 i 輪結(jié)束后,得到了最小值
            // 將這個最小值與 arr[i] 交換
            //但如果minIndex沒有改變,也就是最小值未發(fā)生改變,則不需要執(zhí)行后面的交換了
            if (minIndex != i) {
                arr[minIndex] = arr[i];
            	arr[i] = min;
            }
            System.out.println("第 " + (i + 1) + " 輪排序后:" + Arrays.toString(arr));
        }
    }

測試輸出

原始數(shù)組:[101, 34, 119, 1]
第 1 輪排序后:[1, 34, 119, 101]
第 3 輪排序后:[1, 34, 101, 119]

則可以看到,第二輪就跳過了交換這一個步驟,從而優(yōu)化了這個算法所要花費的時間。

算法函數(shù)封裝

@Test
public void selectSortTest() {
    int arr[] = {101, 34, 119, 1};
    System.out.println("升序");
    System.out.println("原始數(shù)組:" + Arrays.toString(arr));
    selectSort(arr, true);
    System.out.println("排序后:" + Arrays.toString(arr));
    System.out.println("降序");
    System.out.println("原始數(shù)組:" + Arrays.toString(arr));
    selectSort(arr, false);
    System.out.println("排序后:" + Arrays.toString(arr));
}

/**
 * 選擇排序算法封裝
 *
 * @param arr 要排序的數(shù)組
 * @param asc 升序排列,否則降序
 */
public void selectSort(int[] arr, boolean asc) {

    // 把之前假定當前最小值的地方,使用變量 i 代替了
    // 由于需要 arr.length -1 輪,所以使用外層一個循環(huán),就完美的解決了這個需求
    for (int i = 0; i < arr.length - 1; i++) {
        int current = arr[i]; // 先假定第一個數(shù)為最小值
        int currentIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
            // 挨個與最小值對比,如果小于,則進行交換
            if (asc) {
                if (current > arr[j]) {
                    // 如果后面的值比當前的 min 小,則重置min為這個數(shù)
                    current = arr[j];
                    currentIndex = j;
                }
            } else {
                if (current < arr[j]) {
                    // 如果后面的值比當前的 min 大,則重置為這個數(shù)
                    current = arr[j];
                    currentIndex = j;
                }
            }
        }
        // 第 i 輪結(jié)束后,得到了最小/大值
        // 將這個值與 arr[i] 交換
        //但如果minIndex沒有改變,也就是最小值未發(fā)生改變,則不需要執(zhí)行后面的交換了
        if (currentIndex == i) {
            arr[currentIndex] = arr[i];
        	arr[i] = current;
        }
    }
}

測試輸出

升序
原始數(shù)組:[101, 34, 119, 1]
排序后:[1, 34, 101, 119]
降序
原始數(shù)組:[1, 34, 101, 119]
排序后:[119, 101, 34, 1]

大量數(shù)據(jù)耗時測試

排序隨機生成的 8 萬個數(shù)據(jù)

 @Test
    public void bulkDataSort() {
        int max = 80_000;
        int[] arr = new int[max];
        for (int i = 0; i < max; i++) {
            arr[i] = (int) (Math.random() * 80_000);
        }

        Instant startTime = Instant.now();
        selectSort(arr, true);
//        System.out.println(Arrays.toString(arr));
        Instant endTime = Instant.now();
        System.out.println("共耗時:" + Duration.between(startTime, endTime).toMillis() + " 毫秒");
    }

多次運行測試輸出

共耗時:2983 毫秒
共耗時:3022 毫秒

冒泡排序和選擇排序的時間復(fù)雜度雖然都是 o(n²),但由于冒泡排序每一步有變化都要交換位置,導(dǎo)致了消耗了大量的時間,所以選擇排序相對冒泡排序所花費的時間要更少。

關(guān)于冒泡排序請看java 排序算法之冒泡排序

到此這篇關(guān)于java 排序算法之選擇排序的文章就介紹到這了,更多相關(guān)java 選擇排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • springboot項目整合注冊功能模塊開發(fā)實戰(zhàn)

    springboot項目整合注冊功能模塊開發(fā)實戰(zhàn)

    這篇文章主要介紹了springboot項目整合注冊功能模塊開發(fā)實戰(zhàn),在用戶的注冊是首先需要查詢當前的用戶名是否存在,如果存在則不能進行注冊,相當于一個查詢語句,本文通過實例代碼詳細講解,需要的朋友可以參考下
    2022-11-11
  • java中全排列的生成算法匯總

    java中全排列的生成算法匯總

    本文給大家匯總介紹了常見的6種全排列的生成算法,包括字典序法、遞增進位數(shù)制法、遞減進位數(shù)制法、鄰位交換法、遞歸類算法、元素增值法,有需要的小伙伴可以參考下
    2015-07-07
  • 一篇文章帶你了解JAVA結(jié)構(gòu)化編程詳情

    一篇文章帶你了解JAVA結(jié)構(gòu)化編程詳情

    下面小編就為大家?guī)硪黄v解JAVA結(jié)構(gòu)化編程的文章。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2021-09-09
  • 基于java中stack與heap的區(qū)別,java中的垃圾回收機制的相關(guān)介紹

    基于java中stack與heap的區(qū)別,java中的垃圾回收機制的相關(guān)介紹

    本篇文章小編將為大家介紹,基于java中stack與heap的區(qū)別,java中的垃圾回收機制的相關(guān)介紹,需要的可以參考一下
    2013-04-04
  • Spring的Xml和JavaConfig 擴展哪個好用

    Spring的Xml和JavaConfig 擴展哪個好用

    今天給大家介紹基于注解的Spring擴展,Spring的Xml和JavaConfig 擴展的配置方法,關(guān)于Spring的Xml和JavaConfig 擴展你會選哪個呢,帶著這個問題一起通過本文學(xué)習(xí)下吧
    2021-05-05
  • ReentrantReadWriteLock不能鎖升級的原因總結(jié)

    ReentrantReadWriteLock不能鎖升級的原因總結(jié)

    今天給大家?guī)淼氖顷P(guān)于Java并發(fā)的相關(guān)知識,文章圍繞著為什么ReentrantReadWriteLock不能鎖升級展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下
    2021-06-06
  • 詳解WebSocket+spring示例demo(已使用sockJs庫)

    詳解WebSocket+spring示例demo(已使用sockJs庫)

    本篇文章主要介紹了WebSocket spring示例demo(已使用sockJs庫),小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2017-01-01
  • springboot默認文件緩存(easy-captcha?驗證碼)

    springboot默認文件緩存(easy-captcha?驗證碼)

    這篇文章主要介紹了springboot的文件緩存(easy-captcha?驗證碼),本文通過實例代碼給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-06-06
  • RabbitMQ 的消息持久化與 Spring AMQP 的實現(xiàn)詳解

    RabbitMQ 的消息持久化與 Spring AMQP 的實現(xiàn)詳解

    這篇文章主要介紹了RabbitMQ 的消息持久化與 Spring AMQP 的實現(xiàn)剖析詳解,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2019-08-08
  • 使用Java獲取系統(tǒng)信息的常用代碼整理總結(jié)

    使用Java獲取系統(tǒng)信息的常用代碼整理總結(jié)

    這篇文章主要介紹了使用Java獲取系統(tǒng)信息的常用代碼整理總結(jié),在服務(wù)器端一般經(jīng)常能夠用到,歡迎收藏,需要的朋友可以參考下
    2015-11-11

最新評論