Java 实现插入排序

本文介绍插入排序原理及 Java 语言实现。

目录

• 插入排序原理
• 代码实现
  • 版本一
  • 版本二
  • 单元测试

插入排序原理

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
3. 升序时如果该元素（已排序）大于新元素，将该元素移到下一位置，降序时如果该元素（已排序）小于新元素，将该元素移到下一位置；
4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
5. 将新元素插入到该位置；
6. 重复步骤 2 ~ 5。

代码实现

版本一

package tutorial.java.util;

public class InsertionSortUtils {

    public static <T extends Comparable> void sort(T[] array, SortType sortType) {
        int comparableValue = sortType == SortType.ASC ? 1 : -1;
        for (int i = 0; i < array.length; i++) {
            T t = array[i];
            int j = i - 1;
            while (j >= 0 && array[j].compareTo(t) == comparableValue) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = t;
        }
    }

    public static enum SortType {
        ASC, DESC;
    }
}

版本二

package tutorial.java.util;

public class InsertionSortUtils {

    public static <T extends Comparable> void sort(T[] array, SortType sortType) {
        int comparableValue = sortType == SortType.ASC ? 1 : -1;
        for (int i = 0; i < array.length; i++) {
            T t = array[i];
            int j = i - 1;
            for (; j >= 0 && array[j].compareTo(t) == comparableValue; j--) {
                array[j + 1] = array[j];
            }
            array[j + 1] = t;
        }
    }

    public static enum SortType {
        ASC, DESC;
    }
}

单元测试

package tutorial.java.util;

import org.apache.commons.lang3.StringUtils;
import org.junit.Assert;
import org.junit.Test;

public class InsertionSortUtilsTest {

    @Test
    public void test() {
        Integer[] data = {10, 5, 1, 20, 3, 8, 99, 0, 16, 5};
        InsertionSortUtils.sort(data, InsertionSortUtils.SortType.ASC);
        Assert.assertEquals("0,1,3,5,5,8,10,16,20,99", StringUtils.join(data, ","));
        InsertionSortUtils.sort(data, InsertionSortUtils.SortType.DESC);
        Assert.assertEquals("99,20,16,10,8,5,5,3,1,0", StringUtils.join(data, ","));
    }
}