用於排序三角形列表的最小交換次數

讓L = list of S's其中S = list of lengths of sides of a triangle。用於排序三角形列表的最小交換次數

然後，我需要找到對列表進行排序L.

列表L被說成是分類需要交換的最小數目：

其中0 <= i <= 2

注：兩種類型的交換操作可以做到：

任何有效的算法時間複雜度方面找到排序列表L 儘可能需要交換的最小數目？

編輯：

正如@Mbo正確地指出，它並不總是能夠如此排序這樣的列表L.，這將是巨大的，如果有人提供了一個算法來檢查，如果列表L可以排序，然後如果可能的話進行排序。

2014-12-19 Coding man

看起來1）和2）條件是相似的。你會指定更好嗎？ – MBo 2014-12-19 08:30:20

@MBo 1）我正在討論S1，S2，...，S的Sj列表中的元素。如果S1 = [a，b，c]，那麼a，b，c應該是非decr順序。 2）我在談論每個Sj列表的相應元素，例如S1 [0]，S2 [0]，S3 [0] ...應該按照非遞減順序排序。 – 2014-12-19 08:40:14

在一般情況下是不可能的。考慮（4,7,10）和（5,6,7） – MBo 2014-12-19 08:47:02

也許我誤解了，但在我看來，你必須對每個S中的3個元素進行排序。一旦完成，它只是按照列表{S0 [0] ，S1 [0] ...}，然後檢查序列{S0 [1]，S1 [1] .....}，{S0 [2]，S1 [2] ..}是否按升序排列。如果你有n個三角形，漸近最壞情況下的複雜度就是O（n）

2014-12-20 02:18:02 McDowells

這不回答這個問題。他不問如何進行排序，而是要求計算給定特定三角形排列所需的最小交換次數。因此，需要多少次交換才能對各個三角形的邊進行排序，然後對三角形列表進行排序需要多少次交換。也就是說，理想的最小交易次數是完美的排序算法。 – 2014-12-20 04:08:41

回答