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

题目描述

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

算法分析

算法:利用快速排序的一次划分思想，后面的奇数往前移，前面的偶数往后移

时间复杂度 ：O(n)
空间复杂度 ：O(1)

完整代码

void Move(int* arr, int len)
{
    int low = 0;//起始下标
    int high = len - 1;//结束下标
    while (low < high)//数据还没有处理完成
    {
        while (low<high && (arr[low]&1)==1)//从前往后找偶数
        {
            ++low;
        }
        while (low<high && (arr[high]&1)==0)//从后往前找奇数
        {
            --high;
        }
        if (low < high) //奇偶数交换
        {
            int tmp = arr[low];
            arr[low] = arr[high];
            arr[high] = tmp;
        }
    }
}
int main()
{
	int arr[10] = { 1,2,43,41,6,4,21,4,2,3 };
	int len = sizeof(arr) / sizeof(arr[0]);
	Move(arr, len);
	for (int i = 0;i < len;i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

---

---

本篇完！