面试题：调整数字顺序，使奇数位于偶数前面

本文主要是介绍面试题：调整数字顺序，使奇数位于偶数前面，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

输入一个整数数组，实现一个函数，来调整该数组中数字的顺序

使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分

算法1：

利用快速排序的一次划分思想，从2端往中间遍历

时间复杂度：O（n）,只遍历一次

空间复杂度：O（1），只在当前数组里面移动，找到就交换

#include <stdio.h>void Move(int* arr, int len)
{int low = 0;//起始下标，左int high = len - 1;//结束下标，右while (low < high)//左右下标未相遇，数据还未处理完{while (low < high && (arr[low] % 2) != 0)//从前往后找偶数，奇数就跳过{low++;}//出来arr[low]==0，偶while (low < high && (arr[high] % 2) == 0)//从后往前找奇数，偶数就跳过{high--;}//出来arr[high]!=0，奇if (low < high)//奇偶数交换{int tmp = arr[low];arr[low] = arr[high];arr[high] = tmp;}}
}//输出arr的所有数据
void Show(int* arr, int len)
{for (int i = 0; i < len; i++){printf("%d  ", arr[i]);}printf("\n");
}int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };Move(arr, sizeof(arr) / sizeof(arr[0]));Show(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

算法2：

遍历数组，并把偶数移到数组的末尾

时间复杂度：O(n)

空间复杂度：O(1)

void Move(int* arr, int len)
{int tmp;//拿出的偶数暂存位置for (int i = 0; i < len - 1; i++)//最后一个数字不需要处理//是奇数则是处理后的最后一个奇数，是偶数则是处理后的第一个偶数{if ((arr[i] % 2) == 0)//是偶数{tmp = arr[i];//把当前偶数拿出来for (int j = i; j + 1 < len; j++)//后面所有数据前移一位{arr[j] = arr[j + 1];//从i+1开始，依次往前移动}arr[len - 1] = tmp;//当前偶数放到数组最后位置}}
}//输出arr的所有数据
void Show(int* arr, int len)
{for (int i = 0; i < len; i++){printf("%d  ", arr[i]);}printf("\n");
}int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };Move(arr, sizeof(arr) / sizeof(arr[0]));Show(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}

算法3：（这个奇偶数的原顺序不变）

额外定义一个数组，存放数据（空间复杂度为O(n)）

遍历原数组2遍（时间复杂度为O(n)）

第一遍把所有的奇数复制到新数组

第二遍把所有的偶数复制到新数组

void Move(int* arr, int len)
{int* brr = (int*)malloc(len * sizeof(int));int i = 0;//arr下标int j = 0;//brr下标//把所有奇数放到brr前半部分for (i = 0; i < len; i++){if ((arr[i] % 2) != 0)//奇数brr[j++] = arr[i];}//把所有偶数放到brr后半部分for (i = 0; i < len; i++){if ((arr[i] % 2) == 0)//偶数brr[j++] = arr[i];}//把brr中的数据重新复制到arrfor (i = 0; i < len; i++)arr[i] = brr[i];//位置不同ij,位置相同都ifree(brr);}//输出arr的所有数据
void Show(int* arr, int len)
{for (int i = 0; i < len; i++){printf("%d  ", arr[i]);}printf("\n");
}int main()
{int arr[] = { 1,2,3,4,5,6,7,8,9,10 };Move(arr, sizeof(arr) / sizeof(arr[0]));Show(arr, sizeof(arr) / sizeof(arr[0]));return 0;
}