交换排序(冒泡排序和快速排序)
1.冒泡排序在冒泡排序中，第 1 轮需要比较 n -1 次，第 2 轮需要比较 n -2 次……第 n -1 轮需要比较 1 次。因此，总的比较次数为 (n -1) +(n -2) +…+1 ≈ n^2/2。这个比较次数恒定为该数值，和输入数据的排列顺序无关。
//从左到右冒泡，大数右移，排好序的元素在右边
var arr=[1,3,4,5,2,7,9];
for(var i=0;i<arr.length;i++){
for(var j=0;j<arr.length-1-i;j++){//这里比较n-1次，然后n-2,最后0
if(arr[j]>arr[j+1]){
var temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
} 初始i=0,不管最大的数在哪个位置，都需要各相邻数之间两两比较n-1次，才能把最大的数送到右边去，未排好序的元素则剩下从左往右数n-1个，则需要两两比较n-2次，循环往复，直到最后比较次数为0 2.快速排序：快速排序算法首先会在序列中随机选择一个基准值（pivot），然后将除了基准值以外的数分为“比基准值小的数”和“比基准值大的数”这两个类别，再将其排列成以下形式。
function MySort( arr ) {
// write code here
if(arr.length<=1){
return arr;
}//如果数组的长度小于1，则不用排序直接返回
var index=Math.floor(arr.length/2);//取中位数索引
var left=[];//构建左边的空数组
var right=[];//构建右边的空数组
var middum=arr.splice(index,1)[0];//返回中位数索引的数值
for(var i=0;i<arr.length;i++){
if(arr[i]<middum){
left.push(arr[i]);
}else{
right.push(arr[i]);
}
}
return MySort(left).concat(middum,MySort(right));//一个递归药到病除
}
投递旷视等公司10个岗位 >