<< 返回算法列表

排序

描述：给定一个数组，请你编写一个函数，返回该数组排序后的形式。

示例1

输入：
[5,2,3,1,4]
返回值：
[1,2,3,4,5]

示例2

输入：
[5,1,6,2,5]
返回值：
[1,2,5,5,6]

解答

常见排序方案有：快速排序、冒泡排序、选择排序、插入排序。其中快速排序性能最好，时间复杂度是O(N*logN)，另外三种时间复杂度均为O(N^2)。

使用JavaScript实现快速排序算法时有两种方法，一种是在递归时创建临时数组，代码简单、思路清晰，但空间利用太多。 还有一种是直接在数组上操作。

快速排序

function quickSort(arr) {
  if(arr.length <= 1) {
    return arr
  }
  let leftArr = [] 
  let rightArr = []
  for(let i = 1; i < arr.length; i++) {
    if(arr[i] >= arr[0]) {
      rightArr.push(arr[i])
    } else {
      leftArr.push(arr[i])
    }
  }
  return quickSort(leftArr).concat(arr[0]).concat(quickSort(rightArr))
}
 
let arr = [10, 34, 21, 47, 3, 28]
quickSort(arr)
console.log(arr)

排序步骤

• 从数列中挑出一个元素，称为“基准”，
• 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面
• 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序
• 递归到最底部时，数列的大小是零或一，也就是已经排序好了

原理演示

在原数组上操作

function quickSort(arr) {
  function _quickSort(arr, start, end) {
    if(start >= end) return
    let key = arr[end]
    let left = start, right = end - 1
    while(left < right) {
      while(arr[left] < key && left < right) left++
      while(arr[right] >= key && left < right) right--
      [arr[left], arr[right]] = [arr[right], arr[left]]
    }
    if(arr[left] >= arr[end]) { 
      [arr[left], arr[end]] = [arr[end], arr[left]]
    } else {  // 对于最后一个是最大值的情况
      left++
    }
    _quickSort(arr, start, left - 1)
    _quickSort(arr, left + 1, end)
  }
  _quickSort(arr, 0, arr.length - 1)
  return arr
}

原理演示

冒泡排序

原理：相邻元素比较交换

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

选择排序

原理：依次从未排序部分找到最小的，和第一个、第二个、...、交换

function sectionSort(arr) {
  for(let i = 0; i < arr.length-1; i++) {
    let min = i
    for(let j = i + 1; j < arr.length; j++) {
      if(arr[min] > arr[j]) {
        min = j
      }
    }
    [ arr[i], arr[min] ] = [ arr[min], arr[i] ] //把每轮的第一个和当前轮的最小值交换位置
  }
}

插入排序

原理： 依次取出未排序元素，插入到已排序的合适位置

function insertionSort(arr) {
  for(let i = 1; i < arr.length; i++) {
    for(let j = 0; j < i; j++) {
      if(arr[i] < arr[j]) {
        //arr[i]复制一份插入j前面
        arr.splice(j, 0, arr[i]) 
        arr.splice(i+1, 1) //删除原来的arr[i]，注意i的位置变成i+1
        break
      }
    }
  }
}