Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

冒泡排序

介绍

重复遍历要排序的元素列,依次比较两个相邻的元素,前一个元素若比后一个元素大则互换位置。以升序排序为例,最大的元素会在第一次遍历后“冒泡”到数组的末端。假如数组长度为n,在n-1次遍历后可完成排序。

实现

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function bubbleSort(arr) {
  let time = arr.length - 1
  while (time) {
    let i = 0
    while (i<time) {
      if (arr[i] > arr[i+1]) [arr[i], arr[i+1]] = [arr[i+1], arr[i]]
      i ++
    }    
    time --
  }
}

bubbleSort(arr)

快速排序

介绍

通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

实现

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort(arr) {
  if (arr.length <= 1) return arr
  let pivotVal = arr[0],
  smallers = [], 
  biggers = [], 
  idx = 1
  while (idx < arr.length) {
    if (pivotVal > arr[idx]) {
      smallers.push(arr[idx])
    } else {
      biggers.push(arr[idx])
    }
    idx ++
  }
  return quickSort(smallers).concat(pivotVal, quickSort(biggers))
}

quickSort(arr)

这种方法较好理解,就是找一个基准元素,一般是数组的第1位,然后遍历数组,比基准元素大的元素扔进去一个临时数组里,较小的扔进另一个临时数组里,最后把这两个数组和基准元素按顺序拼接起来。当然临时数组还要递归调用方法来对内部继续进行拆分,直到最后产生的临时数组长度为0或1为止。

接下来对此方法进行优化,毕竟这样一套递归下来,新建了不少临时数组,对性能会有一定的影响。

优化

let arr = [1, 5, 2, 9, 7, 4, 2, 3, 6, 8]

function quickSort2(arr, start, end) {
  while(start >= end) return
  let pivot = start,
  pivotVal = arr[pivot],
  idx = pivot + 1
  while (idx <= end) {
    if (arr[idx] < pivotVal) {
      pivot ++
      if (arr[pivot] != arr[idx]) {
        [arr[pivot], arr[idx]] = [arr[idx], arr[pivot]]
      }
    }
    idx ++
  }
  [arr[pivot], arr[start]] = [arr[start], arr[pivot]]
  quickSort2(arr, pivot + 1, end)
  quickSort2(arr, 0, pivot - 1)
}

quickSort2(arr, 0, arr.length-1)

原理就是以数组的第一个元素为基准元素,从第二个元素开始对基准元素进行比较,如果比基准元素小则让基准点前进一位,同时把现基准点上的值与对比元素的值对换。一次遍历下来后,现基准点所在的位置就是最后一个比基准元素小的元素所在的位置,右边是大于或者等于基准元素的元素,左边是小于基准元素的元素(除了第一位,第一位是基准元素),所以最后一步操作就是让现基准点上的元素和第一位上的元素(基准元素)互换,确保基准点和基准元素对应上。之后递归调用就可以完成。

Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

快速排序,简单高效,但是当序列长度在5到25之间时,直接插入排序的速度比快速排序快至少10%, 改进后的快速排序,当数据规模小于25时,采用直接插入排序。

插入排序

介绍

当插入第i(i ≥ 1)个元素时,假设前面从arr[0]到arr[i-1]已经有序,那么只需将arr[i]和前面那些有序的数值进行比较,找到自己应该插入的位置即可,原来位置上的元素一次向后顺移。

实现

let arr = [0, 99, 2, 6, 1, 10, 2, 3, 1, 9, 0]

function insertSort(arr) {
  let idx = 1
  while(idx < arr.length) {
    while(idx > 0) {
      if (arr[idx] >= arr[idx-1]) break
      [arr[idx], arr[idx-1]] = [arr[idx-1], arr[idx]]    
      idx --
    }
    idx ++
  }
}

insertSort(arr)

Javascript实现冒泡排序与快速排序以及对快速排序的性能优化

相关推荐