排序方法

一、 冒泡排序

var arr = [18, 12, 20, 8, 30, 4];
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; 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;
      }
    }
  }
  console.log(arr);
  return arr;
}
bubbleSort(arr);

二、 快速排序

1. 先随机找出其中一个'基准'
2. 创建两个空数组,分别为左右数组,放置的值就是比基准小或大的数
3. 根据左右两侧数组的长度,只要不是剩下一个数,就继续执行步骤一二,拆分数组
4. 直到所有的数组长度为一,重新合并数组

var arr = [18, 22, 20, 8, 30, 4];

/*
		20  --> [18 ,12,8,30,4]
		    左边 [18,12,8,4]    基准 [20]  右边 [30]
		12  --> [18 ,8 ,4]
		    左边 [8,4]    基准 [12]  右边 [18]
		4  --> [8]
		    左边 []   基准 [4]  右边 [8]
*/

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr; //长度为1或0的时候,返回自身,不需要拆分
  }

  //1.找基准下标
  var index = Math.floor(Math.random() * (arr.length - 1));
  // 1. 从原数组抽取基准值
  var mid = arr.splice(index, 1);
  // 2.
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < mid[0]) {
      //小的放左
      left.push(arr[i]);
    } else {
      //大的放右
      right.push(arr[i]);
    }
  }
  // console.log(left,mid, right);
  //4. 拼接数组
  return quickSort(left).concat(mid, quickSort(right)); //3.
}

console.log(quickSort(arr));
quickSort(arr);