数据结构——数组排序（左奇数、右偶数）
一 重新排列数组使得数组左边为奇数，右边为偶数
学习C语言是为了让大家如何写程序
学习数据结构是为了让大家更简洁、高效的写程序
程序：数据结构+算法
数据结构研究的是数据的逻辑结构、存储结构及其操作
1.1给定一个存放整数的数组，重新排列数组使得数组左边为奇数，右边为偶数。
要求:空间复杂度为0(1)，时间复杂度为0(n)。
1.2考查的知识点
（1）数组的基本操作 （2）数组相关的算法设计
二 问题分析
本题要求将数组元素重排，使得数组左边为奇数，右边为偶数。这有些类似于快速排序的 过程:在快速排序的一趟排序中， 首先指定一个 基准点，然后实现数组元素的一-次划分， 将小 于基准点的元素移动到基准点之前，将大于基准点的元素移动到基准点之后。本题可以借鉴快 速排序算法的思想来解决，数组重排的过程如下: 1)设定两个变量low和high, 作为数组下标分别指向数组第一 个和最后一个元素。 2)循环执行low++操作，直到low指向-一个偶数元素或者low>=high。 3)循环执行high--操作，直到high指向一个 奇数或者high <= low。 4)如果low>= high,则程序结束，此时数组的左边为奇数，右边为偶数;否则将数组中 low指向的元素与high指向的元素交换位置。再重复2)、3)、4)的操作。 下面通过一个实例进- - 步理解该算法，如图所示。
a为初始状态，数组内容为123456789， 此时low和high分别指向数组第一个元素 和最后- -个元素;图b为循环执行high--,直到high指向了一个奇数，此时high等于3;图c为循环执行low ++，直到low指向了一-个偶数，此时low等于1;因为low小于high,所以将low指向的元素与high指向的元素交换位置，变成d的样子;接下来重复图b、图c、图16- 10d的操作，直到low大于等于 high程序结束。最终数组为135792468 。
三 代码展示
下一篇：
九九乘法表——C语言