一个无序整数数组，对它排序，使其前半部分都为奇数有序，后半部分为偶数有序。
基本想法：利用插入排序算法，对奇偶子序列分别插入排序。用两个变量把整个数组分割为三个部分，第一个部分为奇数有序子序列，第二部分为偶数有序子序列，第三部分为未排序子序列。使用两个变量进行分割，mid 指向偶数有序子序列的一个元素，end 指向未排序子序列（等待一个个插入前面的奇数有序子序列或偶数有序子序列）。
_________________________________________________________ | 奇数有序子序列 | 偶数有序子序列 | 未排序子序列 | _________________________________________________________ | | mid end #include <iostream> using namespace std; void PrintArr(int *arr, int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; } void OESort(int *arr, int n) { cout << "Array Count : "<< n << endl; int mid = 0; int end = 0; for (; end < n; end++) { int currValue = arr[end]; int j = end; if (currValue % 2 != 0) { // Odd while (((j-1) >= mid) || (currValue < arr[j-1]) && ((j-1) >= 0)) { arr[j] = arr[j-1]; j--; } arr[j] = currValue; mid++; } else { // Even while ((j - 1) >= mid && currValue < arr[j-1]) { arr[j] = arr[j-1]; j--; } arr[j] = currValue; } } } int main(int argc, char *argv[]) { int arr[] = {101, 2, 3, 5, 8, 12, 33, 6, 7}; OESort(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); return 0; }初始时，mid 和 end 变量为0， 表示奇数有序子序列和偶数有序子序列都为空。取end 变量指向的元素一个个向前插入两个有序子序列中，end之前的元素可以依次向后移动，根据end指向元素是奇数还是偶数，分别不同处理。
奇数时， 要先跳过偶数区（(j-1) >= mid) 条件， j-1是要向后移动元素索引，下同）， 移动到奇数区就和插入排序条件一样了（(currValue < arr[j-1]) && ((j-1) >= 0) 条件）。移动结束，j位置为空，也是要插入的位置。这时奇数子序列长度加一，所以mid应向后移动一个。
偶数时，条件相对简单了，不用跳过一部分序列，直接使用插入排序，但需判断不要越过偶数子序列的第一个元素（(j - 1) >= mid 条件）。
注： 1. j-1 是要向后移动的元素索引，保持循环不变性。 2. 算法时间复杂度O（n²）
