Bubble Sort 2D Array

我有一個2D數組，看起來像這樣;Bubble Sort 2D Array

0. PID: 0, PRI:-1 
1. PID: 0, PRI:-1 
2. PID: 0, PRI:-1 
3. PID: 15, PRI:4 
4. PID: 209, PRI:5 
5. PID: 0, PRI:0 
6. PID: 0, PRI:0 
7. PID: 0, PRI:0 
8. PID: 0, PRI:0 
9. PID: 0, PRI:0

什麼是移動PID與有效PRI的最快和最合理的方式（其中PRI> 0）到陣列的頂部，而基於該PRI讓他們在數字順序。

感謝

來源

2013-02-28 Jake Evans

這聽起來不像二維排序，聽起來像是你先在一個屬性上進行1d排序，然後是另一個屬性。順便說一下，2d排序與1d排序相同，你只需在一個維度中排序，然後再排序，並且保證在兩個維度上排序。 – 2013-02-28 03:47:20

這被稱爲「穩定排序」，而不是二維排序。 – 2013-02-28 05:13:10

他說泡泡排序（上）2D陣列。但是，是的，如果相同的元素保持相同的順序，則排序是穩定的。 – 2013-02-28 05:26:18

至少從你的描述，你只關心在PRI值進行排序，但希望負值後，積極的來（但積極的是按順序）。

這樣做的一個簡單方法是在進行比較之前將PRI值轉換爲無符號值。當轉換爲無符號時，負值將以2爲模2 ^N -1減少，因此（例如）-1將轉換爲UINT_MAX（更重要的是，所有負數將轉換爲無符號數大於任何開始的無符號數一個有號的正號）。

typedef struct { 
    int PID; 
    int PRI; 
} proc; 

int cmp(void const *a, void const *b) { 
    proc const *aa = (proc const *)a; 
    proc const *bb = (proc const *)b; 

    if ((unsigned)(bb->PRI) < (unsigned)(aa->PRI)) 
     return -1; 
    if ((unsigned)(aa->PRI) < (unsigned)(bb->PRI)) 
     return 1; 
    return 0; 
}

最後，而不是返回僅基於PRI值的平等0，你也可能要添加的PID的比較，所以項目將等於PRI值將由PID進行排序。我現在已經拋棄了這一點，因爲你沒有說你真的需要/想要它（並且它使得代碼更長，並且可能更難理解，特別是如果你不期望它在那裏）。

編輯：如果不清楚，這個比較函數打算與qsort一起使用，並且（假設您正確地進行比較），不需要穩定的排序。如果您決定首先在一個字段上排序（幾乎總是較慢），然後在第二個字段上執行第二個（單獨）排序，而不是在單個比較中比較所有相關字段，則只需要穩定排序。

來源

2013-02-28 05:24:15

您可以按降序對PRI上的數組進行排序。或者，而不是使用-1，則可以定義無效PRI是這樣的：

const int INVALID_PRI = INT_MAX;

而且在PRI列中的數組進行排序。

來源

2013-02-28 06:13:49 perreal

Bubble Sort 2D Array

回答

相關問題