JS简单实现排序算法

function merge(left, right) { var result = []; while(left.length > 0 && right.
length > 0) { if(left[0] < right[0]) { result.push(left.shift()); } else {
result.push(right.shift()); } } return result; } function mergeSort(arr){ if(
arr.length==1) {return arr}; var mid=Math.floor(arr.length/2); var left_arr=arr.
slice(0,mid),right_arr=arr.slice(mid); return
merge(mergeSort(left_arr),mergeSort(right_arr)); }

function AdjustHeap(arr, pos, len){ var swap = arr[pos]; var child = pos * 2 +
1; while(child < len){ if(child + 1 < len && arr[child] < arr[child + 1]){
child +=1; } if(arr[pos] < arr[child]){ arr[pos] = arr[child]; pos = child;
child = pos *2 + 1; } else{ break; } arr[pos] = swap; } } function HeapSort(arr)
{ for(var j=arr.length/2; j>=0; j--){ AdjustHeap(arr, j, arr.length); } for(var
i=arr.length-1; i>0; i--){ var swap = arr[i]; arr[i] = arr[0]; arr[0] = swap;

function quickSort(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)); }

function clone(obj){ var o; switch (typeof obj){ case "undefined": break; case
"string": o=obj+""; break; case "number": o=obj-0; break; case "boolean": o=obj;
break; case "object": if(obj===null){ o=null; } else { if(Object
.prototype.toString.call(obj).slice(8,-1)==="Array"){ o=[]; for(var i=0
;i<obj.length;i++){ o.push(clone(obj[i])); } }else { o={}; for(var k in obj){
o[k] = clone(obj[k]); } } }break; default: o = obj; break; } return o; }

