JavaScript数组-排序算法

冒泡排序

插入排序

快速排序

选择排序

希尔排序

归并排序

...

算法在线动态演示

// 冒泡排序
    // 当前项和后一项进行比较 如果当前项大于后一项则 交换位置
    var arr = [29, 10, 34, 40, 18]

    function bubbleSort(arr) {
      arr = arr.slice(0)

      for (var i = 0; i < arr.length - 1; i++) {
        for (var j = 0; j < arr.length - 1 - i; j++) {
          var cur = arr[j]
          if (cur > arr[j + 1]) {
            var temp = arr[j]
            arr[j] = arr[j + 1]
            arr[j + 1] = temp
          }
        }
      }
      return arr
    }
    console.log(bubbleSort(arr)) // [10, 18, 29, 34, 40]


    // 快速排序
    // 创建两个数组(left right) 用中间项和其它项比较，比中间项小的放在左边数组 比中间项大的放在右边数组... 
    // 左边数组和右边数组均按照以上思路 进行排序
    function quickSort(arr) {
      if (arr.length <= 1) {
        return arr
      }
      var mind = Math.floor(arr.length / 2)
      var mid = arr.splice(mind, 1)
      var left = []
      var right = []
      for (var i = 0; i < arr.length; i++) {
        var cur = arr[i]
        if (cur < mid) {
          left.push(cur)
        } else {
          right.push(cur)
        }
      }
      return quickSort(left).concat(mid, quickSort(right))
    }
    var arr = [29, 10, 34, 40, 18]

    console.log(quickSort(arr)) // [10, 18, 29, 34, 40]
复制代码

算法具体实现

冒泡排序

让当前项和后一项进行比较，如果当前项大于后一项则交换位置。

思想：

• 比较相邻的两个的元素，如果当前元素大于后一项 则交换位置

• 对每一对相邻两项，从开始第一对到结尾的最后一对。每一轮比较结束后，都会有一个最大的数排在后面

• 随着每轮的比较，越来越少的元素重复上面的步骤（后面排列着之前几轮每轮比较出来的最大数），直到没有任何一对数字需要比较。

// 冒泡排序 bubbleSort
  function bubbleSort(arr) {
    var temp
    for (var i = 0; i < arr.length - 1; i++) { // 控制轮数
      for (var j = 0; j < arr.length - 1 - i; j++) { // 控制每轮的比较次数
        if (arr[j] > arr[j + 1]) {
          temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = temp
        }
      }
    }
    return arr
  }
  bubbleSort(arr)
复制代码

简单优化 - 对于有序数组无须排序

// 冒泡排序 bubbleSort
  function bubbleSort(arr) {
    var temp
    for (var i = 0; i < arr.length - 1; i++) { // 控制轮数
      var isSort = true
      for (var j = 0; j < arr.length - 1 - i; j++) { // 控制每轮的比较次数
        if (arr[j] > arr[j + 1]) {
          temp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = temp
          isSort = false
        }
      }
      if (isSort) {
        return arr
      }
    }
    return arr
  }
  bubbleSort(arr)
复制代码

继续优化-抽象处理交换逻辑swap

// 冒泡排序 bubbleSort
  function bubbleSort(arr) {
    for (var i = 0; i < arr.length - 1; i++) { // 控制轮数
      var isSort = true
      for (var j = 0; j < arr.length - 1 - i; j++) { // 控制每轮的比较次数
        if (arr[j] > arr[j + 1]) {
          swap(arr, i, j) // 交换位置
          isSort = false
        }
      }
      if (isSort) {
        return arr
      }
    }
    return arr
  }
   
  // 交换swap
  function swap(arr, i, j) {
    var temp = arr[j]
    arr[j] = arr[j + 1]
    arr[j + 1] = temp
  }
  bubbleSort(arr)
复制代码

插入排序

思想：

插入 排序 是从后往前比较, 从第二项开始一次往前比较 如果当前项大于前一项 则停止比较并将当前项插入到前一项的后面

function insertC(A) {
  for (let i = 1; i < A.length; i++) {
    // p 指向 下一个要比较的索引
    let p = i - 1

    // 当前要插入项
    let cur = A[i]
    
    // 只要前一项大于当前项就一直循环下去
    while(p >= 0 && A[p] > cur) {
      // 前一项大于当前项 就将前一项往后挪一位
      A[p + 1] = A[p]
      // 每比较完一次 p存储的索引值 就往前挪一位 进行下次比较
      p--
    }

    // 执行到这一行 说明 当前项cur 大于索引p这一项
    // 则将当前项插入到后面
    A[p + 1] = cur
  }
}

