===============
== 大程熙 ==
===============
一个小学生

算法之成对插入排序学习

成对插入排序算法重新学习。

成对插入排序是对直接插入排序的改进,成对插入排序一次对两个元素进行排序。第一个元素排序好之后,第二个元素可以利用第一个元素已有排序信息来进行排序,减少重复元素的移动,提高效率。

成对插入排序算法

成对插入排序算法在直接插入排序算法基础上进行改进,算法描述如下:

  1. 成对插入排序一次对两个元素(a1和a2)进行排序,需要确保元素a1大于等于a2
  2. 先对a1进行排序,使用直接插入排序进行排序。
  3. a1排序完成后,a2只需要在a1的右边继续进行排序,无需重复a1左边的排序,因为a1大于等于a2,a2一定在a1左边位置。

成对插入排序代码示例

可以参考JDK8中源码:java.util.DualPivotQuicksort#sort(int[], int, int, boolean),以下代码是源码学习后写的示例:

/**
 * 成对插入排序
 * 直接插入排序的优化算法,一次处理两个相邻的元素
 */
public class PairInsertionSort {

    public void pairInsertionSort(Integer[] source) {

        for (int i = 1; i < source.length - 1; i += 2) {
            Integer a1 = source[i];
            Integer a2 = source[i + 1];

            // 确保a1大于等于a2
            if (a1 < a2) {
                a1 = a2;
                a2 = source[i];
            }

            int j;
            // 先排序a1
            for (j = i - 1; j >= 0 && source[j] > a1; j--) {
                source[j + 2] = source[j];
            }

            source[j + 2] = a1;

            // 排序a2
            for (; j >= 0 && source[j] > a2; j--) {
                source[j + 1] = source[j];
            }

            source[j + 1] = a2;
        }

        // 如果数组的待排序序列是奇数个,还会剩余最后一个未排序,需要再进行最后一次排序
        Integer last = source[source.length - 1];
        int j;
        for (j = source.length - 2; j >= 0 && source[j] > last; j--) {
            source[j + 1] = source[j];
        }

        source[j + 1] = last;
    }

    public static void main(String[] args) {
        Integer[] array = new Integer[] {3, 4, 6, 2, 3, 1, 4, 10, 48, 2, 3, 12, 14, 13};
        new PairInsertionSort().pairInsertionSort(array);
        System.out.println(Arrays.toString(array));
    }
}

代码里在最后又进行一次直接插入排序,是因为如果待排序序列如果是奇数个,最后一个元素是没法进行排序的,所以需要最后走一遍直接插入排序即可。

参考内容

  • JDK源码:Java8u192