成都web前端培训
成都达内金融街中心

18328393564

热门课程

web前端-js冒泡排序

  • 时间:2016-10-13 13:31
  • 发布:达内杨老师
  • 来源:达内

时间复杂度:算法的时间复杂度是一个函数,描述了算法的运行时间。时间复杂度越低,效率越高。

自我理解:一个算法,运行了几次时间复杂度就为多少,如运行了n次,则时间复杂度为O(n)。

1.冒泡排序

解析:1.比较相邻的两个元素,如果前一个比后一个大,则交换位置。

2.第一轮的时候最后一个元素应该是最大的一个。

3.按照步骤一的方法进行相邻两个元素的比较,这个时候由于最后一个元素已经是最大的了,所以最后一个元素不用比较。

1 function sort(elements){

2 for(var i=0;i<elements.length-1;i++){

3  for(var j=0;j<elements.length-i-1;j++){

4   if(elements[j]>elements[j+1]){

5    var swap=elements[j];

6    elements[j]=elements[j+1];

7    elements[j+1]=swap;

8   }

9  }

10 }

11 }

12 

13 var elements = [3, 1, 5, 7, 2, 4, 9, 6, 10, 8];

14 console.log('before: ' + elements);

15 sort(elements);

16 console.log(' after: ' + elements);

2.快速排序

解析:快速排序是对冒泡排序的一种改进,第一趟排序时将数据分成两部分,一部分比另一部分的所有数据都要小。然后递归调用,在两边都实行快速排序。

function quickSort(elements) {

if (elements.length <= 1) { return elements; }

var pivotIndex = Math.floor(elements.length / 2);

var pivot = elements.splice(pivotIndex, 1)[0];

var left = [];

var right = [];

for (var i = 0; i < elements.length; i++){

if (elements[i] < pivot) {

left.push(elements[i]);

} else {

right.push(elements[i]);

}

}

return quickSort(left).concat([pivot], quickSort(right));

};

var elements=[5,6,2,1,3,8,7,1.2,5.5,4.5];

alert(quickSort(elements));

3.插入排序

解析:

(1)从第一个元素开始,该元素可以认为已经被排序

(2)取出下一个元素,在已经排序的元素序列中从后向前扫描

(3)如果该元素(已排序)大于新元素,将该元素移到下一位置

(4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

(5)将新元素插入到下一位置中

(6)重复步骤2

1 insertSort: function(elements) {

2

3    var i = 1,

4    j, step, key, len = elements.length;

5

6    for (; i < len; i++) {

7

8        step = j = i;

9        key = elements[j];

10

11        while (--j > -1) {

12            if (elements[j] > key) {

13                elements[j + 1] = elements[j];

14            } else {

15                break;

16            }

17        }

18

19        elements[j + 1] = key;

20    }

21

22    return elements;

23 }

2.二分查找

解析:二分查找,也为折半查找。首先要找到一个中间值,通过与中间值比较,大的放又,小的放在左边。再在两边中寻找中间值,持续以上操作,直到找到所在位置为止。

(1)递归方法

1 function binarySearch(data,item,start,end){

2    var end=end || data.length-1;

3    var start=start || 0;

4    var m=Math.floor((start+end)/2);

5    if(item==data[m]){

6        return m;

7    }else if(item<data[m]){

8        return binarySearch(data,item,start,m-1) //递归调用

9    }else{

10        return binarySearch(data,item,m+1,end);

11    }

12    return false;

13 }

14

15    var arr=[34,12,5,123,2,745,32,4];

16

17    binary(arr,5);

(2)非递归方法

1    function binarySearch(data, item){

2    var h = data.length - 1,

3        l = 0;

4    while(l <= h){

5        var m = Math.floor((h + l) / 2);

6        if(data[m] == item){

7            return m;

8        }

9        if(item > data[m]){

10            l = m + 1;

11        }else{

12            h = m - 1;

13        }

14    }

15  

16    return false;

17 }

18 var arr=[34,12,5,123,2,745,32,4];

19 binarySearch(arr,5);

上一篇:web前端-回到顶部按钮代码
下一篇:web前端-构造函数之intanceof
选择城市和中心
贵州省

广西省

海南省