对数组进行分区
给定一个由 n 个元素组成的随机排序数组 (arr)，函数 partitionArray(int arr[], int n, int x) 将元素划分为两个子集，使得元素 <= x 在左侧子集中，元素 > x 在右侧子集。
测试用例的第一行将包含两个由空格分隔的数字 n（列表中的元素数）和 x（用于分区的数字）。下一行将包含 N 个空格分隔的整数。
对于某些情况，我从以下函数中得到了错误的输出。
这是我的代码：
void partitionArray(int arr[], int n, int x)
{
int i, j, temp;
i = 0;
j = n-1;
while (i < j)
{
while (arr[i] <=x)
i++;
while (arr[j] > x)
j--;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
对于我得到正确输出的情况是：
10 6
28 26 25 5 6 7 24 29 6 10
对于我没有得到正确输出的情况是：
10 17
28 26 25 11 16 12 24 29 6 10
The output I am getting in this:
10
6
12
11
25
16
24
29
26
28
Expected Output:
10
6
12
11
16
25
24
29
26
28
10 6
28 26 25 11 5 7 24 29 6 10
The output I am getting in this:
6
25
5
11
26
7
24
29
28
10
Expected Output:
6
5
25
11
26
7
24
29
28
10
谁能帮我这个
回答
以下更改将执行以下操作：
if(i < j){
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
当 j 的值为 i+1 和arr[i]<xand时交换时arr[j]>x，在while 循环之后i++和j--来自 while 循环时，j 的值在您的代码中为 i-1。因此，i<j在交换之前检查很重要。
假设输入是
2 5
1 10
你的输出将是
10 1
并且必须检查索引，因为索引可能会超出数组的大小。
while (i<n && arr[i]<=x)
i++;
while (j>=0 && arr[j]>x)
j--;
示例输入：
5 7
5 3 2 4 1
5 3
7 6 9 5 6