通过移动原始列表，将一个独特的列表重新排序到另一个列表。

Question

我正在寻找一种在任何命令式编程语言中的算法，通过在原始列表中的移动，将一个唯一的列表重新排序到另一个列表。

输入：输入

items       = [a, b, c, d, e]
sampleItems = [b, c, e, d, a]

输出：

items   =     [b, c, e, d, a]

列表中的项目集 物品 和 样本项 是相等的。

重新排序应通过在原列表中移动(物品).

void Move(int oldIndex, int newIndex)
{
  Item item = items[oldIndex];
  items.RemoveAt(oldIndex);
  items.Insert(item, newIndex);
}

所以 物品 列表在重新排序的所有时期保存其唯一性。

算法应该尽可能的高效，不需要创建额外的数据结构，如字典，并且动量最小，复杂度最低。

蛮力的方法是按新的指数进行气泡排序。但它需要创建一个字典（key：项，value：新索引）或者在样本列表上进行无数次枚举(样本项). 我正在寻找更高效的方法。

我尝试了下面的算法(C#)，它工作正常，但效率不高，因为它创建了一个字典，而且复杂度为O(n^2)。处理10001个项目需要大约9秒。它很慢。

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp14
{
	class Program
	{
		static void Main(string[] args)
		{
			ObservableCollection<Item> items = new ObservableCollection<Item>();

			int count = 10001;

			for (int i = 0; i < count; i++)
			{
				items.Add(new Item(i));
			}

			Random random = new Random();			
			ObservableCollection<Item> sampleItems = new ObservableCollection<Item>(items.OrderBy(i => random.Next()));
			
			Stopwatch stopwatch = Stopwatch.StartNew();
			Dictionary<Item, int> oldIndeces = new Dictionary<Item, int>();
			for (int i = 0; i < count; i++)
			{
				oldIndeces.Add(items[i], i);
			}

			for (int i = 0; i < count; i++)
			{
				int oldIndex = oldIndeces[sampleItems[i]];
				items.Move(oldIndex, i);

				for (int j = 0; j < count; j++)
				{
					Item item = items[j];
					int oldIndex1 = oldIndeces[item];
					if (oldIndex1 <= oldIndex)
						oldIndeces[item] = oldIndex1 + 1;
				}
			}

			Debug.Assert(sampleItems.SequenceEqual(items));
			stopwatch.Stop();
			Console.WriteLine($"Done in {stopwatch.ElapsedMilliseconds}ms");
			Console.ReadLine();
		}
	}

	public class Item
	{
		public Item(int num)
		{
			Num = num;
		}

		private int Num { get; }

		#region Overrides of Object

		public override string ToString()
		{
			return Num.ToString();
		}

		#endregion
	}
}

输出：

9123毫秒完成

Answer 1

这里是一个没有字典的实现。

using System;
using System.Collections.ObjectModel;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp14
{
	class Program
	{
		static void Main(string[] args)
		{
			ObservableCollection<Item> items = new ObservableCollection<Item>();

			int count = 10001;

			for (int i = 0; i < count; i++)
			{
				items.Add(new Item(i));
			}

			Random random = new Random();			
			ObservableCollection<Item> sampleItems = new ObservableCollection<Item>(items.OrderBy(i => random.Next()));
			
			Stopwatch stopwatch = Stopwatch.StartNew();
			int oldIndex = 0;
			Item sampleItem;
			Item nextSampleItem = null;
			for (int i = 0; i < count; i++)
			{
				sampleItem = sampleItems[i];
				if (i < count - 1) nextSampleItem = sampleItems[i + 1];

				if (i == 0)
				{
					for (int j = 0; j < count; j++)
					{
						if (sampleItem == items[j])
							oldIndex = j;
					}
				}

				items.Move(oldIndex, i);

				for (int j = i + 1; j < count; j++)
				{
					if (items[j] == nextSampleItem)
					{
						oldIndex = j;
					}
				}
			}

			Debug.Assert(sampleItems.SequenceEqual(items));
			stopwatch.Stop();
			Console.WriteLine($"Done in {stopwatch.ElapsedMilliseconds}ms");
			Console.ReadLine();
		}
	}

	public class Item
	{
		public Item(int num)
		{
			Num = num;
		}

		private int Num { get; }

		#region Overrides of Object

		public override string ToString()
		{
			return Num.ToString();
		}

		#endregion
	}
}

533ms内完成

这个实现也适用于非唯一列表。