Java直接插入排序算法实现

下面是“Java直接插入排序算法实现”的完整攻略。

算法简介

直接插入排序，也叫插值排序，是对于插入排序算法的一种变形。与通常的插入排序不同之处在于，它可以在O(n)的时间内完成前n个元素的排序。类似于整理扑克牌，抓出一张新牌插入手中的牌序中。遍历未排序的元素，将其插入到已排序的序列中的正确位置。

算法步骤

1. 从第一个元素开始，该元素可以认为已经被排序
2. 取出下一个元素，插入到已经排序的元素序列中
3. 对于新插入的元素，从后往前遍历已排序的序列
4. 如果当前遍历到的元素大于新元素，则将大于新元素的元素往后移动一位
5. 重复步骤3,4 直到找到正确的位置并插入元素
6. 重复步骤2~5

Java代码实现

public class InsertionSort {
    public static void main(String[] args) {
        int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        insertionSort(arr);
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }

    public static void insertionSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        for (int i = 1; i < arr.length; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j > 0 && temp < arr[j - 1]; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}

算法分析

• 平均时间复杂度为O(n²)
• 空间复杂度为O(1)
• 稳定排序

示例说明

示例一

输入：[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

输出：[1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

示例二

输入：[6, 5, 4, 3, 2, 1]

输出：[1, 2, 3, 4, 5, 6]

在以上示例中，我们可以看到插入排序成功将无序的数组进行排序，而且在示例一中，排序后结果依然保持了元素原本的相对位置不变，因此这种排序方法被称为稳定排序。