算法学习之InsertSort

今天咱们来简单聊一聊这个叫做插入排序的算法。

思路：

• 我们视最左端的数字已完成排序

• 然后，取出那些尚未操作的左端的数字，将其与已经操作的左侧的数字进行比较

• 如果左边的数字较大，交换两个数字

• 重复此操作，直到出现一个较小的数字或者数字达到左端

• 重复相同的操作，知道所有的数字完成排序

下面是一张比较直观的InsertSort的GIF

InsertSort.gif

性能分析：

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n²) 平均情况：T(n) = O(n²)

空间复杂度：O(1) 排序方式：In-place

稳定性：稳定

代码示例(Java版)：

public class InsertSort {

    public int[] insert_sort(int[] arr) {
        int arr_length = arr.length;
        int j;
        if (arr_length <= 1) return arr;
        for (int i = 1; i < arr_length; i++) {
            int temp = arr[i];
            for (j = i - 1; j >= 0; j--) {
                if (temp < arr[j]) arr[j + 1] = arr[j];
                else break;
            }
            arr[j + 1] = temp;
        }
        return arr;
    }

    private void print(int[] arr) {
        System.out.println();
        for(int i:arr) System.out.print(i + " ");
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {0, 5, 9, 7, 8, 4, 2, 3, 1, 6};
        InsertSort IS = new InsertSort();
        IS.print(IS.insert_sort(arr));
    }
}