排序-插入排序 - JAVA学习网

https://en.wikipedia.org/wiki/Insertion_sort

对于插入排序

原理:从低位到高位执行遍历操作,遍历到的元素作为对比元素存在;对于对比操作,实际是通过高位到低位,将比较元素和[0,比较元素所在索引-1]区间的数据进行对比操作以及交换(移动)操作; 对于移动操作而言只移动被比较的元素,在比较循环结束后,将比较元素写入到空槽中;而无需在比较过程中就持续交换比较元素
插入排序也不需要额外的数组内存空间,只需要在原数组上进行操作,因此属于原地操作算法
稳定性:对于插入排序在比较操作时实际是通过高位和低位对比操作,当存在相同元素对比操作时,对于排序前后相同元素的相对位置并不会发生变化,因此属于稳定排序

java代码实现

public interface Sort<T extends Comparable<T>> {
    /**
     * 对数组进行排序
     *
     * @param array
     * @param flag  true 代表的是正序;false代表的是逆序
     */
    void sort(T[] array, boolean flag);
}

public class InsertSort<T extends Comparable<T>> implements Sort<T> {

    /**
     * 插入排序
     * 例如:
     * 5   4   3   2   1
     * j   i
     * j 和 j+1 位进行比较
     * 5 > 4 ,交换 5 和 4 的位置,且 j 指向的索引为 0,比较中止,i的位置往后移动一位, j 的位置 为 i-1
     * 4   5   3   2   1
     *      j   i
     * 5 > 3,交换 5 和 3 的位置,但j指向的索引不为0.因此,继续比较,i的位置不变,j的位置往前移动一位
     * 4   3   5   2   1
     * j       i
     * 4 > 3,交换 3 和 4 的位置,且j指向的索引为 0 ,比较中止,i的位置往后移动一位,j的位置为 i - 1
     * ..............
     *
     * @param array
     * @param flag  true 代表的是正序;false代表的是逆序
     */
    @Override
    public void sort(T[] array, boolean flag) {
        if (array == null || array.length < 2) {
            return;
        }
        int length = array.length;
        for (int i = 1; i < length; i++) {
            // 对于compareValue一直等于 array[j+1]
            T compareValue = array[i];
            int j = i - 1;
            for (; j >= 0; j--) {
                // flag && array[j].compareTo(compareValue) == 1 (array[j] > compareValue) 升序
                // !flag && array[j].compareTo(compareValue) == -1 (array[j] < compareValue) 降序
                if ((flag && array[j].compareTo(compareValue) == 1) || (!flag && array[j].compareTo(compareValue) == -1)) {
                    array[j + 1] = array[j];
//                    array[j] = compareValue;// 该交换操作实际是没有必要的
                } else {
                    break;
                }
            }
            // 可以在全部比较操作都执行结束后,在结束游标的后一位将当前比较的元素塞入数组中
            array[j + 1] = compareValue;
        }
    }

    public static void main(String[] args) {
        Integer[] values = new Integer[]{5, 3, 2, 1};
        Sort<Integer> integerInsertSort = new InsertSort<>();
        integerInsertSort.sort(values, true);
        Stream.of(values).forEach(System.out::print);
        System.out.println();
        integerInsertSort.sort(values, false);
        Stream.of(values).forEach(System.out::print);
    }
}

对于插入排序操作由于是从高位到低位进行对比,因此对于第一个元素实际没有可比较数据,因此遍历的起点从第二个元素开始,所以对于第一层for 循环中 i = 1而不是 "i = 0";这里i的另一个含义表示的是提供比较元素;将使用当前i指向的元素和[0,i-1]区间的元素进行对比操作;

对于比较操作,插入排序比较操作是从高位到低位进行顺序对比的;因此对于第二层循环 "j = i-1 ; j >=0 ; j--"; 对于[0,j]中的元素全部都是有序的,因此当存在不符合条件的对比操作时,直接终止当前循环操作,并将比较元素(array[i])插入当前[0,j]空闲插槽位置(j+1);

JDK实现

"JDK 15"

java.util.Arrays#mergeSort(java.lang.Object[], java.lang.Object[], int, int, int)

// Insertion sort on smallest arrays
if (length < INSERTIONSORT_THRESHOLD) {
    for (int i=low; i<high; i++)
        for (int j=i; j>low &&
                 ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
            swap(dest, j, j-1);
    return;
}

"未完待续-----剩余使用python+Matplotlib 绘制可视化动画"

https://zhuanlan.zhihu.com/p/38157591

JAVA学习网

分类