陣列分函數

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