通过在原始列表中移动，将一个唯一列表重新排序到另一个列表-解网

问：

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

输入：

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

输出：

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

items 和 sampleItems 中的项集相等。

重新排序应通过移动原始列表（项目）来执行。

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

因此，项目列表在重新排序的所有期间都保留了其唯一性。

该算法应尽可能高效，不创建额外的数据结构（如字典），并且具有最少的移动量和最小的复杂性。

蛮力方法是按新索引对气泡进行排序。但它需要创建字典（键：item，值：新索引）或示例列表（sampleItems）上的大量枚举。我正在寻找更有效的东西。

我尝试了以下算法（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 毫秒内完成

列表算法排序与语言无关的唯一

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
	}
}

在 533 毫秒内完成

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

上一个：对两个数组进行排序的时间复杂度

下一个：对变化数组中的倒置进行计数

通过在原始列表中移动，将一个唯一列表重新排序到另一个列表

Reorder a unique list to another by movings in the original list

评论