风和日丽 2019-07-01
插入排序:
var a = [1,7,4,2,17,13,9]
function insertionSort(arr){
arr.map((d,index)=>{ let i = index while(d<arr[i-1]&&i-1>0){ [arr[i-1],arr[i]]=[arr[i],arr[i-1]] i-- } })
}
insertionSort(a)
归并排序(非hack)
function merge (arr,l,m,r){
var left = [] var right = [] for (let i =l;i<m;i++){ // console.log(i) left.push(arr[i]) } for(let j = m;j<=r;j++){ right.push(arr[j]) // console.log(j) } left.push(Infinity) right.push(Infinity) console.log(left,right) var i =0 var j =0 for(let k =l;k<r+1;k++){ if(left[i]<right[j]){ arr[k]=left[i] i++ }else{ arr[k]=right[j] j++ } }
}
function mergeSort(arr,l,r){
if(r>l){ var m=Math.ceil((l+r)/2) // console.log(m) mergeSort(arr,l,m-1) mergeSort(arr,m,r) merge(arr,l,m,r) }
}
归并排序(酷炫简单)
function merge(left, right) {
var tmp = []; while (left.length && right.length) { if (left[0] < right[0]) tmp.push(left.shift()); else tmp.push(right.shift()); } return tmp.concat(left, right);
}
function mergeSort(a) {
if (a.length === 1) return a; var mid = ~~(a.length / 2) , left = a.slice(0, mid) , right = a.slice(mid); return merge(mergeSort(left), mergeSort(right));
}
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。