成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

簡單選擇排序

tylin / 2852人閱讀

摘要：因?yàn)槊恳惶舜_定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間復(fù)雜度和空間復(fù)雜度分別為和。

概述

在要排序的一組數(shù)中，選出最小的一個數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。

換句話說：

以 i 代表當(dāng)前需要排序的序號，則需要在剩余的 [i... n-1] 中找出其中的最小值，然后將找到的最小值與 i 指向的值進(jìn)行交換。因?yàn)槊恳惶舜_定元素的過程中都會有一個選擇最大值的子流程，所以人們形象地稱之為選擇排序。選擇排序的時間復(fù)雜度和空間復(fù)雜度分別為 O(n2) 和 O(1) 。

直觀釋義圖：

步驟

從n 個記錄中找出關(guān)鍵碼最小的記錄與第一個記錄交換

從第2 個記錄開始的 n-1 個記錄中再選出最小的記錄與第2 個記錄交換

從第i (i是不斷+1的)個記錄開始的 n-i+1 個記錄中選出最小的與第i 個記錄交換

直到整個序列有序

實(shí)例

原始數(shù)據(jù)：

3 5 2 6 2

第一輪，找出 [5 2 6 2] 中最小的第三個位置 2 ，與第一個位置 3 進(jìn)行交換

2 5 3 6 2

第二輪，找出 [3 6 2] 中最小的 2 與第一輪中第二個位置 5 進(jìn)行交換

2 2 3 6 5

第三輪，找出 [6 5] 中最小的 5 與第二輪中第三個位置 3 不需交換

2 2 3 6 5

第四輪，找出 [5] 中最小的 5 與第三輪中的第四個位置 6 進(jìn)行交換

2 2 3 5 6

第五輪，沒有了，最終結(jié)果

2 2 3 5 6

簡單選擇排序也可以認(rèn)為是穩(wěn)定的排序。

代碼實(shí)現(xiàn)(Java) 
package com.coder4j.main.arithmetic.sorting;
    
public class SimpleSelection {

    /**
     * 簡單選擇排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.println("第" + (i + 1) + "輪比較結(jié)果：");
            int minPosition = i;
            // 找出i之后的數(shù)組中的最小索引
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minPosition]) {
                    minPosition = j;
                }
            }
            // 判斷是否需要調(diào)換位置
            if (array[i] > array[minPosition]) {
                int temp = array[i];
                array[i] = array[minPosition];
                array[minPosition] = temp;
            }
            // 輸出此輪排序結(jié)果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結(jié)果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }
}

測試輸出結(jié)果：

第1輪比較結(jié)果：
2 5 3 6 2 
第2輪比較結(jié)果：
2 2 3 6 5 
第3輪比較結(jié)果：
2 2 3 6 5 
第4輪比較結(jié)果：
2 2 3 5 6 
第5輪比較結(jié)果：
2 2 3 5 6 
最終結(jié)果
2 2 3 5 6

經(jīng)測試，與實(shí)例中結(jié)果一致。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65415.html

相關(guān)文章

  • 選擇排序就這么簡單

    摘要：選擇排序就這么簡單從上一篇已經(jīng)講解了冒泡排序了，本章主要講解的是選擇排序，希望大家看完能夠理解并手寫出選擇排序的代碼，然后就通過面試了如果我寫得有錯誤的地方也請大家在評論下指出。 選擇排序就這么簡單 從上一篇已經(jīng)講解了冒泡排序了，本章主要講解的是選擇排序，希望大家看完能夠理解并手寫出選擇排序的代碼，然后就通過面試了！如果我寫得有錯誤的地方也請大家在評論下指出。 選擇排序介紹和穩(wěn)定性說明...

    wua_wua2012 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法（三）：帶你讀懂選擇排序（Selection sort）

    摘要：基本介紹選擇式排序也屬于內(nèi)部排序法，是從欲排序的數(shù)據(jù)中，按指定的規(guī)則選出某一元素，再依規(guī)定交換位置后達(dá)到排序的目的。而移動次數(shù)與序列的初始排序有關(guān)?？臻g復(fù)雜度簡單選擇排序需要占用個臨時空間，在交換數(shù)值時使用。 showImg(https://img-blog.csdnimg.cn/20190509221741422.gif); showImg(https://segmentfault....

    Kaede 評論0 收藏0

  • 【算法日積月累】1-選擇排序

    摘要：選擇排序算法實(shí)現(xiàn)實(shí)現(xiàn)選擇排序，記錄最小元素的索引，最后才交換位置說明交換兩個數(shù)組中的元素，在中有更簡單的寫法，這是的語法糖，其它語言中是沒有的。和語言中比較器的實(shí)現(xiàn)前面我們說到了，我們?yōu)榱送怀雠判蛩惴ǖ乃枷?，將所有的例子僅限在數(shù)組排序中。 showImg(https://segmentfault.com/img/remote/1460000017909538?w=1949&h=1080...

    neuSnail 評論0 收藏0

  • Github標(biāo)星2w+，熱榜第一，如何用Python實(shí)現(xiàn)所有算法

    摘要：歸并排序歸并排序，或，是創(chuàng)建在歸并操作上的一種有效的排序算法，效率為大符號。以此類推，直到所有元素均排序完畢。與快速排序一樣都由托尼霍爾提出的，因而也被稱為霍爾選擇算法。 showImg(https://segmentfault.com/img/remote/1460000019096360);編譯：周素云、蔣寶尚 學(xué)會了Python基礎(chǔ)知識，想進(jìn)階一下，那就來點(diǎn)算法吧！畢竟編程語言只...

    zxhaaa 評論0 收藏0

  • 排序算法（Java）——那些年面試常見的排序算法

    摘要：下面會介紹的一種排序算法快速排序甚至被譽(yù)為世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。為了展示初級排序算法性質(zhì)的價值，我們來看一下基于插入排序的快速的排序算法希爾排序。 前言 　　排序就是將一組對象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計算時代早期，大家普遍...

    Harpsichord1207 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<