数组排序，奇数在前，偶数在后（二）

一个无序整数数组，对它排序，使其前半部分都为奇数有序，后半部分为偶数有序。

第二种解法： 基本思想：先对数组进行分割，分割为两部分：奇数序列和偶数序列， 再利用任何一种排序算法排序。

#include <iostream> #include <algorithm> using namespace std; void PrintArr(int *arr, int n) { for (int i = 0; i < n; i++) { cout << arr[i] << " "; } cout << endl; } int Partition(int *arr, int n) { int odd = 0; int even = n-1; while (odd < even) { while (arr[odd] % 2 != 0 && odd < even) { odd++; } while (arr[even]% 2 == 0 && odd < even) { even--; } // swap int temp = arr[odd]; arr[odd] = arr[even]; arr[even] = temp; } return odd; } void OESort1(int *arr, int n) { int pivot = Partition(arr, n); std::sort(arr, arr + pivot); std::sort(arr + pivot, arr + n); } int main(int argc, char *argv[]) { int arr[] = {101, 2, 3, 5, 8, 12, 33, 6, 7}; OESort1(arr, sizeof(arr) / sizeof(arr[0])); PrintArr(arr, sizeof(arr) / sizeof(arr[0])); return 0; }

注：

分割可参考快速快速排序分割算法算法时间复杂度O(n*logn) （使用快速排序）