常用的排序方式有哪些?

在写排序之前我们需要先搞懂两个概念 排序的稳定性时间复杂度

排序的稳定性

排序分为稳定排序和不稳定排序,稳定排序在排序过程中不会影响到想等数据之间的相对位置,如

1
2
3
// 我们为了方便标示 将2做区分为a2 和 b2
// const a = [2, 3, 2, 1]
const a = [a2, 3, b2, 1]

冒泡排序的步骤是这样的

整个过程a2和b2的位置相对没有发生变化,因此冒泡排序属于稳定排序

选择排序是这样的

选择排序在排序过程中a2和b2的相对位置已经发生变化,因此选择排序属于不稳定排序

时间复杂度

这个就直接看这篇文章:(数据结构)十分钟搞定算法的时间复杂度

1
2
// 数组为arr,将arr升序排列
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]

冒泡排序(稳定排序)

冒泡排序是最常见的排序方式

1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr.length - 1; j++) {
    if (arr[j] > arr[j + 1]) {
      [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
    }
  }
}
console.log(arr)  // [0, 1, 2, 2, 3, 3, 4, 22, 33, 52, 88, 120]

实现方式:

  • 从第一个元素开始,比较相邻的元素,如果前一个比后一个大,则交换两个元素位置,继续比较第二个(原本的第一个)和第三个的大小以此类推
  • 第一轮比较完了之后会找到一个最大数值,在数组的最后一位
  • 开始第二轮,从第二个开始,执行第一步,得到的是第二大元素,放在倒数第二个位置
  • 第三个、第四个、第五个... 以此类推
  • 最后得到一个从小到大的排序

时间复杂度: O(n²) 两次for循环

选择排序(不稳定排序)

1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]

for (let i = 0; i < arr.length - 1; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[i] > arr[j]) {
      [arr[i], arr[j]] = [arr[j], arr[i]]
    }
  }
}
console.log(arr)  // [0, 1, 2, 2, 3, 3, 4, 22, 33, 52, 88, 120]

实现方式:

  • 从第一个元素开始到倒数第二个元素,因为执行到这个时候已经知道最大值了,而且已经在最后一位了
  • 子循环查询从第一个元素之后(第二个)到最后一个,有没有比地一个元素小的,有的话交换位置,继续往后查找有没有比当前第一个元素小的,如果小的话以此类推(此时可以得到第一次内部轮训最小的一个元素,且已经放在数组的第一位了)
  • 第二个、第三个、第四个... 以此类推
  • 最后得到一个从小到大的排序

时间复杂度: O(n²) 两次for循环

插入排序(稳定排序)

1
2
3
4
5
6
7
8
9
10
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]

for (let i = 1; i < arr.length; i++) {
  for (let j = i; j > 0; j --) {
    if (arr[j] < arr[j - 1]) {
      [arr[j - 1], arr[j]] = [arr[j], arr[j - 1]]
    }
  }
}
console.log(arr)

实现方式

  • 第一次从第二个元素开始,内层循环从第二个和第一个元素进行比对大小,如果第一个比第二个大则调换位置
  • 第二次从第三个元素开始,内层循环从第三个看是否比第二个大,如果大的话则不做任何操作,如果小则第三个和第二个调换,然后再和第一个比较大小,重复此操作
  • 第三次、第四次、第五次...
  • 最后得到一个从小到大的排序

时间复杂度: O(n²) 两次for循环

快速排序(不稳定排序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const arr = [1, 3, 0, 88, 33, 22, 120, 4, 2, 2, 3, 52]

function sort (lists) {
  if (lists.length <= 1) {
    return lists
  }
  const tmp = lists.splice(0, 1)[0]
  let left = []
  let right = []
  lists.forEach((item) => {
    if (tmp > item) {
      left.push(item)
    } else {
      right.push(item)
    }
  })

  return sort(left).concat(tmp, sort(right))
}

console.log(sort(arr))

实现方式

  • 递归的方式,第一次在数组中随机取一个元素,注意是取出,arr的length被取出会少一个长度
  • 取出的一个元素作为分界线,小于这个元素的放在左边,否则放在右边
  • 第一轮结束之后,针对两边的arr执行相同的操作,知道执行方法传入的数组的长度为1,返回这个数组
  • 将每次执行的方法 由 - tmp - 连接完成快速排序操作 时间复杂度: O (nlogn)

未完 待续

上一篇 : javascript需要注意的this指向问题下一篇 : js数据类型转换