看動畫學算法之:排序-插入排序

• 2020 年 7 月 13 日
• 筆記
• JAVA, 動畫學算法, 排序, 插入排序, 數據結構, 算法

簡介

插入排序就是將要排序的元素插入到已經排序的數組中，從而形成一個新的排好序的數組。

這個算法就叫做插入排序。

插入排序的例子

同樣的，假如我們有一個數組：29,10,14,37,20,25,44,15，怎麼對它進行插入排序呢？

先看一個插入排序的動畫，對它有個直觀的了解：

我們來分析一下排序的流程。

八個數字，我們分為7輪。

第一輪，假設29是已經排好序的數組，從第二個元素開始，向排好序的數組插入新的元素。 也就是說向數組[29]插入10。得到[10,29]。

第二輪，[10,29]已經排好序了，選擇數組中的第三個元素14，插入排好序的數組[10,29]。

先將29和14比較，發現29>14,則將29右移一位[10, ,29],然後比較10和14，發現10小於14，那麼將14插入10後面[10,14,29]，以此類推。

插入排序的java程序

我們看下java程序怎麼寫：

public class InsertionSort {

    public void doInsertSort(int[] array){
        log.info("排序前的數組為:{}",array);
        int n = array.length;
        //從第二個元素開始插入
        for (int i = 1; i < n; ++i) {
            int key = array[i];
            int j = i - 1;
            //j表示的是要插入元素之前的已經排好序的數組
            //已經排好序的數組，從後向前和要插入的數據比較，如果比要插入的數據大，需要右移一位
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                    j = j - 1;
            }
            //最後的j+1的位置就是需要插入新元素的位置
            array[j + 1] = key;
            log.info("第{}輪排序後的數組為:{}", i+1, array);
        }

    }

    public static void main(String[] args) {
        int[] array= {29,10,14,37,20,25,44,15};
        InsertionSort insertionSort=new InsertionSort();
        insertionSort.doInsertSort(array);
    }
}

運行結果：

插入排序的時間複雜度

從代碼中我們可以看到，插入排序有一個for循環，在for循環中還有一個while循環。

所以插入排序的時間複雜度也是O(n²)。

本文的代碼地址：

learn-algorithm

本文已收錄於 //www.flydean.com/algorithm-insertion-sort/

最通俗的解讀，最深刻的乾貨，最簡潔的教程，眾多你不知道的小技巧等你來發現！

歡迎關注我的公眾號:「程序那些事」,懂技術，更懂你！