C++中不修改原数组的结构体数组排序顺序实现方案

我来给你详细拆解这个需求的实现思路——核心是借助双向链表的prev/next指针构建有序序列，最后遍历链表给每个元素的pos字段赋值排序后的位置，全程不会改动原数组的元素存储位置，完全符合你的限制条件。

整体思路 #

因为不能修改原数组的元素位置，我们只能通过调整每个elemento节点的指针，把它们串联成一个有序的双向链表；之后再遍历这个有序链表，依次给每个节点的pos字段设置对应的排序后索引，这样就能在不移动原数组元素的前提下完成排序标记。

具体实现步骤&代码 #

假设这是某个类的成员逻辑，我们可以实现一个成员函数来完成这个操作：

1. 边界情况处理 #

如果有效元素数量_cont小于等于1，直接给每个元素的pos赋值即可，不需要排序：

if (_cont <= 1) {
    for (int i = 0; i < _cont; ++i) {
        _array[i].pos = i;
    }
    return;
}

2. 初始化有序链表（用哨兵节点简化边界） #

用一个哨兵节点来处理空链表的特殊情况，避免额外的判断逻辑：

elemento sentinel;
elemento* sorted_head = &sentinel;
sentinel.next = nullptr;
sentinel.prev = nullptr;

3. 遍历原数组，将元素插入有序链表 #

遍历所有有效元素，通过调整prev/next指针把每个元素插入到有序链表的对应位置（这里默认是升序排序，降序只需修改比较条件）：

for (int i = 0; i < _cont; ++i) {
    elemento* curr = &_array[i];
    // 重置当前元素的指针，避免旧数据干扰有序链表
    curr->prev = nullptr;
    curr->next = nullptr;

    // 找到当前元素应该插入的位置：找第一个值大于当前元素的节点的前驱
    elemento* prev_node = sorted_head;
    while (prev_node->next != nullptr && prev_node->next->value < curr->value) {
        prev_node = prev_node->next;
    }

    // 执行双向链表插入操作
    curr->next = prev_node->next;
    if (prev_node->next != nullptr) {
        prev_node->next->prev = curr;
    }
    curr->prev = prev_node;
    prev_node->next = curr;
}

4. 遍历有序链表，设置pos字段 #

从有序链表的第一个有效节点开始，依次给每个元素的pos赋值排序后的索引：

int current_pos = 0;
elemento* curr = sorted_head->next;
while (curr != nullptr && current_pos < _cont) {
    curr->pos = current_pos++;
    curr = curr->next;
}

完整函数代码 #

把上面的步骤整合起来，完整的成员函数如下：

template<typename T>
void YourClassName::sortByPos() {
    if (_cont <= 1) {
        for (int i = 0; i < _cont; ++i) {
            _array[i].pos = i;
        }
        return;
    }

    elemento sentinel;
    elemento* sorted_head = &sentinel;
    sentinel.next = nullptr;
    sentinel.prev = nullptr;

    for (int i = 0; i < _cont; ++i) {
        elemento* curr = &_array[i];
        curr->prev = nullptr;
        curr->next = nullptr;

        elemento* prev_node = sorted_head;
        while (prev_node->next != nullptr && prev_node->next->value < curr->value) {
            prev_node = prev_node->next;
        }

        curr->next = prev_node->next;
        if (prev_node->next != nullptr) {
            prev_node->next->prev = curr;
        }
        curr->prev = prev_node;
        prev_node->next = curr;
    }

    int current_pos = 0;
    elemento* curr = sorted_head->next;
    while (curr != nullptr && current_pos < _cont) {
        curr->pos = current_pos++;
        curr = curr->next;
    }
}

额外说明 #

• 排序规则调整：如果需要降序排序，只需要把插入时的比较条件prev_node->next->value < curr->value改成prev_node->next->value > curr->value即可。
• 性能优化：上面的实现是插入排序，时间复杂度为O(n²)，适合小数据量场景。如果你的数据量很大，想要O(n log n)的效率，可以先收集所有有效元素的指针到一个数组，用标准库的sort函数排序指针数组，再遍历给pos赋值（这个方法不需要用到prev/next指针，但同样满足不修改原数组的要求）：

  template<typename T>
  void YourClassName::sortByPosFast() {
      if (_cont <= 1) {
          for (int i = 0; i < _cont; ++i) {
              _array[i].pos = i;
          }
          return;
      }
  
      std::vector<elemento*> ptrs;
      ptrs.reserve(_cont);
      for (int i = 0; i < _cont; ++i) {
          ptrs.push_back(&_array[i]);
      }
  
      // 升序排序指针数组
      std::sort(ptrs.begin(), ptrs.end(), [](elemento* a, elemento* b) {
          return a->value < b->value;
      });
  
      // 给每个元素设置pos
      for (int i = 0; i < _cont; ++i) {
          ptrs[i]->pos = i;
      }
  }
  

内容的提问来源于stack exchange，提问作者Riccardo