c - 将项目移动到数组的前面

Question

我在一个数组的中心有一些项目，我想将它们移到这个数组的前面。例如:

array[8] = {10, 38, 38, 0, 8, 39, 10, 22}

我有一个索引数组

index[6] = {0, 3, 4, 6, 7, 1}

我想将这 6 项移动到数组的前面

result[8] = {10, 0, 8, 10, 22, 38, 38, 39}

其实顺序并不重要，只要确保索引在索引数组中的项总是在索引不在索引数组中的项之前即可。

谁能给我一个快速算法？实际上这是 KNN 问题的第一步，数据数组可能非常大。该算法应尽可能快地运行，并且所需的额外空间应尽可能小。如果你能给我 CUDA 实现就更好了。

更新:与数据数组相比，索引数组的大小非常小。就我而言，它只有大约 200。

更新:请注意数据数组的大小可能非常非常大!它达到 1M、10M 甚至更高(数据数组加载到非常有限的 GPU 内存)。任何算法都需要一个与数据数组具有相同大小的临时数组是 Not Acceptable 。

Answer 1

对index 数组进行递增排序，这一步将确保我们不会进行任何不必要的交换。

从0开始到n - 1(n为数组index的长度)，将数组中的第ith<​​元素与index[i]th交换 元素。

伪代码

sort(index);

 for(int i = 0; i < index.length; i++){
     swap(array, i , index[i]);
 }

如果你不想排序 index，我们总能找到index数组中不在第数组的开头。 (因为索引的大小很小)

使用 bool 值 used 来标记数组 index 中的哪个位置已经放在正确的位置。

伪代码:

bool []used = //

 for(int i = 0; i < index.length; i++){
     int nxt = -1;
     for(int j = 0; j < index.length; j++){
        if(!used[j]){
           if(nxt == -1 || index[j] < index[nxt]){
              nxt = j;
           }
        }
     }
     used[nxt] = true;
     swap(array, i, nxt);
 }