最近面试可能会问这些
1,插入排序
function sort(elements){ var res =[elements[0]]; for (var i = 0; i < elements.length; i++) { one(res,elements[i]); }; return res; } function one(arr,x){ var len = arr.length; var temp = false; for (var i = 0; i < len; i++) { if(arr[i]>=x){ for (var j = len; j >i; j--) { arr[j]=arr[j-1]; }; arr[i]=x; temp = true; break; } }; !temp&&arr.push(x); return arr; }
简单来说就是插入一个数,在结果里找他插入的位置。位置怎么找呢,比如我要插入一个值,看一下哪个值比它大,那就插入到这个比他大的值的前面。遍历一下数组,往后诺位置。
2.冒泡排序
function sort(arr){ for(var i=0;i<arr.length-1;i++){ for(var j=0;j<arr.length-i-1;j++){ if(arr[j]>arr[j+1]){ var swap=arr[j]; arr[j]=arr[j+1]; arr[j+1]=swap; } } } }
3.快速排序
var quickSort = function(arr) { if (arr.length <= 1) { return arr; } var pivotIndex = Math.floor(arr.length / 2); var pivot = arr.splice(pivotIndex, 1)[0]; var left = []; var right = []; for (var i = 0; i < arr.length; i++){ if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return quickSort(left).concat([pivot], quickSort(right)); };
4希尔排序
function shellSort(arr){ var N=arr.length; var h=1; while(h<N/3){ console.log(h); h=3*h+1;//设置间隔 } while(h>=1){ for(var i=h; i<N; i++){ for(j=i; j>=h && arr[j]<arr[j-h]; j-=h){ swap(arr, j, j-h); console.log(arr); } } h=(h-1)/3; } } function swap(array, i, j){//两个数调换 var temp =array[j]; array[j]=array[i]; array[i]=temp; }
5.归并排序
function merge(left, right) { var re = []; while(left.length > 0 && right.length > 0) { if(left[0] < right[0]) { re.push(left.shift()); } else { re.push(right.shift()); } } /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */ return re.concat(left).concat(right); } function mergeSort(array) { if(array.length == 1) return array; /* 首先将无序数组划分为两个数组 */ var mid = Math.floor(array.length / 2); var left = array.slice(0, mid); var right = array.slice(mid); /* 递归分别对左右两部分数组进行排序合并 */ return merge(mergeSort(left), mergeSort(right)); } mergeSort(a);