使用引用数组和交换函数在JavaScript中对数组进行排序

Question

在我编写的一些实际代码中，我似乎遇到了一个基本上是leetcode的问题。我的问题是，我需要使用索引的引用数组和交换函数对数组进行排序。

了解这个问题的来龙去脉可能会有所帮助。这是一个简化的、孤立的版本，当我试图通过ExtendScript在Adobe Illustrator中根据对象位置对层进行排序时，我会遇到这种情况。这就是为什么交换是必要的，这就是为什么有一个引用数组而不是仅仅使用.sort()函数。

arrayToBeSorted包含我试图排序的实际数据。referenceArray是arrayToBeSorted的索引的已排序列表。该referenceArray通过引用arrayToBeSorted中的项目的索引来描述arrayToBeSorted中的项目应该以什么顺序结束。

设置示例1:

// index              0      1       2       3       4      5                   
arrayToBeSorted = [ "six", "four", "one", "three", "two", "five" ]
referenceArray  = [   2,     4,      3,      1,      5,     0    ]
function swapItems(a, b) {
var temp = arrayToBeSorted[a];
arrayToBeSorted[a] = arrayToBeSorted[b];
arrayToBeSorted[b] = temp;
}
// desired outcome:
algorithmToSortArray(arrayToBeSorted, referenceArray)
// should return this: 
[
"one",   // was arrayToBeSorted[2]
"two",   // was arrayToBeSorted[4]
"three", // was arrayToBeSorted[3]
"four",  // was arrayToBeSorted[1]
"five",  // was arrayToBeSorted[5]
"six"    // was arrayToBeSorted[0]
]

设置示例2:

// index              0       1       2       3        4         5                   
arrayToBeSorted = [ "red", "green", "blue", "pink", "purple", "orange" ]
referenceArray  = [   5,      1,      4,      2,       0,        3     ]
function swapItems(a, b) {
var temp = arrayToBeSorted[a];
arrayToBeSorted[a] = arrayToBeSorted[b];
arrayToBeSorted[b] = temp;
}
// desired outcome:
algorithmToSortArray(arrayToBeSorted, referenceArray)
// should return this: 
[
"orange",  // was arrayToBeSorted[5]
"green",   // was arrayToBeSorted[1]
"purple",  // was arrayToBeSorted[4]
"blue",    // was arrayToBeSorted[2]
"red",     // was arrayToBeSorted[0]
"pink"     // was arrayToBeSorted[3]
]

解决方案限制：

该解决方案应仅使用交换功能在arrayToBeSorted中移动项目，并且最好针对尽可能少的交换次数进行优化。

编写algorithmToSortArray()的最佳方式是什么

Answer 1

这个版本相当简单：

const swap = (xs, i, j) => 
[xs [j], xs [i]] = [xs [i], xs [j]]
const refSort = (vals, refs) => {
const indices = Array .from (vals, (_, i) => i)
refs .forEach ((r, i) => {
const j = indices .indexOf (r)
swap (indices, i, j)
swap (vals, i, j)
})
return vals
}
console .log (
refSort (["six", "four", "one", "three", "two", "five"], [2, 4, 3, 1, 5, 0])
)
console .log (
refSort (["red", "green", "blue", "pink", "purple", "orange"], [5, 1, 4, 2, 0, 3])
)

.as-console-wrapper {max-height: 100% !important; top: 0}

我们同时对索引[0, 1, 2, ..., length]和我们的值进行重新排序，方法是基于引用索引，在两者上使用swap将我们的每个引用放置到位。有n掉期，如果它们过于昂贵，我们可以用去除无用的掉期

refs .forEach ((r, i) => {
const j = indices .indexOf (r)
if (i !== j) {
swap (indices, i, j)
swap (vals, i, j)
}
})

我认为这必须是最低限度的，尽管我们在任何地方都进行双重互换。

这不会进行错误检查。如果refs.length与vals.length不同，则可能会失败。

我不清楚这种简单的方法是否会扩展到你真正的问题，但如果不是，它可能会成为一个基础。在这种情况下，您可能会用一个更真实的例子来打开一个新问题。(也许一些改变了的值穿插着其他值，尽管我想上面的固定点——比如"绿色"——可能足以证明它应该有效。我只是不清楚。(

Answer 2

我提出了另一个解决方案，它只使用swapItems方法来更新arrayToBeSorted。我敢肯定，通过单独存储每个数字的位置变化，而不是每个"数字"的交换，可以做得更简单；循环；但现在已经很晚了，这一次很有效，所以我希望这对你有足够的帮助。

function algorithmToSortArray(arrayToBeSorted, referenceArray) {
const changeHistory = []
for(let i = 0; i < referenceArray.length; i++) {
number = referenceArray[i]
for(let j = 0; j < changeHistory.length; j++) {
if(changeHistory[j][0] === number) {
number = changeHistory[j][1]
} else if (changeHistory[j][1] === number) {
number = changeHistory[j][0]
}
}
if (i !== number) {  // this avoid some unnecessary swaps
swapItems(i, number)
}
changeHistory[i] = [i, number]
}
return arrayToBeSorted
}