插入排序法

插入排序，一般也被称为直接插入排序。插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。

public class InsertionSort {
    public static void main(String[] args) {
        Integer[] data = new Integer[]{17, 23, 15, 2, 19, 11, 22, 33, 14, 27, 16, 7, 6};
        InsertionSort insertionSort = new InsertionSort();
        insertionSort.sort(data);
    }

    public void sort(Comparable[] data) {
        for (int i = 1; i < data.length; i++) {
            for (int j = i; j > 0 && (data[j].compareTo(data[j - 1]) < 0); j--) {
                Comparable temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
                System.out.println("第" + (i - 1) + "环的倒数第" + (j - 1) + "步" + Arrays.toString(data));
            }
        }
        System.out.println("结果" + Arrays.toString(data));
    }
}

运行结果：

第1环的倒数第1步[17, 15, 23, 2, 19, 11, 22, 33, 14, 27, 16, 7, 6]

第1环的倒数第0步[15, 17, 23, 2, 19, 11, 22, 33, 14, 27, 16, 7, 6]

第2环的倒数第2步[15, 17, 2, 23, 19, 11, 22, 33, 14, 27, 16, 7, 6]

第2环的倒数第1步[15, 2, 17, 23, 19, 11, 22, 33, 14, 27, 16, 7, 6]

第2环的倒数第0步[2, 15, 17, 23, 19, 11, 22, 33, 14, 27, 16, 7, 6]

第3环的倒数第3步[2, 15, 17, 19, 23, 11, 22, 33, 14, 27, 16, 7, 6]

第4环的倒数第4步[2, 15, 17, 19, 11, 23, 22, 33, 14, 27, 16, 7, 6]

第4环的倒数第3步[2, 15, 17, 11, 19, 23, 22, 33, 14, 27, 16, 7, 6]

第4环的倒数第2步[2, 15, 11, 17, 19, 23, 22, 33, 14, 27, 16, 7, 6]

第4环的倒数第1步[2, 11, 15, 17, 19, 23, 22, 33, 14, 27, 16, 7, 6]

第5环的倒数第5步[2, 11, 15, 17, 19, 22, 23, 33, 14, 27, 16, 7, 6]

第7环的倒数第7步[2, 11, 15, 17, 19, 22, 23, 14, 33, 27, 16, 7, 6]

第7环的倒数第6步[2, 11, 15, 17, 19, 22, 14, 23, 33, 27, 16, 7, 6]

第7环的倒数第5步[2, 11, 15, 17, 19, 14, 22, 23, 33, 27, 16, 7, 6]

第7环的倒数第4步[2, 11, 15, 17, 14, 19, 22, 23, 33, 27, 16, 7, 6]

第7环的倒数第3步[2, 11, 15, 14, 17, 19, 22, 23, 33, 27, 16, 7, 6]

第7环的倒数第2步[2, 11, 14, 15, 17, 19, 22, 23, 33, 27, 16, 7, 6]

第8环的倒数第8步[2, 11, 14, 15, 17, 19, 22, 23, 27, 33, 16, 7, 6]

第9环的倒数第9步[2, 11, 14, 15, 17, 19, 22, 23, 27, 16, 33, 7, 6]

第9环的倒数第8步[2, 11, 14, 15, 17, 19, 22, 23, 16, 27, 33, 7, 6]

第9环的倒数第7步[2, 11, 14, 15, 17, 19, 22, 16, 23, 27, 33, 7, 6]

第9环的倒数第6步[2, 11, 14, 15, 17, 19, 16, 22, 23, 27, 33, 7, 6]

第9环的倒数第5步[2, 11, 14, 15, 17, 16, 19, 22, 23, 27, 33, 7, 6]

第9环的倒数第4步[2, 11, 14, 15, 16, 17, 19, 22, 23, 27, 33, 7, 6]

第10环的倒数第10步[2, 11, 14, 15, 16, 17, 19, 22, 23, 27, 7, 33, 6]

第10环的倒数第9步[2, 11, 14, 15, 16, 17, 19, 22, 23, 7, 27, 33, 6]

第10环的倒数第8步[2, 11, 14, 15, 16, 17, 19, 22, 7, 23, 27, 33, 6]

第10环的倒数第7步[2, 11, 14, 15, 16, 17, 19, 7, 22, 23, 27, 33, 6]

第10环的倒数第6步[2, 11, 14, 15, 16, 17, 7, 19, 22, 23, 27, 33, 6]

第10环的倒数第5步[2, 11, 14, 15, 16, 7, 17, 19, 22, 23, 27, 33, 6]

第10环的倒数第4步[2, 11, 14, 15, 7, 16, 17, 19, 22, 23, 27, 33, 6]

第10环的倒数第3步[2, 11, 14, 7, 15, 16, 17, 19, 22, 23, 27, 33, 6]

第10环的倒数第2步[2, 11, 7, 14, 15, 16, 17, 19, 22, 23, 27, 33, 6]

第10环的倒数第1步[2, 7, 11, 14, 15, 16, 17, 19, 22, 23, 27, 33, 6]

第11环的倒数第11步[2, 7, 11, 14, 15, 16, 17, 19, 22, 23, 27, 6, 33]

第11环的倒数第10步[2, 7, 11, 14, 15, 16, 17, 19, 22, 23, 6, 27, 33]

第11环的倒数第9步[2, 7, 11, 14, 15, 16, 17, 19, 22, 6, 23, 27, 33]

第11环的倒数第8步[2, 7, 11, 14, 15, 16, 17, 19, 6, 22, 23, 27, 33]

第11环的倒数第7步[2, 7, 11, 14, 15, 16, 17, 6, 19, 22, 23, 27, 33]

第11环的倒数第6步[2, 7, 11, 14, 15, 16, 6, 17, 19, 22, 23, 27, 33]

第11环的倒数第5步[2, 7, 11, 14, 15, 6, 16, 17, 19, 22, 23, 27, 33]

第11环的倒数第4步[2, 7, 11, 14, 6, 15, 16, 17, 19, 22, 23, 27, 33]

第11环的倒数第3步[2, 7, 11, 6, 14, 15, 16, 17, 19, 22, 23, 27, 33]

第11环的倒数第2步[2, 7, 6, 11, 14, 15, 16, 17, 19, 22, 23, 27, 33]

第11环的倒数第1步[2, 6, 7, 11, 14, 15, 16, 17, 19, 22, 23, 27, 33]

结果[2, 6, 7, 11, 14, 15, 16, 17, 19, 22, 23, 27, 33]

从结果上来看不难发现插入排序法通过一次插入一个元素的方式按照原有排序方式增加元素，插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。

如果待排序的序列中存在两个或两个以上具有相同关键词的数据，排序后这些数据的相对次序保持不变，即它们的位置保持不变，通俗地讲，就是两个相同的数的相对顺序不会发生改变，则该算法是稳定的，所以插入排序算法是稳定的。

最后

以上就是刻苦枕头为你收集整理的插入排序法的全部内容，希望文章能够帮你解决插入排序法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。