# 排序算法

# 冒泡排序

让数组的当前项和数组的后一项进行比较,如果当前项比后一项大,则两项交换位置(让大的靠后)即可

const arr = [12, 5, 56, 78, 90]
function bubbleSort(arr) {
  const len = arr.length - 1;
  let temp = null;
  // 外层循环控制比较次数
  for (let i = 0; i < len; i++) {
    let done = true; // 设置标记优化循环次数
    // 里层循环每一次比较次数
    for (let j = 0; j < len - i; j++) {
      // 如果前一项大于后一项,交换位置
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        done = false;
      }
    }
    if (done) {
      break;
    }
  }
  return arr;
}
console.log(bubbleSort(arr)); // [5, 12, 56, 78, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 插入排序

  • 开始先抓一张牌
  • 继续抓牌,抓到这张牌,和手里的牌依次比较(从后向前比较)
  • 如果当前新牌A比手里的某张牌B大,则把A放到B的后面,如果小则继续向前面的牌比较(如果已经比较到第一张了,则把当前牌A插入到最前面即可)
const arr = [12, 5, 56, 78, 90]
function insertSort(arr) {
  // 1.定义新数组,用来存储抓到手里的牌
  const handleBrand = [];
  const len = arr.length;
  handleBrand.push(arr[0]); // 开始先抓一张牌进来
  // 2. 从第二项开始依次抓牌,一直到把台面上的牌抓光  
  for (let i = 1; i < len; i++) {
    // brand当前新抓的牌
    const brand = arr[i];
    const max = handle.length;
    // 和handle手里的牌依次比较(从后向前比较)  
    for (let j = max; j >= 0; j--) {
      const branded = handle[j]; // 每一次要比较的牌
      // 如果当前新牌brand比要比较的牌大,把brand放到branded后面  
      if (brand > branded) {
        handleBrand.splice(j + 1, 0, brand);
        break;
      }
      // 当前已经比到第一项,把新牌放到手中第一项即可
      if (j === 0) {
        handleBrand.unshift(brand);
      }
    }
  }
  return handleBrand;
}
console.log(insertSort(arr)); // [5, 12, 56, 78, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# 快速排序

  • 找到数组中间项,从数组中移除
  • 让拿出的每一项和中间项继续比较
  • 中间项小的放在左边数组
  • 中间项大的放在右边数组
  • 左右边数组继续重复上面操作(递归)
  • 直至得到结果,左边 + 中间项 + 右边
const arr = [12, 5, 56, 78, 90]
function quickSort(arr) {
  // 当arr中小于等于一项,则不做处理
  if (arr.length <= 1) {
    return arr;
  }
  // 1. 找到中间项, 移除
  let middleIndex = Math.floor(arr.length / 2);
  const middleValue = arr.splice(middleIndex, 1)[0];
  // 2. 准备左右数组
  const arrLeft = [];
  const arrRight = [];
  for (let i = 0; i < arr.length; i++) {
    let item = arr[i];
    if (item < middleValue) {
      arrLeft.push(item);
    } else {
      arrRight.push(item);
    }
  }
  return quickSort(arrLeft).concat(middleValue, quickSort(arrRight));
}
console.log(quickSort(arr))// [5, 12, 56, 78, 90]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
更新于: 2/4/2020, 6:54:30 AM