mergesort算法

首先讓我說這是hw，所以我正在尋找更多的建議，而不是一個答案。我將編寫一個程序來讀取輸入序列，然後生成一個鏈接數組，以按升序排列值。mergesort算法

輸入文件的第一行是序列的長度（n），其餘的n行中的每一行都是非負整數。輸出的第一行指示最小輸入值的下標。每個剩餘的輸出行都是由下標組成的三元組以及相應的輸入序列和鏈接值。

（該鏈接值沒有初始化遞歸排序開始之前，每個鏈路將被初始化爲-1時，其序列值被放置在一個單一的元素列表中的遞歸樹的底部）

輸出看起來是像這樣：

在哪裏（我認爲）的最後一列是標，該中心是在無序數組，最後一列是鏈接值。我已經有了mergeSort的代碼，並且瞭解它是如何工作的，我只是感到困惑以及鏈接如何實現。

來源

2013-02-09 bardockyo

你是指什麼*鏈接*？ – 2013-02-09 23:07:45

不是100％，但它看起來像我將有一個單獨的「鏈接」元素數組，從-1開始，在mergesort期間的某個地方，他們從原始數組中分配一個int。整個想法對我來說非常混亂。 – bardockyo 2013-02-09 23:19:31

這是一種排序數據的非常規方法。即使我們假設主陣列的元素太大而無法移動，並且_links_允許我們將事物連接在一起，但鏈接值的工作原理並不清楚。 – 2013-02-09 23:31:08

我用結構向量來保存每行的三個值。

的主要步驟是：

初始化索引和由值
從輸入讀出的值
排序矢量確定的鏈接
排序（背面）由索引的矢量

這裏是代碼示意圖：

struct Element { 
    int index; 
    int value; 
    int nextIndex; // link 
} 

Element V[N + 1]; 
int StartIndex; 

V[i].index = i; 
V[i].value = read_from_input; 

sort(V); // by value 

startIndex = V[0].index; 
V[i].nextIndex = V[i + 1].index; 
V[N].nextIndex = -1; 

sort(V); // by index

來源

2013-02-10 15:06:44 Spatarel

謝謝您的回覆。我得到它的大部分，但是N假設代表什麼？ – bardockyo 2013-02-10 22:20:03

N是序列中元素的數量減1。在你的例子中，它是7。 – Spatarel 2013-02-11 01:29:31

回答

相關問題