使用引用数组和交换函数对JavaScript中的数组进行排序
在我正在编写的一些实际代码中，我似乎遇到了一个基本上是leetcode的问题。我的问题是，我需要使用索引的引用数组和交换函数对数组进行排序。
了解这个问题的背景可能会有所帮助。这是一个简化的、孤立的版本，当我试图想出一个脚本来通过ExtendScript按照Adobe中的对象位置对层进行排序时，我将面临这个问题。这就是为什么交换是必要的，这也是为什么存在一个引用数组，而不是仅仅使用.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()__的最好方法是什么？
回答 2
Stack Overflow用户
发布于 2022-08-17 14:27:13
这个版本相当简单：
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不同，这可能会失败。
我不清楚这个简单的方法是否会扩展到真正的问题，但如果不是，它可能作为基础。在这种情况下，您可能会用一个更真实的例子来打开一个新问题。(也许有些改变的价值观与其他单独存在，尽管我想上面的不动点-例如“绿色”-可能足以证明它应该有效。我只是不清楚。)
Stack Overflow用户
发布于 2022-08-16 09:37:39
我想出了另一个解决方案，它只使用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
}https://stackoverflow.com/questions/73356172
复制相似问题
腾讯云开发者
