HUFEOJ-1593:A002顺序表：划分1

金币值：0 定数：1 时间限制：1.000 s 内存限制：128 M

正确：8 提交：39 正确率：20.51% 命题人：

点赞量：0 收藏量：0 题目类型：程序知识点：顺序表，快速排序

划分操作是在给定的数组区间内选择一个基准元素（pivot），然后将数组重新排列，使得所有小于等于基准的元素位于基准的左边，所有大于基准的元素位于基准的右边。经过划分后，基准元素就处于其最终排序后的正确位置。划分是快速排序的关键操作。

算法描述如下：

选择基准元素：通常选择数组区间的首元素作为基准元素。
初始化指针：设置 left 从数组区间的起始位置开始，right 从数组区间的末尾位置开始。
循环条件：如果left>=right，则跳转到第5步；否则进入第4步。
移动指针并移动元素：
- 从右向左移动 right ，直到找到一个小于等于基准的元素。然后将right指向的元素移到left位置，再将left右移一下。
- 从左向右移动 left ，直到找到一个大于基准的元素。然后将left指向的元素移到right位置，再将right左移一下。
- 返回到第3步。
放置基准元素：将基准元素移到left位置，此时所有小于基准的元素位于基准的左边，所有大于基准的元素位于基准的右边。

请用c/c++实现求该算法循环过程中元素的移动次数，函数头如下：

int partition(Elemtype a[],int left,int right)//以a[left]为基准对a[left..right]划分

并编写main函数测试该算法。

两行：

第1行：整数n(0<n<10000)

第2行：n个整数

一个整数

7
5 3 1 6 8 2 10

10
5 3 8 4 2 7 1 6 9 10

对于样例2详细的模拟步骤如下：

初始化：
- 数组 a：[5, 3, 8, 4, 2, 7, 1, 6, 9, 10]
- 基准 base = a[0] = 5
- i = 0，j = 9，n = 0
从右向左找小于基准的元素：
- 从 j = 9 开始向左找，找到 a[6] = 1 小于基准 5，此时 i = 0，j = 6。
- 将 a[6] 的值赋给 a[0]，数组变为 [1, 3, 8, 4, 2, 7, 1, 6, 9, 10]，i++变为 1，n++变为 1。
从左向右找大于基准的元素：
- 从 i = 1 开始向右找，找到 a[2] = 8 大于基准 5，此时 i = 2，j = 6。
- 将 a[2] 的值赋给 a[6]，数组变为 [1, 3, 8, 4, 2, 7, 8, 6, 9, 10]，j 变为 5，n 变为 2。
继续从右向左找小于基准的元素：
- 从 j = 5 开始向左找，找到 a[4] = 2 小于基准 5，此时 i = 2，j = 4。
- 将 a[4] 的值赋给 a[2]，数组变为 [1, 3, 2, 4, 2, 7, 8, 6, 9, 10]，i 变为 3，n 变为 3。
继续从左向右找大于基准的元素：
- 从 i = 3 开始向右找，a[3] = 4 小于基准 5，继续向右，i 变为 4，此时 i = 4，j = 4，循环结束。
放置基准元素：
- 将基准 5 放到 a[4] 的位置，数组变为 [1, 3, 2, 4, 5, 7, 8, 6, 9, 10]。

1593: A002顺序表：划分1