冒泡排序和快速排序-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

冒泡排序和快速排序

简介: 冒泡排序:比较次数(n+1)*n/2,时间复杂度为O(n2) function bubblesort(arr){ var temp; for(var i=0;ii;j--){ if(arr[j-1]>arr[j]){ ...

冒泡排序:比较次数(n+1)*n/2,时间复杂度为O(n2)

function bubblesort(arr){
    var temp;
    for(var i=0;i<arr.length-1;i++){
        for(var j = arr.length-1;j>i;j--){
            if(arr[j-1]>arr[j]){
                temp = arr[j-1];
                arr[j-1] = arr[j];
                arr[j]=temp;
            }
        }
    }
}
            
var arr = [51,33,62,96,87,17,28,51];
            
bubblesort(arr);



快速排序时间复杂度为O(nlog2n)

function partition(arr,left,right){
    var baseNum = arr[left];
    while(left<right){
        while(left<right&& arr[right]>=baseNum){
            right = right -1;
                        
        }
        arr[left] = arr[right];
        while(left<right && arr[left]<=baseNum){
            left = left + 1;
        }
        arr[right] = arr[left];
    }
    arr[left] = baseNum;
    return left;
}
            
function quicksort(arr,left,right){
    if(left<right){
        var i = partition(arr, left, right);
        quicksort(arr, left, i - 1);
        quicksort(arr, i + 1, right);
    }
}
            
var arr = [51,33,62,96,87,17,28,51];
            
quicksort(arr);

 

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: