[数据结构与算法]排序算法 - 插入排序

思路

1. 对数组进行遍历，从索引为1开始，从后往前遍历，如果当前索引处的值小于（或大于）上一个索引处的值则交换位置，那么索引1及其前面的值就都是有序的了，然后进行下一次遍历
2. 因为索引1前面的值已经都是有序的了，所以只需要找到索引2处的值在前面有序数组中的位置即可
3. 以此类推，直到所有元素均排序完毕

Code

public class InsertionSort {
    public void sort(int[] arr) {
        if (ArrayUtils.isEmpty(arr) || arr.length == 1) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1]) {
                    swap(arr, j, j - 1);
                }
            }
        }
    }

    private void swap(int[] arr, int index, int target) {
        int temp = arr[index];
        arr[index] = arr[target];
        arr[target] = temp;
    }
}

• 时间复杂度：O(N^2)

• 空间复杂度：O(1)

• 稳定性：稳定