冒泡排序最佳情况的时间复杂度

冒泡排序的时间复杂度O(n)

 1 var modifiedBubbleSort = function (array) {
 2     var length = array.length;
 3     var swap = function (index1, index2) {
 4         var aux = array[index1];
 5         array[index1] = array[index2];
 6         array[index2] = aux;
 7     };
 8     for (var i = 0; i < length; i++) {
 9         for (var j = 0; j < length - 1 - i; j++) { 
10             if (array[j] > array[j + 1]) {
11                 swap(j, j + 1);
12             }
13         }
14     }
15     return array;
16 };

这种实现方法很显然无论如何都会去比较，因此还是O(N^2)，但这是实现的不好导致的，事实上可以添加一个标志位就可以搞定这个问题：

 1 var modifiedBubbleSort = function (array) {
 2     var length = array.length;
 3     var swap = function (index1, index2) {
 4         var aux = array[index1];
 5         array[index1] = array[index2];
 6         array[index2] = aux;
 7     };
 8     for (var i = 0; i < length; i++) {
 9         var didSwap = false;
10         for (var j = 0; j < length - 1 - i; j++) { 
11             if (array[j] > array[j + 1]) {
12                 swap(j, j + 1);
13                 didSwap = true;
14             }
15         }
16         if(didSwap == false){
17             return array;
18         }   
19     }
20 };
21 var result = modifiedBubbleSort(arr);

冒泡排序最佳情况的时间复杂度

推荐阅读