将一个数组分成奇数部分和偶数部分，并分别排好序 CVTE

给定一个数组，将奇数放到前面，偶数放到后面，各自排好序

（2016年3月12日晚上，CVTE笔试编程第一道题）：

思路很简单：

（1）先将数组中的奇数和偶数分开（利用两个指针遍历一遍即可，同时统计好数组中奇数的个数）；

（2）然后分别进行快速排序。

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
void quick_sort(int *nums, int first, int last);
int partion(int *nums, int first, int last);
void sort(int *nums, int length)
{
    int count1 = 0, count2 = 0;
    int *first = nums;
    int *last = nums + length - 1;
    while (first < last)
    {
        while (*first % 2 == 1)
        {
            count1++; first++;
        }
        while (*last % 2 == 0)
        {
            count2++; last--;
        }
        if (first < last)//这个条件判断很是关键，防止一开始就归类好的情况下（前面都是奇数，后面都是偶数），二者越界交换
        {
            int temp = *first; *first = *last; *last = temp;
            first++;
            last--;
            count1++;//二者交换完成后，也别忘记各自统计一次
            count2++;
        }
    }
    quick_sort(nums, 0, count1 - 1);
    quick_sort(nums, count1, length - 1);
}
void quick_sort(int *nums, int first, int last)
{
    if (first >= last)return;
    int  mid = partion(nums, first, last);
    quick_sort(nums, first, mid - 1);
    quick_sort(nums, mid + 1, last);
}
int partion(int *nums, int first, int last)
{
    int ptvor = nums[first];
    while (first < last)
    {
        while (nums[last]>ptvor&&first < last)
            last--;
        nums[first] = nums[last];
        while (nums[first] <= ptvor && first < last) first++;
        nums[last] = nums[first];
        swap(nums[first], nums[last]);//？？？？2016年3月22日再看到，莫名其妙的一句是不是
    }
    nums[last] = ptvor;
    return last;
}

int main()
{
    int nums[10] = { 3, 6, 2, 10, 9, 22, 1, 8, 13, 15 };
    sort(nums, 10);
    for (int i = 0; i < 10; i++)
        cout << nums[i] << " ";
    return 0;
}