const A5 = [2, 4, 13, 6, 3]
insertC(A5)
console.log(A5) // [ 2, 3, 4, 6, 13 ]
复制代码

// 插入排序
  function insertSort(arr) {
    var len = arr.length
    var cur
    var prev
    for (var i = 1; i < len; i++) {
      cur = arr[i]
      prev = i - 1
      while (prev > -1 && cur < arr[prev]) {
        arr[prev + 1] = arr[prev]
        prev--
      }
      arr[prev + 1] = cur
    }
    return arr
  }
  insertSort(arr)
复制代码

快速排序

思想:

1.在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；

2.将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；

3.对左右两个分区重复以上步骤直到所有元素都是有序的。

快速排序（大众版）

// 快速排序 (大众版)
function quickSort(arr) {
  if (arr.length <= 1) return arr
  let midIndex = Math.floor(arr.length / 2)
  let midNum = arr.splice(midIndex, 1)[0]
  let left = []
  let right = []
  for (let i = 0; i < arr.length; i++) {
    let cur = arr[i]
    if (cur <= midNum) {
      left.push(cur)
    } else {
      right.push(cur)
    }
  }
  return quickSort(left).concat(midNum, quickSort(right))
}
let arr = [2, 4, 12, 9, 22, 10, 18, 6]
console.log(quickSort(arr))
复制代码

快速排序（完全版）

let array = [9, 6, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];

function quickSort(arr, left = 0, right = arr.length - 1) {
  let len = arr.length;
  let partitionIndex;
  // left = typeof left != 'number' ? 0 : left;
  // right = typeof right != 'number' ? len - 1 : right;
  if (left < right) {
    partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}

function partition(arr, left, right) {
  let pivot = left;
  let index = pivot + 1;
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
  return index - 1;
}

function swap(arr, i, index) {
  [arr[i], arr[index]] = [arr[index], arr[i]];
}
console.log(quickSort(array));
复制代码

快速排序 - 原地排序

function swap(A, i, j) {
  [A[i], A[j]] = [A[j], A[i]]
}

function partition(A, lo, hi) {
  const pivot = A[hi - 1]
  let j = hi - 1
  let i = lo
  while(i !== j) {
    A[i] <= pivot ? i++ : swap(A, i, --j)
  }
  swap(A, j, hi - 1)
  return j
}

function qsort(A, lo = 0, hi = A.length) {
  if (hi - lo <= 1) return
  const p = partition(A, lo, hi)
  qsort(A, lo, p)
  qsort(A, p + 1, hi)
}
const A = [1, 5, 28, 6, 0, 12]
qsort(A)
console.log(A) // [ 0, 1, 5, 6, 12, 28 ]
复制代码

选择排序

思想：

每一次从未排序序列中找到最小（大）元素，存放到排序序列的当前的起始位置。以此类推，直到所有元素均排序完毕。

// 选择排序 insert_sort
const ary = [1, 24, 8, 19, 10]

function insert_sort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    var min = i
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j
      }
    }

    if (i !== min) {
      var temp = arr[i]
      arr[i] = arr[min]
      arr[min] = temp
    }
  }
  return arr
}

console.log(insert_sort(ary))
复制代码

希尔排序

let array = [5, 13, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];

function shellSort(arr) {
  var len = arr.length,
    temp,
    gap = 1;
  while (gap < len / 3) { //动态定义间隔序列
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

console.log(shellSort(array));
复制代码

归并排序

let array = [5, 13, 20, 3, 2];
// let array = [15, 13, 20, 21, 29];

function mergeSort(array) {
  let arr = array.slice(0);
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let midIndex = Math.floor(len / 2);
  let left = arr.slice(0, midIndex);
  let right = arr.slice(midIndex);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  while(left.length && right.length) {
    result.push(left[0] < right[0] ? left.shift() : right.shift());
  }

  if (left.length && !right.length) {
    result = result.concat(left);
  }

  if (right.length && !left.length) {
    result = result.concat(right);
  }
  return result;
}

console.log(mergeSort(array));
复制代码

----------------------------------------------------------------------------------------------------------------

参考文章&&强烈推荐：布罗利