OpenJudge

5:Partion

总时间限制:
100ms
内存限制:
1024kB
描述

写一个函数 void partion(int *low, int *high),它的参数给出一段内存区间。以第一个数为枢轴(pivot)划分为2个部分。前一部分的所有元素小于枢轴,后一部分的所有元素大于枢轴。

写一个函数 void show(int *buf, int size),输出一个整型数组所有元素的值。每个整数之间隔一个空格。输出结束时输出换行符。

写一个函数 void myswap(int *px, int *py),交换指针参数所指向的2个整型变量。

partion函数的具体做法是:low指针和high指针分别指向数组的第一个元素和最后一个元素。设枢轴(pivot)的值是数组第一个元素的值。先从high所指位置起向前搜索找到第一个关键字小于pivot的元素,交换此时low指针和high指针指向的元素。然后从low所指向的位置起向后搜索,找到第一个大于pivot的元素,交换此时low指针和high指针指向的元素。重复这两步直到low等于high为止。


代码示例如下:

#include

//partion函数,它的参数给出一段内存区间。以第一个数为枢轴(pivot)划分为2个部分。

//前一部分的所有元素小于枢轴,后一部分的所有元素大于枢轴。

void partion(int *low, int *high);

//show函数在一行上输出一个整型数组的所有元素,每个整数之间隔一个空格。

//输出结束后输出换行符

void show(int *buf, int size);

//myswap交换指针参数所指向的2个整型变量

void myswap(int *px, int *py);

int main(void)

{

    int buf[8] = {49, 38, 65, 97, 76, 13, 27, 49};

    //调用show函数

    //调用partion函数

    //调用show函数

    return 0;

}

//show函数的定义

//myswap函数的定义

//partion函数的定义


提示:

partion函数算法如下:

把 low 指向的元素赋值给 pivot

当 low 小于 high 时重复执行以下步骤:

{

      当 low 小于 high 并且 high 指向的元素大于等于 pivot 时

      {

            high 指向前一个元素

      }

      交换 low 指向元素与 high 指向元素的值

      当 low 小于 high 并且 low 指向的元素小于等于 pivot 时

      {

            low指向后一个元素

      }

      交换 low 指向元素与 high 指向元素的值

}

输入
输出
首先调用show函数输出分割之前的数组。
调用partion函数之后,再次调用show函数输出分割之后的数组。
样例输入
样例输出
49 38 65 97 76 13 27 49 
27 38 13 49 76 97 65 49 
来源
重庆科技学院 WJQ
全局题号
16477
添加于
2017-12-12
提交次数
60
尝试人数
45
通过人数
42