插入排序的數組隊列

我正在處理排序的隊列，如優先級隊列。我已經做了一個列表，它已經很好。現在我想用數組來完成它。但是我有一點邏輯性問題，添加一個新元素並將其插入排序後的數組中。插入排序的數組隊列

最終的輸出應該是這樣的：
優先順序：5值：x
優先級：4值：異
....（等）
所以元件與所述最高Priorithy應該在索引= 0.
我只是不知道（是的，我知道它真的只是切換它，但我不能這樣做：/）如何做到這一點...

我已經嘗試了一些東西，但我卡住了......：/可以請任何人幫幫我？

這裏是我的代碼：

public class Queue { 

private QueueElem[] a; 

public Queue(int capacity) 
{ 
    QueueElem[] tempQueue = new QueueElem[capacity]; 
    a= tempQueue; 
} 

public void enqueue(int p, String v) 
{ 
    QueueElem neu = new QueueElem(p,v); 
    int i=0; 

     while(i<a.length) 
     { 
      if (a[i] == null) 
      { 
       a[i] = neu; 
       break; 
      } 
      i++; 
     } 
} 

public void writeQueue() 
{ 
    int i=0; 
    while((i< a.length) && (a[i] != null)) 
    { 
     System.out.println("Priority: " + a[i].priority + " Value: " + a[i].value); 
     i++; 
    } 
} 

public static void main(String args[]) 
{ 
    Queue neu = new Queue(10); 
    neu.enqueue(4,"iso"); 
    neu.enqueue(2,"abc"); 
    neu.enqueue(5,"x"); 
    neu.enqueue(1,"abc"); 
    neu.enqueue(4,"bap"); 
    neu.enqueue(2,"xvf"); 
    neu.enqueue(4,"buep"); 
} 
}//end class Queue 


class QueueElem { 
int priority; 
String value = new String(); 

public QueueElem(){ } 

public QueueElem(int p, String v) 
{ 
    this.priority = p; 
    this.value = v; 
} 

public int getPrio() 
{ 
    return this.priority; 
} 

public String getValue() 
{ 
    return this.value; 
} 
}

來源

2013-05-16 MikroByte

這將是更好，如果你解釋你的陣列作爲最大堆。這是實施優先隊列的典型方式。

如果你想爲你的優先級隊列維護一個已排序的數組，你需要的是執行insertion sort（你有一個沒有排序的數組，你有一個空的數組，你只需添加到，同時保持排序順序）。每當你插入一個新的元素時，你將遍歷整個數組以找到正確的點，然後將它插入到那裏，然後將當前在該點處的元素和其後的所有元素都移動一次。請注意，這不像使用堆實現這種性能，因爲最壞的情況下，每次插入時都會有O(n)的性能，而對於堆，則有O(logn)。

來源

2013-05-16 19:21:09

我不明白爲什麼有人會想要使用原始數組......特別是現在你已經用List實現它。

如果您想了解如何在原始數組中插入元素，請查看ArrayList的代碼，因爲它下方使用原始數組。您必須將所有元素移動到插入點的右側，您可以將其複製到循環中，或使用System.arraycopy（）。但最麻煩的部分是，你可能不得不創建一個新的數組，因爲當你添加一個元素時，數組的大小增加1（這取決於你使用的數組的大小是否與你的數據的大小完全相同，如ArrayList中所做的那樣）。

來源

2013-05-16 20:04:48 toto2

插入排序的數組隊列

回答

相關問題