0

我很好奇是否有（肯定有，但我不知道要寻找什么）某种智能排序算法。

智能排序算法是什么意思？让我们考虑一个例子：

我在表中排序了 5 个数字：

1, 2, 3, 4, 5

然后我交换第二和第四，所以我有：

1, 4, 3, 2, 5

作为第二步，我交换了第 5 步和第 2 步，所以最终结果是：

1, 5, 3, 2, 4

我对该算法的期望是将最终集作为输入（1、5、3、2、4），因此我想获得应该交换第 2 项和第 5 项然后交换第 2 项和第 4 项的信息列表排序。

我正在考虑使用排序网络：我可以为一定大小的数据生成所有需要的比较和交换指令，然后返回那些将为输入数据完成的交换，但也许还有其他方法？

我应该寻找什么？

4

2 回答 2

2

找到最小交换的数量对于排序通常并不重要（交换可以在指针上完成），但就其本身而言，这是一个众所周知的问题。

看看这个问题： 计算将一种排列转换为另一种排列所需的相邻交换

或者将您的研究指向编辑距离。

于 2013-08-31T11:20:13.600 回答
1

我认为这里的问题是数据的实际交换非常昂贵，但比较相对便宜。

我将首先使用常规排序算法来找出数组中每个元素的位置。有很多算法可以做到这一点，例如快速排序或只是冒泡排序或插入排序。

现在我们知道每个元素应该去哪里，从这里开始，我们可以找到最佳的交换序列，将原始数据放到排序位置。

伪代码示例：

compare(proxy1, proxy2)
  return compare(proxy1.data, proxy2.data)

smartSort(unsorted)
  swaps = []
  count = size(unsorted)
  // create a proxy for all elements
  proxiesOrig = [ new proxy(data) | for unsorted as data ]
  // and make a copy which we are going to sort
  proxiesSort = shallowCopy(proxiesOrig)
  sort(proxiesOrig)  // Do a regular sort here, using the compare function above
  // now note the location of each target
  // because we made a shallow copy, the location will also be marked in the
  // proxiesOrig list
  for i = 1 .. count
    proxiesSort[i].location = i
  // Now the proxiesOrig is the unsorted list
  // with location information to where everything needs to go
  for i = 1 .. count
    while (proxiesOrig[i].location <> i)
      // swap the proxy on location i with the one to where i needs to go
      swap(proxiesOrig, i, proxiesOrig[i].location)
      // and record it
      swaps.add(i, proxiesOrig[i].location)
  return swaps
于 2013-08-31T11:19:19.690 回答