排序算法

sort-alg.md

• bubble
• merge 归并
• quick

https://www.geeksforgeeks.org/merge-sort/?ref=lbp

各种排序：http://blog.csdn.net/han_xiaoyang/article/details/12163251 排序动画：http://jsdo.it/norahiko/oxIy/fullscreen

sort-bubble.js

// 冒泡排序
function bubbleSort(arr) {
  let len = arr.length
  if (len < 2) return arr
  do {
    for (let i = 0; i < len; i++) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1)
      }
    }
  } while (len--)
  return arr
}
function swap(arr, i, j) {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}


const descBubbleSort = (arr) => {
  let l = arr.length

  while (l--) {
    for (let j = 0; j < l; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }

  return arr
}

sort-insertion.js

/**
 * 插入排序
 * @returns {Array}
 */
exports.insertion_sort = function (arr) {
    if (arr.length === 1) return arr;

    let i, j, temp
    for (i = 1; i < arr.length; i++) {
        j = i - 1

        /// region method 1
        // 与已排序的数逐一比较，前值大时替换位置
        /*while ((j >=0) && (arr[j] > arr[j + 1])) {
		    [arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
            j--
        }*/
        /// endregion

        /// region method 2
        temp = arr[i];
        //大于temp时，该数后移,是于temp比较，而不是j+1或j-1!!!!
        while ((j >= 0) && (arr[j] > temp)) {
            arr[j + 1] = arr[j]
            j--
        }
        // asc 倒序排列
        /*while(j >= 0 && arr[j] < temp) {
        }*/
        arr[j + 1] = temp
        /// endregion

        /// region

        /// endregion
    }
    return arr;
};

/**
 * 二分插入排序: 查找插入位置时使用的是二分查找的方式
 * 因为插入排序的一侧是已经排序好的，所以可以用二分查找
 */
exports.binary_insertion_sort = arr => {
    for (let i = 1; i < arr.length; i++) {
        let left = 0, right = i - 1, middle;
        let temp = arr[i]

        // find the `left`
        while (left <= right) {
            middle = Math.floor((left + right) / 2);
            if (arr[middle] > temp)
                right = middle - 1;
            else
                left = middle + 1;
        }

        for (let j = i - 1; j >= left; j--) {
            arr[j + 1] = arr[j];
        }

        arr[left] = temp;
    }
    return arr
}

sort-merge.js

// 归并排序
// 每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
// https://www.cnblogs.com/chengxiao/p/6194356.html
function mergeSort(arr, l, r) {
  if (arr.length < 2) return arr

  const mid = Math.round(arr.length / 2)
  return merge(
    mergeSort(arr.slice(0, mid)),
    mergeSort(arr.slice(mid))
  )
}
// 有序数组的合并
function merge(a1, a2) {
  if (a1.length === 0) return a2
  if (a2.length === 0) return a1
  if (a1[0] > a2[0]) {
    return [a2[0], ...merge(a1, a2.slice(1))]
  }
  return [a1[0], ...merge(a2, a1.slice(1))]
}

sort-quick.js

// 快排
function quickSort(arr) {
  if (arr.length < 2) return arr
  const pivot = arr[0]
  const left = []
  const right = []
  const mid = [pivot]

  for (let i = 1, num; i < arr.length; i++) {
    num = arr[i]
    if (num > pivot) {
      right.push(num)
    } else if (num < pivot) {
      left.push(num)
    } else {
      mid.push(num)
    }
  }
  return quickSort(left).concat(mid, quickSort(right))
}

// in-place sort
function sortInPlace(arr) {
  select(arr, 0, arr.length - 1)
  return arr

  function select(arr, start, end) {
    if (start >= end) return
    const i = partition(arr, start, end)
    select(arr, i + 1, end)
    select(arr, start, i - 1)
  }

  function partition(arr, start, end) {
    const m = start + Math.floor(Math.random() * (end - start + 1))
    swap(arr, end, m)
    const val = arr[end]
    let j = start
    for(let i = start; i < end; i++) {
      if(arr[i] <= val) {
        swap(arr, i , j)
        j++
      }
    }
    swap(arr, j, end)
    return j
  }

  function swap(arr, i, j) {
    const tmp = arr[i]
    arr[i] = arr[j]
    arr[j] = tmp
  }
}

sort-selection.js

/**
 * 选择排序
 */
let selectionSort = (arr) => {
    for (let i = 0, l = arr.length - 1; i < l; i++) {
        let min = i
        // ***j<=l***
        for(let j = i + 1; j <= l; j++) {
            if (arr[j] < arr[min]) {
                min = j
            }
        }
        [arr[i], arr[min]] = [arr[min], arr[i]]
        console.log(arr)
    }
    return arr
}

exports.selectionSort = selectionSort