function BubbleSort1(arr) { var i,j; for(var i=0;i<arr.length-1;i++){ for(var
j=arr.length-1;j>=i;j--){ if(arr[j-1]>arr[j]){ var temp=arr[j]; arr[j]=arr[j-1
]; arr[j-1]=temp; } } } return arr; } //改进冒泡 function BubbleSort2(arr) { var
i,j;var flag=true; for(var i=0;i<arr.length-1 && flag;i++){ flag=false; for(var
j=arr.length-1;j>=i;j--){ if(arr[j-1]>arr[j]){ var temp=arr[j]; arr[j]=arr[j-1
]; arr[j-1]=temp; flag=true; } } } return arr; } //选择排序 function
SelectSort(arr) { var i,j,min; for(var i=0;i<arr.length-1;i++){ min=i; for(var
j=i+1;j<arr.length;j++){ if(arr[min]>arr[j]) min=j; } if(i!=min){ var temp=arr[
min]; arr[min]=arr[i]; arr[i]=temp; } } return arr; } //直接插入排序 function
InsertSort(arr) { var i,j; for(var i=1;i<arr.length;i++){ if(arr[i]<arr[i-1]){
var temp=arr[i]; for (var j=i-1;arr[j]>temp;j--){ arr[j+1]=arr[j]; } arr[j+1
]=temp; } }return arr; } //插入排序 function insertionSort(arr) { for(var i=1
;i<arr.length;i++){ key=arr[i];var j=i-1; while ( j>=0 && arr[j]>key){ arr[j+1
]=arr[j]; j=j-1; } arr[j+1]=key; } return arr; } //希尔排序 function ShellSort(arr)
{ var i,j; var increment=arr.length; while (increment>1){ increment=Math
.floor(increment/3)+1; for(i=increment;i<arr.length;i++){ if
(arr[i]<arr[i-increment]){var tmp=arr[i]; for(j=i-increment;j>=0
&&tmp<arr[j];j-=increment){ arr[j+increment]=arr[j]; } arr[j+increment]=tmp; }
} }return arr; } //堆排序 function HeapSort(arr) { var i; for(i=Math
.floor(arr.length/2);i>=0;i--){ HeapAjust(arr,i,arr.length); } for
(i=arr.length-1;i>0;i--){ var temp=arr[0]; arr[0]=arr[i]; arr[i]=temp;
HeapAjust(arr,0,i-1); } return arr; } function HeapAjust(arr,s,m) { var temp;
temp=arr[s];for(var j=2*s;j<=m;j*=2){ if((j<m) && (arr[j]<arr[j+1])){ ++j; } if
(temp>=arr[j]){break; } arr[s]=arr[j]; s=j; } arr[s]=temp; } //归并排序 递归方式
function mergeSort(arr){ var len = arr.length; if(len > 1){ var index = Math
.floor(len /2); var left = arr.slice(0, index), right = arr.slice(index); return
merge(mergeSort(left), mergeSort(right)); }else{ return arr; } } function merge
(left, right){ var arr = []; while(left.length && right.length){ if(left[0] <
right[0]){ arr.push(left.shift()); }else{ arr.push(right.shift()); } } return
arr.concat(left, right); }//归并排序 //大辉版 function MergeSort(arr) { MSort(arr,arr,0
,arr.length-1); } function MergeSort(arr) { MSort(arr,0,arr.length-1); return
arr; }//将SR归并排序为result function MSort(arr,s,t) { if(s==t){ return; } else { var
m=Math.floor((s+t)/2); MSort(arr,s,m); MSort(arr,m+1,t); Merge(arr,s,m,t); } }
//SR源数组，SR[i,m],SR[m+1,n]组合为TR[i,n] function Merge(arr,left,mid,right) { var
i,j,k;var temp=[]; i=left; j=mid+1; k=0; while(i<=mid&&j<=right){ if
(arr[i]<arr[j]){ temp[k++]=arr[i++]; }else { temp[k++]=arr[j++]; } } while
(i<=mid){ temp[k++]=arr[i++]; }while(j<=right){ temp[k++]=arr[j++]; } k=0; for
(i=left;i<=right;i++){ arr[i]=temp[k++]; } }//归并排序 课本递归版 function MergeSort(arr)
{ var TR1=[]; MSort(arr,TR1,0,arr.length-1); return TR1; } //将SR归并排序为result
function MSort(SR,TR1,s,t) { var m; var TR2=[]; if(s==t){ TR1[s]=SR[s]; } else {
var m=Math.floor((s+t)/2); MSort(SR,TR2,s,m); MSort(SR,TR2,m+1,t);
Merge(TR2,TR1,s,m,t); } }//SR源数组，SR[i,m],SR[m+1,n]组合为TR[i,n] function Merge
(SR,TR,i,m,n) { var j,l; var k=0; for(j=m+1,k=i;i<=m&&j<=n;k++){ if
(SR[i]<SR[j]){ TR[k]=SR[i++]; }else { TR[k]=SR[j++]; } } if(i<=m){ for(l=0
;l<=m-i;l++){ TR[k+l]=SR[i+l]; } }if(j<=n){ for(l=0;l<=n-j;l++){
TR[k+l]=SR[j+l]; } }// return TR; } //归并排序 课本非递归版 function MergeSort2(arr) { var
TR=[];var k=1; while (k<arr.length){ MergePass(arr,TR,k,arr.length); k=2*k;
MergePass(TR,arr,k,arr.length); k=2*k; } return arr; } function MergePass
(SR,TR,s,n) { var i=0; var j; while (i<=n-2*s){ Merge(SR,TR,i,i+s-1,i+2*s-1);
i=i+2*s; } if(i<n-s){ Merge(SR,TR,i,i+s-1,n-1); } else { for(j=i;j<=n-1;j++){
TR[j]=SR[j]; } } }function Merge(SR,TR,i,m,n) { var j,l; var k=0; for(j=m+1
,k=i;i<=m&&j<=n;k++){if(SR[i]<SR[j]){ TR[k]=SR[i++]; } else { TR[k]=SR[j++]; } }
if(i<=m){ for(l=0;l<=m-i;l++){ TR[k+l]=SR[i+l]; } } if(j<=n){ for(l=0
;l<=n-j;l++){ TR[k+l]=SR[j+l]; } } } //快排 课本版 function QuickSort(arr){ if
(arr.length <=1){ return arr; } // 从中间取一个数 var index = Math.floor(arr.length / 2
);// 被选中的一个数 //arr.splice返回的是一个数组 var key = arr.splice(index, 1)[0]; var left =
[], right = [];for(var i = 0; i < arr.length; i++){ if(arr[i] < key){
left.push(arr[i]); }else{ right.push(arr[i]); } } return
QuickSort(left).concat(key, QuickSort(right)); }//
console.log(QuickSort([2,1,5,3,7,4,8,6,9])); function QuickSort(arr) {
QSort(arr,0,arr.length-1); return arr; } //对序列表中子序列作快排 function QSort
(arr,low,high) { var pivot; if(low<high){ pivot=Partion(arr,low,high);
QSort(arr,low,pivot-1); QSort(arr,pivot+1,high); } } //返回枢轴所在位置 function Partion
(arr,low,high) { pivotkey=arr[low]; while (low<high){ while
(low<high&&arr[high]>=pivotkey){ high--; }var temp=arr[low];
arr[low]=arr[high]; arr[high]=temp;while (low<high&&arr[low]<=pivotkey){ low++;
}var temp=arr[low]; arr[low]=arr[high]; arr[high]=temp; } return low; } //快排优化
function QuickSort(arr) { QSort(arr,0,arr.length-1); return arr; } //对序列表中子序列作快排
function QSort(arr,low,high) { var pivot; if(low<high){
pivot=Partion(arr,low,high); QSort(arr,low,pivot-1); QSort(arr,pivot+1,high); }
}//返回枢轴所在位置 function Partion(arr,low,high) { var pivotkey; var m=low+(high-low)/
2; if(arr[low]>arr[high]){ var temp=arr[low]; arr[low]=arr[high];
arr[high]=temp; }if(arr[m]>arr[high]){ var temp=arr[high]; arr[high]=arr[m];
arr[m]=temp; }if(arr[m]>arr[low]){ var temp=arr[low]; arr[low]=arr[m];
arr[m]=temp; } pivotkey=arr[low];while (low<high){ while
(low<high&&arr[high]>=pivotkey){ high--; }var temp=arr[low];
arr[low]=arr[high]; arr[high]=temp;while (low<high&&arr[low]<=pivotkey){ low++;
}var temp=arr[low]; arr[low]=arr[high]; arr[high]=temp; } return low; } //再优化
function QuickSort(arr) { QSort(arr,0,arr.length-1); return arr; } //对序列表中子序列作快排
function QSort(arr,low,high) { var pivot; if(low<high){
pivot=Partion(arr,low,high); QSort(arr,low,pivot-1); QSort(arr,pivot+1,high); }
}//返回枢轴所在位置 function Partion(arr,low,high) { var pivotkey; var m=low+(high-low)/
2; if(arr[low]>arr[high]){ var temp=arr[low]; arr[low]=arr[high];
arr[high]=temp; }if(arr[m]>arr[high]){ var temp=arr[high]; arr[high]=arr[m];
arr[m]=temp; }if(arr[m]>arr[low]){ var temp=arr[low]; arr[low]=arr[m];
arr[m]=temp; } pivotkey=arr[low];var num=pivotkey; while (low<high){ while
(low<high&&arr[high]>=pivotkey){ high--; } arr[low]=arr[high];while
(low<high&&arr[low]<=pivotkey){ low++; } arr[high]=arr[low]; } arr[low]=num;
return low; }

function search(arr,low,high, key) { var mid = parseInt((high + low) / 2); if
(arr[mid] == key){return mid; }else if (arr[mid] > key){ high = mid - 1; return
binary_search(arr, low, high, key); }else if (arr[mid] < key){ low = mid + 1;
return binary_search(arr, low, high, key); } }

function search(arr,key) { var low,mid,high; low=0; high=arr.length; while
(low<=high){mid=parseInt(low+high)/2; if(key<a[mid]){ high=mid-1; } else if
(key>a[mid]){ low=mid+1; } else return mid; } }