基本排序法概览

本文所有测试及排序算法

公用测试部分

1
2
3
4
5
6
7
function createTestData() {
  var testData = []
  for (var i = 0; i < 10; i++) {
    testData.push(Math.floor(Math.random() * 100))
  }
  return testData
}

冒泡排序

可以先找大的，也可以先找小的

  • 含有两层循环，外层循环决定冒泡排序的结束位置索引，内层循环决定当前这一项冒泡排序的开始位置索引
  • 每次内层循环，仅比较当前项和下一项的大小，如果当前项较大，则将两项位置互换。
  • 保证每次内层循环结束后，内层循环的数列的末尾值是该数列的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
function sort(data = []) {
    data = Object.assign([], data)
    for (sp = data.length - 2; sp >= 1; sp--) {
      for (mp = 0; mp <= sp; mp++) {
        if (data[mp] > data[mp + 1]) {
          var temp = data[mp]
          data[mp] = data[mp + 1]
          data[mp + 1] = temp
        }
      }
    }
    return data
}

选择排序

可以先找大的，也可以先找小的

  • 含有两层循环，外层循环决定选择排序当前比较数列的开始索引，同时假定当前开始索引中存储的值最小，内层循环决定选择排序仍然需要比较的数列范围
  • 当需要比较的数列范围内有比当前假定的最小值小的值时，将两个值的位置互换
  • 这种算法保证每次内层循环后都找到当前内层循环队列中的最小值，并且处于当前数列的头部
  • 这是一种循环找极值的排序算法
1
2
3
4
5
6
7
8
9
10
11
12
13
function sort(data=[]) {
    data = Object.assign([], data)
    for (var sp = 0; sp < data.length - 1; sp++) {
      for (var mp = sp + 1; mp < data.length; mp++) {
        if (data[mp] < data[sp]) {
          var temp = data[sp]
          data[sp] = data[mp]
          data[mp] = temp
        }
      }
    }
    return data
}

插入排序

可以先找大的，也可以先找小的

  • 从第二项开始遍历，从当前项往前检查之前的项是否比当前项大，如果大则两项位置互换，然后重复此过程，直到检查完所有之前的项或者碰到小于当前项的项，即在之前的项中找到适合当前项的位置，并将项插入到这个合适的位置上
  • 由于每一次项插入后的数列都是有序的，保证了当前项之前的项一定是有序的
1
2
3
4
5
6
7
8
9
10
11
12
13
function sort(data = []) {
    data = Object.assign([], data)
    for (let i = 1; i < data.length; i++) {
      const temp = data[i]
      let j = i
      while (j > 0 && data[j - 1] > temp) {
        data[j] = data[j - 1]
        j -= 1
      }
      data[j] = temp
    }
    return data
}
分享到