题目：
输入一个整数数组，实现一个函数，来调整该数组中数字的顺序
使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分
算法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;
}
