在使用合併排序時保留原始索引c

我試圖用合併排序算法對列表進行排序，同時保留它的原始索引。我被告知，直接的解決方案是使用一個索引數組（顯然它會被初始化爲0 1 2 3 ...），並在合併排序中對其進行更改，因爲我更改了原始數據中的對應值陣列。事情是，我找不到一種方法來使它工作，因爲合併排序不使用原始數組的索引，而是原始數組分割的小數組的索引。我想我在這裏丟失了一些東西......我到目前爲止考慮的解決方案是將索引數組視爲原始數組，我的意思是將其分割成更小的數組，爲新索引聲明一個「helperIndexArray」，調用合併與這些變量等......但它似乎真的不夠高效。沒有更好的方法嗎？我很感激任何提示，謝謝！在使用合併排序時保留原始索引c

void internalMsort(int array[], int size, int helperArray[], int index[]) { 
    int left = size/2, right = size - left; 
    if (size < 2) 
     return; 
    internalMsort(array, left, helperArray); 
    internalMsort(array + left, right, helperArray); 
    merge(array, left, array + left, right, helperArray, index); 
    memCpy(array, helperArray, size); 
} 

void merge(int a[], int na, int b[], int nb, int c[], index[]) { 
int ia, ib, ic; 
    for(ia = ib = ic = 0; (ia < na) && (ib < nb); ic++) 
    { 
     if(a[ia] < b[ib]) { 
      c[ic] = a[ia]; 
      ia++; 
      // here I was trying to swap index[ic] with index[ia] but it didn't work 
     } 
     else { 
      c[ic] = b[ib]; 
      ib++; 
     } 
    } 
    for(;ia < na; ia++, ic++){ c[ic] = a[ia]; } 
    for(;ib < nb; ib++, ic++) { c[ic] = b[ib]; } 
}

來源

2016-01-19 Anna

定義新的類型，稱爲元組：

typedef struct 
{ 
    int value; 
    size_t index; 
} tuple;

創建的元組的陣列，其值填充，並設置在索引順序，從0到大小-1。

然後使用成員值對數組進行排序，並忽略成員索引。

生成的數組將被排序，其元素將包含成員索引中的原始索引。

來源

2016-01-19 08:19:32 2501

這是很容易的（而不是具體到mergesort）。只要創建的

struct element_and_index_st  { 
    int element; 
    size_t original_index; // could be an `int` or an `unsigned` 
};

一個數組和排序數組，提供一個比較功能只比較element領域。

^{（除非你的陣列是巨大的，實際上你可以有original_index一些int或當前的臺式機或者筆記本的一些unsigned，其中int■找至少32位）}

但你不要告訴爲什麼你需要原始索引，你將如何將它們還給你的調用者？

也許你只是想要一些stable sort？

來源

2016-01-19 08:20:48

首先根據數組對索引進行排序（比較array [index [ia]] < = array [index [ic]]來對index []進行排序，使用輔助數組作爲索引的第二個數組，數組和索引是整數，可以使用幫助程序數組對索引排序後的數組進行排序：

for(i = 0; i < size; i++) 
     helperArray = array[index[i]]; 
    for(i = 0; i < size; i++) 
     array[i] = helperArray[i];

來源

2016-01-21 04:33:39 rcgldr

在使用合併排序時保留原始索引c

回答

相關問題