相关疑难解决方法(0)

我正在研究一个整数序列,它没有相同的数字(不失一般性,让我们假设序列是一个排列1,2,...,n)到它的自然递增顺序(即1,2,...,n).我正在考虑直接交换元素(无论元素的位置如何;换句话说,交换对任何两个元素都有效),交换次数最少(以下可能是一个可行的解决方案):

交换两个元素的约束条件是应将其中一个或两个交换到正确的位置.直到每个元素都放在正确的位置.

但我不知道如何在数学上证明上述解决方案是否是最优的.有人可以帮忙吗？

我们有一个未分类的N个数字序列(1,2,3,4,... N).我们可以通过按特定顺序交换相邻元素来对整个序列进行排序.给定序列,如何计算对序列进行排序所需的最小可能交换.

例如,考虑序列{4,2,5,3,1}.

对此进行排序的最佳方法是按以下顺序使用7次交换

1. 交换3,1:{4,2,5,1,3}
2. 交换5,1:{4,2,1,5,3}
3. 交换4,2:{2,4,1,5,3}
4. 交换4,1:{2,1,4,5,3}
5. 交换2,1:{1,2,4,5,3}
6. 交换5,3:{1,2,4,3,5}
7. 交换3,4:{1,2,3,4,5}

一个贪婪的算法并没有证明是富有成效的.一个反例很容易构建.接近解决方案的下一个明显选择是动态编程.

假设我们有一个未排序的序列:{A1,A2,... Ai,A(i + 1),...,An}.我们知道对序列{Ai,A(i + 1),...,An}进行排序所需的最小交换次数是Min [Ai,A(i + 1),...,An}.问题是找到Min [A(i-1),Ai,...,An].

好吧,我想到的第一个想法就是添加将A(i-1)放在已经排序的序列{Ai,...,An}中的正确位置所需的步骤数.这是有效的:问题中给出的例子已经使用完全相同的方法解决了.

但我无法证明这个解决方案的有效性.这种情况经常发生在我身上.当我认为我已经解决了问题时,我能做的最好的就是获得一个"直观"的证据.我在高中并且没有正确的算法训练.我纯粹出于兴趣而这样做.

是否有严格的数学符号表明这个问题可以转化为正式的证明？这种符号可以扩展到其他问题吗？怎么样？如果能够以高中生可以理解的形式呈现,我将不胜感激.

请问您能告诉我在JavaScript中实现冒泡排序算法有什么问题吗？

for (var i=1; i<records.length; i++){
        for (var j=records.length; j<1; j--){
            if (parseInt(records[i-1]) < parseInt(records[i])){
                var temp = records[i-1];
                records[i-1] = records[i]
                records[i] = temp;
            }   
        }    
    }