国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

算法之旅 | 選擇排序法

liaorio / 2134人閱讀

摘要:由于排序的算法有很多,在本次算法系列的分享當中,我們先從簡單易上手的選擇排序法開始,其它的排序算法會隨后陸續跟大家一起分享。

HTML5學堂-碼匠:數據快速的計算與排序,與前端頁面性能有直接的關系。由于排序的算法有很多,在本次“算法系列”的分享當中,我們先從簡單易上手的選擇排序法開始,其它的排序算法會隨后陸續跟大家一起分享。

算法的基本概念 算法是什么,它有何作用

為解決一個問題而采取的方法和步驟,稱為算法。
我們可以把算法看成一本“福字剪紙教程”,其中每一種算法就是剪紙教程中的一種包含“固定步驟”的剪紙方法,使用者只要按照步驟進行剪紙,就可以剪出好看的福字。
之所以有這么多的算法,在于不同算法解決問題的效率各有不同適合不同的場景。隨著問題規模的增長,算法之間的差距會變的不可跨越。提升解決問題的效率,不僅僅依賴于選擇快速的硬件,還依賴于選擇有效(適合)的算法。

排序的使用場景

針對數組進行從大到小(或從小到大)的排序。例如:管理系統中按照成績的排序,按閱讀量對文章的排序等。
數據快速的計算與排序,與前端頁面性能有直接的關系。(譬如在頁面中有10000條的數據需要靠JS進行排序,采用不同的算法所消耗的時間差距甚大,直接影響著網站的用戶體驗)

常見的排序方法

較為常見的排序方法,包括:冒泡排序、選擇排序、快速排序、二分法插入排序等。
由于排序的算法有很多,在本次“算法系列”的分享當中,我們先從簡單易上手的選擇排序法開始,其它的排序算法會隨后陸續跟大家一起分享。

選擇排序法的基本原理

先找到序列中最小的數,將它和序列中第一個數交換位置;
接下來,在剩下的序列中繼續此操作:找到最小的數,將它和序列中的第二個數交換位置;
依此類推,直到將整個序列排序完成。
簡言之,選擇排序就是 —— 不斷地選擇剩余序列中最小者,然后與未排序數列的“第一個”數字交換位置。

案例說明

實現選擇排序的步驟分解 排序次數

排序次數:序列長度 – 1(注意,不是比較次數);
因為序列中的最后一個數不需要再次比較大小,故排序次數為 序列長度 – 1。

找到最小的數

序列中找到最小的數,并記錄該數的索引值;
因為minIndex默認開始為0,則第一個數無需與自身比較,所以j = i + 1;

// 遍歷序列,找到最小的數
for (var j = i + 1; j < len; j++) {
    if (arr[j] < arr[minIndex]) {
        // 記錄最小數的索引
        minIndex = j;
    };
};

在排序次數內多次遍歷找到最小的數,因此需要再用一個for語句來進行控制。

// 排序次數
for (var i =   0; i < len - 1; i++) {

    // 默認最小數的索引為i
    minIndex = i;

    // 遍歷序列,找到最小的數
    for (var j = i + 1; j < len; j++) {
        if (arr[j] < arr[minIndex]) {
            // 記錄最小數的索引
            minIndex = j;
        };
    };
};
兩數交換位置

利用temp變量,實現兩數組元素之間數值的交換,也就是交互位置。

temp =   arr[i];
arr[i] =   arr[minIndex];
arr[minIndex]   = temp;
選擇排序法完整代碼
var arr = [9, 8, 3, 1, 2, 4],
    len = arr.length,
    minIndex, temp;
 
    // 排序次數
    for (var i =   0; i < len - 1; i++) {

        // 默認最小數的索引為i
        minIndex = i;

        // 遍歷剩下的序列,找到最小的數
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {
                // 記錄最小數的索引
                minIndex = j;
            };
        };

    // HTML5學堂出品

    // 兩數交互位置
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;

};

console.log(arr);

歡迎溝通交流~~~HTML5學堂(碼匠)

選擇排序法的效率 算法復雜度的基本概念

算法復雜度分為時間復雜度和空間復雜度(時間和空間是計算機最重要的資源,因此復雜度分為時間和空間)。
時間復雜度:指執行算法所需要的計算工作量;
空間復雜度:指執行算法所需要的內存空間。

時間復雜度:O(n*n)

時間復雜度是總運算次數表達式中受n的變化影響最大的項(不含系數);
第一次循環比較n-1次,然后是n-2次,n-3次,依此類推,最后一次循環比較1次,總的比較次數和為(n - 1 + 1) * n / 2,即進行比較操作的時間復雜度為O(n^2)
Tips:選擇排序的比較次數與序列的初始排序無關。

空間復雜度:O(1)

排序算法需要一個額外的空間(temp變量)來交換元素的位置。

不穩定排序的一種算法

選擇排序是一種不穩定排序的算法。
比如:序列[3, 8, 3, 1, 9 ],第一次循環第1個元素3會和1交換,變成[1, 8, 3, 3, 9],此時,原序列中兩個3的先后順序被破壞。

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/84818.html

相關文章

  • 之旅 | 快速排序

    摘要:今天跟大家分享多種排序算法里使用較廣泛,速度快的排序算法快速排序法平均時間復雜度為。快速排序法的原理快速排序是一種劃分交換排序,它采用分治的策略,通常稱其為分治法。 HTML5學堂-碼匠:前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法,它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛,速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...

    AlanKeene 評論0 收藏0
  • 之旅 | 冒泡排序

    摘要:學堂碼匠本期繼續走入算法冒泡排序法。冒泡排序法完整代碼冒泡排序法的優化假如序列的數據為使用上面的冒泡排序法進行排序,得到的結果肯定沒有問題,但是,待排序的序列是有序的,理論上是無需遍歷排序。 HTML5學堂-碼匠:本期繼續走入算法 —— 冒泡排序法。冒泡排序算法相對簡單,容易上手,穩定性也比較高,算是一種較好理解的算法,也是面試官高頻提問的算法之一。 Tips:關于算法及排序的基礎知識...

    qujian 評論0 收藏0

發表評論

0條評論

liaorio

|高級講師

TA的文章

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