排序算法java實作——插入排序

插入排序

• 一、基本思路
• 二、算法分析
• 三、代碼實作

一、基本思路

基本思路： 把n個待排序元素看成一個有序表和一個無序表，開始時有序表中隻含有一個元素，無序表中包含n-1個元素，排序過程中每次從無序表中取出一個元素，把它依次與有序表中的元素進行比較，并插入到有序表的适當位置，使之成為新的有序表。

簡單來說： 就是先将第一個元素看成一個有序表，從第二個元素開始，依次 插入到對應的位置，直到所有元素都插入完成。

舉例：

有一序列為：101，34，119，1要求按升序排列

先把101看作一個有序表，從第二個元素開始，依次插入到有序表中适當的位置。

1. 第一輪（把34插入到有序表[101]中）

   （1）34，101，119，1（34小于101，是以将101後移，34插入到第一個位置）

2. 第二輪（把119插入到有序表[34,101]中）

   （1）34，101，119，1（119大于101，是以将119插入到101後面，即不改變）

3. 第三輪（把1插入到有序表[34,101,119]中）

   （1）1，34，101，119（1小于119、101、34，是以将這三個元素依次後移，将1插入到第一個位置）

   這樣4個數經過3輪插入序列就确定下來了。

二、算法分析

時間： 在插入排序中，當待排序數組是有序時，是最優的情況，隻需目前數跟前一個數比較一下就可以了，這時一共需要比較N- 1次，時間複雜度為 O(n);最壞的情況是待排序數組是逆序的，此時需要比較次數最多，總次數記為：1+2+3+…+N-1，是以，插入排序最壞情況下的時間複雜度為O(n²)。

空間： 可以看到，插入排序的元素後移以及插入操作都是在序列上直接進行的，無需另外開辟空間，是以空間複雜度為O(1)。

算法	平均時間	最好情形	最壞情形	穩定度	空間複雜度	備注
插入排序	O(n²）	O(n）	O(n²）	穩定	O（1）	大部分元素有序時較好

三、代碼實作

import java.util.Arrays;

/**
 * @author dankejun
 * @create 2020-04-28 12:13
 */
public class InsertSort {
    public static void main(String[] args) {
        int arr[] = {101,34,119,1};

        insertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void insertSort(int[] arr) {
        int insertVal;
        int insertIndex;
        for (int i = 1; i < arr.length ; i++) {
            insertVal = arr[i];
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertIndex + 1 != i) {

                arr[insertIndex + 1] = insertVal;
            }

            System.out.printf("第%d輪：%s\n",i,Arrays.toString(arr));
        }

    }
}
           

測試序列： int arr[] = {101,34,119,1};

測試結果：