算法之成对插入排序学习
成对插入排序算法重新学习。
成对插入排序是对直接插入排序的改进,成对插入排序一次对两个元素进行排序。第一个元素排序好之后,第二个元素可以利用第一个元素已有排序信息来进行排序,减少重复元素的移动,提高效率。
成对插入排序算法
成对插入排序算法在直接插入排序算法基础上进行改进,算法描述如下:
- 成对插入排序一次对两个元素(a1和a2)进行排序,需要确保元素a1大于等于a2
- 先对a1进行排序,使用直接插入排序进行排序。
- 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