老青菜

剑指offer-调整数组顺序使奇数位于偶数前面

2017-01-23

题目

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

分析

假如现在有一个数组:

int a[] = {1,2,3,4,5,6,7,8,9};

交换后:

a = {1,9,3,7,5,6,4,8,2};

涉及到交换,我们可以参考交换排序的快速排序(QuickSort)。思路如下:

  1. 声明数组array,两个游标a、b,a指向array[0],b指向array[length-1]。
  2. a向后移动找到第一个偶数,此时第二个指针指向奇数5,不需要移动。
  3. 重复步骤2,直到a、b 相遇。

实现

void reOrder(int *arr, int length) {
    if (arr == NULL || length<=1) {
        return;
    }
    int x = 0;
    int y = length-1;
    while (true) {
        //x往后移动,找到偶数
        while (x<y && arr[x]%2!=0) {
            x++;
        }
        //往后移动,找到奇数
        while (y>x && arr[y]%2==0) {
            y--;
        }
        if (x==y) {
            break;
        }
        //交换找到的奇数、偶数
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}

添加测试代码

int arr[] = {9,4,5,6,8,20,11,1,15,2,4,7,3,1,13,14,16,24};
int length = sizeof(arr)/sizeof(int);
reOrder(arr, length);
for (int i=0; i<length; i++) {
    printf("%d,", arr[i]);
}

//output
9,13,5,1,3,7,11,1,15,2,4,20,8,6,4,14,16,24
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章