JavaScript常用排序算法

// 冒泡算法
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
	for (var j = 0; j < len-1-i; j++) {
	// 为什么要减一，数组从0开始，先取第一个与第二个比，再将较大值与第三个比，一直比到最后一个，再拿第二个值与第三个比……(外层循环一次，内层循环多次)
	  if (arr[j] > arr[j+1]) { // 比较相邻两个值的大小
		var temp = arr[j+1]; // 临时变量存储arr[j+1]的值
		arr[j+1] = arr[j]; // 将arr[j]的值赋值给arr[j+1]，即把较大值往后放
		arr[j] = temp; // 又将temp的值赋值给arr[j]，即将较小值往前放
	  }
	}
  }
  return arr;
}
var arr = [2, 3, 4, 5, 6, 1, 90, 16, 35, 7];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 16, 35, 90]

// 插入排序
function insertSort(arr) {
  // 从第二个元素开始，因为要留一个坑
  for (var i = 1; i < arr.length; i++) {
    var x = arr[i]; // 现将arr[i]的值存下来
	for (var j = i-1; arr[j] > x; j--) {
	  arr[j+1] = arr[j]; // i=3时 [2, 3, 6, 6, ...]
	}
	if (arr[j+1] != x) {
	  arr[j+1] = x; // i=3时 j=2 [2, 3, 4, 6, ...]
	}
  }
  return arr;
}
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(insertSort(arr)); //[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]

// 大致分三步：
// 1、找基准（一般以中间项为基准）
// 2、遍历数组，小于基准的放在left，大于基准的放在right
// 3、递归
function quickSort(arr) {
// 如果数组<=1，则直接返回
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  // 找基准，并把基准从原数组删除
  var pivot = arr.splice(pivotIndex, 1)[0];
  // 定义左右数组
  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]

//奇偶排序
function oddEvenSort(arr) {
// swaped用来控制循环是否要继续，如果左边的都比右边的小，则退出循环，返回排好的数组
  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]) {
	    // 如果左边的数字比右边的大，两边交换位置
	    arr[i] = [arr[i+1], arr[i+1] = arr[i]][0];
		swaped = true;
	  }
	}
	k = [1, 0][k]; // 奇偶数之间的转换
  }
  return arr;
}
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(oddEvenSort(arr)); // [1, 2, 3, 4, 5, 6, 20, 90, 100]