算法介绍
2-路插入排序是在折半插入排序的基础上改进的，插入排序的时间主要花在比较和移动这两种操作上。2-路插入排序可以减少排序过程中移动记录的次数，但为此需要借助n个记录的辅助空间。
算法描述
利用一个与排序序列一样大小的数组作为辅助空间，设置first和final指针标记辅助数组开始位置和最后位置。遍历未排序序列，如果待插入元素比已排序序列最小的元素(first位置)小，则first位置前移，将待排序元素插入first位置；如果待插入元素比已排序序列最大的元素(final位置)大，则final位置后移，将待排序元素插入final位置；如果待插入元素比最小大，比最大小，则需要移动元素，过程类似直接插入排序，不过考虑到循环使用数组，对于下标的处理有些许不同。处理完最后一个元素后，将排序记录复制到原来的顺序表里。
算法分析
时间复杂度：O(N2)
空间复杂度：O(N)
稳定性：稳定
虽然减少了移动次数，但移动次数还是占大部分，移动次数大约为N2/8次，并不能避免移动操作。并且当第一个元素是最大或最小关键字时，2-路插入排序就完全失去了它的优越性。
代码实现
// C++ void twoWayInsertionSort(int array[], int length) { const int len = length; // 用于定义辅助数组 int temp[len]; // 辅助数组 int first = 0; // 指示开始位置 int final = 0; // 指示最后位置 temp[0] = array[0]; // 加入第一个元素 for (int i = 1; i < length; ++i) { // 遍历未排序序列 // 由于循环使用数组，以下过程都需要取余操作保证数组下标合法 if (array[i] < temp[first]) { // 待插入元素比最小的元素小 first = (first - 1 + length) % length; // 开始位置前移 temp[first] = array[i]; // 插入元素 } else if (array[i] > temp[final]) { // 待插入元素比最大的元素大 final = (final + 1 + length) % length; // 最后位置后移 temp[final] = array[i]; // 插入元素 } else {// 插入元素比最小大，比最大小 int j = (final + 1 + length) % length; // 用于移动元素 while (temp[(j - 1) % length] > array[i]) { // 元素后移 temp[(j + length) % length] = temp[(j - 1 + length) % length]; j = (j - 1 + length) % length; } temp[(j + length) % length] = array[i]; // 插入元素 final = (final + 1 + length) % length; // 最后位置后移 } } // 将排序记录复制到原来的顺序表里 for (int k = 0; k < length; ++k) { array[k] = temp[(first + k) % length]; } }
参考
数据结构(C语言版)
————————————————
版权声明：本文为CSDN博主「Acx7」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
