c++ - 数组分区函数

Question

我正在编写一个获取 int 数组及其大小的函数:

void partition(int data[], int size) 

数组的第一个元素被分配给名为 val 的变量，函数需要对数组进行分区，使得 val 左侧的元素小于val，右边的元素更大。

例如，

• 如果数组是:5 2 10 4 1 12 7(val 变为 5)

  <

• 输出应该是2 4 1 5 10 12 7

顺序无关紧要，所以 1 2 4 5 12 7 10 也是有效的输出

所以我写了这段代码:

void partition(int data[], int size)
{
    int val = data[0];
    int i = 0, j = size - 1;//array indices
    while (i != j)
    {
        while (data[i] < val)
            i++;
        while (data[j] > val)
                j--;
        swapInArray(data, i, j);
    }
}

它工作正常，除非它得到一个元素等于 val 的数组。

例如:7 8 5 176 18 19 7 12 44

Answer 1

一些更改应该可以解决它。

1. 使用while ( i < j )而不是 while ( i != j ) .
2. 使用while (data[i] <= val)而不是 while (data[i] < val)

这是我的建议:

void partition(int data[], int size)
{
   int val = data[0];
   int i = 0, j = size - 1;
   while (i < j)
   {
      while (data[i] <= val)
         i++;
      while (data[j] > val)
         j--;
      swapInArray(data, i, j);
   }
}

更新

需要进行更多更改。

1. 调用swapInArray仅当i < j .
2. 用 j 交换枢轴- 末尾的第一个元素，如有必要。

更新函数:

void partition(int data[], int size)
{
   int val = data[0];
   int i = 1, j = size - 1;//array indices
   while (i < j)
   {
      while (i < j && data[i] <= val)
         i++;

      while (data[j] > val)
         j--;

      if ( i < j )
         swapInArray(data, i, j);
   }
   if ( val > data[j] )
      swapInArray(data, 0, j);
}

在 http://ideone.com/5A3wTN 查看它的工作情况.