function bubbleSort(arr){
 var len=arr.length;
 for(var i=0;i<len;i++){
 for(var j=0;j<len-1-i;j++){ 
  if(arr[j]>arr[j+1]){ //相鄰元素兩兩對比
  var temp=arr[j+1]; //交互位置,所以大的都放到了最后面
  arr[j+1]=arr[j];
  arr[j]=temp;

  }
 }
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(bubbleSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

//插入排序
//假定當前元素之前的元素已經(jīng)排好序，先把自己的位置空出來，
//然后前面比自己大的元素依次向后移，直到空出一個"坑"，
//然后把目標元素插入"坑"中
function insertSort(arr){
 // 從第二個元素開始，因為要留出一個坑
 for(var i=1;i<arr.length;i++){
 var x=arr[i]; 
 for(var j=i-1;arr[j]>x;j--){ //后挪空出位置 .
  arr[j+1]=arr[j];
 }
 if(arr[j+1]!=x){
  arr[j+1]=x;
 }
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(insertSort(arr,2)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

 function shellSort(arr){
 var gap=Math.floor(arr.length/2);
 while(gap>0){
 for(var i=gap;i<arr.length;i++){
  temp=arr[i];
  for(var j=i;j>=gap&&arr[j-gap]>temp;j-=gap){
  arr[j]=arr[j-gap];
  }
  arr[j]=temp;
 }
 gap=Math.floor(gap/2);
 }
 return arr;
}
var arr = [2,3,6,4,2,1,90,100,20,5];
console.log(shellSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

/* 排序并合并*/
function merge(left, right) {
 var re = [];
 while(left.length > 0 && right.length > 0) {
 if(left[0] < right[0]) {
　　　　　　// 如果左邊的數(shù)據(jù)小于右邊的數(shù)據(jù)，將左邊的數(shù)據(jù)取出，放到新數(shù)組那里
  re.push(left.shift());
 } else {
  re.push(right.shift());
 }
 }
 /* 當左右數(shù)組長度不等.將比較完后剩下的數(shù)組項鏈接起來即可 */
 return re.concat(left).concat(right);
}
function mergeSort(arr) {
 if(arr.length == 1){
 return arr;
 }
 /* 首先將無序數(shù)組劃分為兩個數(shù)組 */
 var mid = Math.floor(arr.length / 2);
 var left = arr.slice(0, mid);
 var right = arr.slice(mid);
 /* 遞歸分別對左右兩部分數(shù)組進行排序合并 */
 return merge(mergeSort(left), mergeSort(right));
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(mergeSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

// 大致分三步：
 // 1、找基準（一般是以中間項為基準）
 // 2、遍歷數(shù)組，小于基準的放在left，大于基準的放在right
 // 3、遞歸
 function quickSort(arr){
 //如果數(shù)組<=1,則直接返回
 if(arr.length<=1){
  return arr;
 }
 var pivotIndex=Math.floor(arr.length/2);
 //找基準，并把基準從原數(shù)組刪除
 var pivot=arr.splice(pivotIndex,1)[0];
 //定義左右數(shù)組
 var left=[];
 var right=[];

 //比基準小的放在left，比基準大的放在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));
 }
 var arr=[2,3,6,4,2,1,90,100,20,5];
 console.log(quickSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

// 在無序區(qū)中選出最小的元素，然后將它和無序區(qū)的第一個元素交換位置。
function selectSort(arr){
 length = arr.length;
 for (var i = 0; i < length; i++){ // 循環(huán)數(shù)組
 var _min = arr[i]; // 把每一次的 數(shù)組里面的數(shù)字記錄下來
 var k = i;   // 記錄下來索引
 for (var j = i + 1; j < length; j++){ // 當前的數(shù)字與后一個數(shù)字相比較
  if (_min > arr[j]){ //當前的數(shù) 大于 后面一個數(shù)的話
  _min = arr[j]; // 就講后面 的數(shù)值 保存下來
  k = j;  /// 保存索引
  }
 }
 arr[k] = arr[i]; // 進行交換位置
 arr[i] = _min;
 }
 return arr;
}
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(selectSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

function oddEvenSort(arr){
 //swaped用來控制循環(huán)是否要繼續(xù)，如果左邊的都比右邊的小，則退出循環(huán)，返回排好的數(shù)組
 var swaped=true; 
 var k=0;
 while(swaped){
 if(k>0){
  swaped=false; 
 }
 for(var i=k;i<arr.length-1;i+=2){
  if(arr[i]>arr[i+1]){
  // 如果左邊的數(shù)字比右邊的大，兩者交換位置
  arr[i]=[ arr[i+1], arr[i+1]=arr[i] ][0]; 
  swaped=true;
  }
 }
 k=[1,0][k]; //奇數(shù)和偶數(shù)之間的轉行
 }
 return arr;
} 
var arr=[2,3,6,4,2,1,90,100,20,5];
console.log(oddEvenSort(arr)); // [1, 2, 2, 3, 4, 5, 6, 20, 90, 100]