javascript - 我的排序算法的时间复杂度应该是多少？

Question

昨天去面试了，

他让我写一个程序来对数组进行升序排序。

我写了一个程序如下，

var mySortOne = function(myArray){
    var num = 0,
        temp = 0, 
        isSwipe = false,
        counter = 0;    

    for(num = 0; num < myArray.length; num++){
        print((++counter)+" => "+myArray);
        if (((num+1) < myArray.length) && (myArray[num] > myArray[num+1])){
            temp = myArray[num+1];
            myArray[num + 1] = myArray[num];
            myArray[num] = temp;
            isSwipe = true; 
        }
        if(isSwipe){
            isSwipe = false;
            num = -1;
        }
    }

    print("\n FINAL "+myArray);
};

mySortOne([45,12,78,22,4]);

面试官不满意，他说“我不是要求最优解，但是你的排序算法最差n^2。”

于是我写了第二种方案，如下，

var mySortTwo = function(myArray){
    var num = 0,
        MAX = myArray.length,
        isSwipe = false,
        temp = 0,
        counter = 0;

    do{
        isSwipe = false;
        for(num = 0; num < MAX; num++){
            print((++counter)+" => "+myArray);
            if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){
                temp = myArray[num + 1];
                myArray[num + 1] = myArray[num];
                myArray[num] = temp;
                isSwipe = true;              
            }
        }
        MAX--;
    }while(isSwipe);

    print("\n FINAL "+myArray);
};

mySortTwo([45,12,78,22,4]);

但他还是不满意。

我有这两种算法的一些打印语句。

第一个算法的输出是

1 => 45,12,78,22,4
2 => 12,45,78,22,4
3 => 12,45,78,22,4
4 => 12,45,78,22,4
5 => 12,45,22,78,4
6 => 12,45,22,78,4
7 => 12,22,45,78,4
8 => 12,22,45,78,4
9 => 12,22,45,78,4
10 => 12,22,45,78,4
11 => 12,22,45,4,78
12 => 12,22,45,4,78
13 => 12,22,45,4,78
14 => 12,22,4,45,78
15 => 12,22,4,45,78
16 => 12,4,22,45,78
17 => 4,12,22,45,78
18 => 4,12,22,45,78
19 => 4,12,22,45,78
20 => 4,12,22,45,78
21 => 4,12,22,45,78

 FINAL 4,12,22,45,78

第二种算法的输出如下，

1 => 45,12,78,22,4
2 => 12,45,78,22,4
3 => 12,45,78,22,4
4 => 12,45,22,78,4
5 => 12,45,22,4,78
6 => 12,45,22,4,78
7 => 12,45,22,4,78
8 => 12,22,45,4,78
9 => 12,22,4,45,78
10 => 12,22,4,45,78
11 => 12,22,4,45,78
12 => 12,4,22,45,78
13 => 12,4,22,45,78
14 => 4,12,22,45,78
15 => 4,12,22,45,78

 FINAL 4,12,22,45,78

他说两者都迭代太多了。我们可以使用简单的冒泡排序得到更好的解决方案。

但我认为我的第二个解决方案是冒泡排序本身。

能否请您告诉我这两种算法的复杂度是多少，以及我如何改进第二个冒泡排序

Answer 1

两个你的算法都是Bubble sort ，因为您比较和交换相邻元素。我没有检查它们是否真的有效，但至少预期的逻辑看起来是正确的。

第一个，与外观相反，是打算是冒泡排序。 for 循环的次数不决定迭代的次数。参见 here有关使用单个循环的冒泡排序的示例。

但是，您的第一个实现看起来确实是 O(n^3)，因为您在每次交换后都重置了迭代变量。如果您坚持使用单个循环，我建议您循环直到 n^2 并消除您正在执行的重置，就像您在上一个链接中看到的那样。感谢Tali感谢您指出这一点。

您的第二个针对冒泡排序进行了很好的优化，但您可以做更多。请注意，在冒泡排序中，最佳元素(最大或最小)在运行内部循环后到达其最终位置。因此，对于下一次迭代，您只需要迭代到上一次迭代中最后一个交换的位置。

do{
    isSwipe = false;
    newMax = 0;
    for(num = 0; num < MAX; num++){
        print((++counter)+" => "+myArray);
        if(((num + 1) < MAX) && (myArray[num] > myArray[num+1])){
            temp = myArray[num + 1];
            myArray[num + 1] = myArray[num];
            myArray[num] = temp;
            isSwipe = true;              
            newMax = i + 1; ///////////////////// here //////////////////// 
         }
    }
    MAX = newMax;
    // no need for this anymore MAX--;
}while(isSwipe);

但它仍然是二次的。不过，这是您本可以进行的优化。

一个更高级的优化是Cocktail sort ，但这在最坏的情况下也是二次的。