ACM教程 - 插入排序

定义

选择排序是一种简单直观的排序算法，其基本原理是每一次从待排序的数组里找到最小值（最大值）的下标，然后将最小值（最大值）跟待排序数组的第一个进行交换，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。反复的进行这样的过程直到待排序的数组全部有序。

• 稳定性：根据 相等元素 在数组中的 相对顺序 是否被改变，排序算法可分为「稳定排序」和「非稳定排序」两类。
• 就地性：根据排序过程中 是否使用额外内存（辅助数组），排序算法可分为「原地排序」和「异地排序」两类。一般地，由于不使用外部内存，原地排序相比非原地排序的执行效率更高。
• 自适应性：根据算法 时间复杂度 是否 受待排序数组的元素分布影响 ，排序算法可分为「自适应排序」和「非自适应排序」两类。「自适应排序」的时间复杂度受元素分布影响，反之不受其影响。
• 比较类：比较类排序基于元素之间的 比较算子（小于、相等、大于）来决定元素的相对顺序；相对的，非比较排序则不基于比较算子实现。

图解

性质

• 时间复杂度

• 最佳 O(n)
• 平均 O( )
• 最差 O( )

• 空间复杂度

• 最差 O(1)

• 稳定性：稳定
• 就地性：原地
• 自适应性：自适应
• 比较类：比较

Java

publicclassinsertSort {
publicstaticvoidmain(String[] args) {
int[] num= {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
intj;
// i=1; 从 1 开始, 没必要和自己比for (inti=1; i<num.length; i++) {
// 记录要插入的值, 这时就有了一个长度为 i+1 的数组可以进行移动inttemp=num[i];
// 在已排序的数组中找到比记录值（temp）要小的值, 位置往后移动（记住此时的数组长度（i+1））for (j=i-1; j>=0&&num[j] >temp; j--) {
// 符合条件的往后移动一位num[j+1] =num[j];
            }
// 归位, 此时符合条件的都全部移动了一位, 此时的 j+1 就是记录值要插入的位置num[j+1] =temp;
        }
System.out.println(Arrays.toString(num));
    }
}