JavaScript 实现冒泡排序与快速排序

lastUpdated: 2023-7-27

一、冒泡排序

冒泡排序的原理：

冒泡排序对相邻元素进行两两比较，如果顺序不对，就要对其位置进行调换，一直到排序完成。比如第一趟比较：首先比较第一个和第二个数的大小，将小数放前，大数放后。然后比较第二个数和第三个数的大小，再将小数放前，大数放后。以此类推，直到比较完最后两个数，第一趟就比较完了。重复第一趟过程，若有 n 个数，就要比较 n-1 趟。

冒泡排序的图解：

在 JavaScript 中可以使用双重循环，外层循环控制比较多少趟，内层循环每一趟比较的次数。

const arr1 = [2, 10, 5, 4, 11, 9, 7, 8, 1, 12, 3, 6, 13, 15, 14]

const bubbleSort = (arr) => {
  for (let j = 0; j < arr.length - 1; j++) {
    let isOk = true
    for (let i = 0; i < arr.length - 1 - j; i++) {
      let prev = arr[i]
      let next = arr[i + 1]
      if (prev > next) {
        arr[i] = next
        arr[i + 1] = prev
        isOk = false
      }
    }
    if (isOk) {
      break
    }
  }
  return arr
}

const res = bubbleSort(arr1)

console.log(res)

冒泡排序的缺点：

但是冒泡排序也有一定的缺点，就是在比较过程中小的数不能一次到位，会导致效率低。所以一般不会选择冒泡排序，虽然冒泡排序书写是最简单的，但是平均性能没有选择排序好。

二、快速排序

快速排序的思想：

「 快速排序 」的思想很简单，整个排序过程只需要三步：

1. 从数组中选择一个元素作为“基准”（pivot）。
2. 遍历数组将小于“基准”的元素放入左边数组，将大于等于“基准”的元素放入右边数组。
3. 对“基准”左边和右边的两个子集不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

const arr1 = [1, 4, 5, 7, 8, 6, 89, 4, 3, 2, 11, 9]

const quickSort = arr => {
    if ( toString.call(arr) !== '[object Array]' || arr.length <= 1 ) {
        return arr
    }
    const pivotIndex = Math.floor(arr.length / 2)
    const pivot = arr.splice(pivotIndex, 1)[0]
    const leftArr = []
    const rightArr = []
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
            leftArr.push(arr[i])
        } else {
            rightArr.push(arr[i])
        }
    }

    // return quickSort(leftArr).concat([pivot], quickSort(rightArr))
    return [ ...quickSort(leftArr), pivot, ...quickSort(rightArr) ]
}

const res = quickSort(arr1)

console.log('quick sort result: ', res)

Comment area