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

資訊專欄INFORMATION COLUMN

數據結構與算法——選擇排序和插入排序

rockswang / 1450人閱讀

摘要：具體可參考我寫的這一篇文章數據結構與算法冒泡排序，今天來看看另外兩種基礎的排序算法選擇排序和插入排序。正因如此，選擇排序比起冒泡排序和插入排序就顯得遜色很多了。冒泡排序在交換數據的時候，需要進行三次賦值操作，而插入排序只需要一次。

1. 回顧

前面說到了冒泡排序，這是一種時間復雜度為 O(n2) 、是原地排序和穩定的的排序算法，具體思路是：根據相鄰兩個元素之間比較大小，然后交換位置，得出最后排序的結果。具體可參考我寫的這一篇文章：數據結構與算法——冒泡排序，今天來看看另外兩種基礎的排序算法：選擇排序和插入排序。

2. 選擇排序

先來看看選擇排序，選擇排序的思路其實很簡單，將排序的數據分為已排序區間和未排序區間，一般是以第一個元素為已排序區間，然后依次遍歷未排序區間，找到其最小值，和未排序區間的最后一個值進行比較，交換位置。未排序區間遍歷完畢，則排序結束。光說可能有點抽象，我畫了一張圖來幫助你理解：

是不是很簡單呢？下面是它的代碼實現：

public class SelectionSort {
    public static void selectionSort(int[] data){
        int length = data.length;
        //如果只有一個元素，或者數組為空，則直接退出
        if (length <= 1) return;

        for (int i = 0; i < length - 1; i++) {
            int min = i + 1;
            //找到最小值
            for (int j = i + 1; j < length; j++) {
                if (data[j] < data[min]) min = j;
            }
            //交換位置
            if (data[min] < data[i]){
                int temp = data[min];
                data[min] = data[i];
                data[i] = temp;
            }
        }
    }
}

結合代碼分析，選擇排序在最好、最壞和平均情況下的時間復雜度都是 O(n2)，并且沒有借助額外的存儲空間，是一種原地排序算法。那么選擇排序是穩定的嗎？答案是否定的，舉個例子：排序的數組為 data[2, 2, 1, 3, 5, 4, 8]，第一次遍歷未排序的數組，找到最小值為 1，和第一個 2 交換位置，那么這兩個 2 的前后順序就被打亂了，所以穩定性被破壞。正因如此，選擇排序比起冒泡排序和插入排序就顯得遜色很多了。

 3. 插入排序

我們再來看看插入排序，其實思路和上面的選擇排序非常的類似，也是將排序數據分為已排序區間和未排序區間，依次遍歷未排序區間，和已排序區間的值進行比較，將其插入到合適的位置上，直至將未排序的區間數據遍歷完。

你可以結合下面的圖來理解：

可以看到，和選擇排序一樣，將第一個數據作為已排序區間，第一次遍歷到 2 ，將其插入到 4 后面，然后再依次遍歷。
下面是代碼實現：

public class InsertionSort {
    public static void insertionSort(int[] data){
        int length = data.length;
        if (length <= 1) return;

        for (int i = 1; i < length; i++) {
            int value = data[i];
            int j = i - 1;
            for (; j >= 0; j --){
                if (data[j] > value) data[j + 1] = data[j];
                else break;
            }
            data[j + 1] = value;
        }
    }
}

很顯然，插入排序也是穩定的，因為我們是在 data[j] > da[j + 1] 的時候，才進行數據交換，不會影響到相同元素的前后位置。并且，插入排序是原地排序，最好情況下，數組本來就是有序的，所以我們只需要遍歷一次數組就可以了，時間復雜度是 O(n)，最壞情況和平均情況下，時間復雜度都是 O(n2)。

最后還有個問題，為什么在實際中，插入排序的比冒泡排序使用的更加廣泛呢？雖然這兩個排序算法的平均時間復雜度都是 O(n2)，但是結合代碼，不難發現，它們涉及到的數據交換操作時略有差別的。

冒泡排序在交換數據的時候，需要進行三次賦值操作，而插入排序只需要一次。

//插入排序的賦值操作            
for (; j >= 0; j --){
    if (data[j] > value) data[j + 1] = data[j];
    else break;
}

//冒泡排序的賦值操作        
for (int j = 0; j < n - i - 1; j++) {
    //如果data[j] > data[j + 1]，交換兩個數據的位置
    if (data[j] > data[j + 1]){
       int temp = data[j];
       data[j] = data[j + 1];
       data[j + 1] = temp;
    }

在數據規模小的時候，這樣的差別沒什么影響，但是如果我們要排序的是一組較大的數據，那么兩種排序算法的執行時間的差別就會很明顯了。

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

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

相關文章

  • JavaScript 數據結構與算法之美 - 冒泡排序、插入排序、選擇排序

    摘要：之所以把冒泡排序選擇排序插入排序放在一起比較，是因為它們的平均時間復雜度都為。其中，冒泡排序就是原地排序算法。所以冒泡排序是穩定的排序算法。選擇排序思路選擇排序算法的實現思路有點類似插入排序，也分已排序區間和未排序區間。 showImg(https://segmentfault.com/img/bVbuvnj?w=900&h=250); 1. 前言 算法為王。 想學好前端，先練好內功，...

    canger 評論0 收藏0

  • JavaScript 數據結構與算法之美 - 十大經典排序算法匯總

    摘要：筆者寫的數據結構與算法之美系列用的語言是，旨在入門數據結構與算法和方便以后復習。這應該是目前較為簡單的十大經典排序算法的文章講解了吧。比如原本在的前面，而，排序之后，在的后面十大經典排序算法冒泡排序思想冒泡排序只會操作相鄰的兩個數據。 showImg(https://segmentfault.com/img/bVbvHet); 1. 前言 算法為王。想學好前端，先練好內功，內功不行，就...

    zsy888 評論0 收藏0

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

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

    Harpsichord1207 評論0 收藏0

  • 常用排序算法之JavaScript實現

    摘要：代碼實現六堆排序算法簡介堆排序是指利用堆這種數據結構所設計的一種排序算法。九計數排序算法簡介計數排序是一種穩定的排序算法。計數排序不是比較排序，排序的速度快于任何比較排序算法。 贊助我以寫出更好的文章，give me a cup of coffee? 2017最新最全前端面試題 1、插入排序 1）算法簡介 插入排序（Insertion-Sort）的算法描述是一種簡單直觀的排序算法。它...

    jerry 評論0 收藏0

發表評論

0條評論

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