阵列分函数

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. 仅当i < j时致电swapInArray。
2. 如有必要，在第一个元素末尾交换数据元。

更新功能：

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工作。