排序算法

简单插入排序

function insertSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    if (arr[i] < arr[i - 1]) {
      let current = i - 1 // the position need to move
      let temp = arr[i] // the value need to insert
      arr[i] = arr[current]
      while (temp < arr[current]) {
        arr[current + 1] = arr[current] // move backward
        current--
      }
      arr[current + 1] = temp
    }
  }
}
let arr = [6, 7, 2, 3, 1, 5, 4]
insertSort(arr)
console.log(arr)

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

希尔排序

由于 JavaScript 的数据都是用浮点数存储的，所以需要用到parseInt()

function shellSort(arr) {
  let dert = parseInt(arr.length / 2)
  while (dert >= 1) {
    shellInsertSort(arr, dert)
    dert = parseInt(dert / 2) // compute the shell step
  }
}
function shellInsertSort(arr, dert) {
  for (let i = dert, len = arr.length; i < len; i++) {
    if (arr[i] < arr[i - dert]) {
      let current = i - dert
      let temp = arr[i]
      arr[i] = arr[current]
      while (temp < arr[current]) {
        arr[current + dert] = arr[current]
        current -= dert
      }
      arr[current + dert] = temp
    }
  }
}
let arr = [6, 7, 2, 3, 1, 4, 5]
shellSort(arr)
console.log(arr)

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

简单选择排序

function minIndex(arr, start) {
  // find the mini index
  let min = start
  for (let i = start + 1, len = arr.length; i < len; i++) {
    if (arr[min] > arr[i]) min = i
  }
  return min
}
function selectSort(arr) {
  let key = 0
  for (let i = 0, len = arr.length; i < len; i++) {
    key = minIndex(arr, i)
    if (key != i) {
      // if the mini index is not the current index then exchange value
      ;[arr[key], arr[i]] = [arr[i], arr[key]]
    }
  }
}
let arr = [6, 7, 2, 3, 1, 4, 5]
selectSort(arr)
console.log(arr)

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

堆排序

function heapAdjust(arr, index, length) {
// adjust the heap
let temp = arr[index],
child = index _ 2 + 1;
while (child < length) {
if (child + 1 < length && arr[child] < arr[child + 1]) {
// find the more big child
child++;
}
if (arr[index] < arr[child]) {
// exchange the parentNode and the childNode
arr[index] = arr[child];
index = child;
child = index _ 2 + 1;
} else {
break;
}
}
arr[index] = temp;
}
function buildHeap(arr) {
// create the heap
let len = arr.length;
for (let i = (arr.length - 1) / 2; i >= 0; i--) {
heapAdjust(arr, i, len);
}
}
function heapSort(arr) {
buildHeap(arr);
for (let i = arr.length - 1; i >= 0; i--) {
// exchange the 0th value and ith value
[arr[i], arr[0]] = [arr[0], arr[i]];
heapAdjust(arr, 0, i);
}
}
let arr = [6, 7, 2, 3, 1, 4, 5];
heapSort(arr);
console.log(arr);

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

冒泡排序

function bubbleSort(arr) {
  let index = arr.length - 1
  while (index > 0) {
    let pos = 0
    for (let j = 0; j < index; j++) {
      if (arr[j] > arr[j + 1]) {
        pos = j
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
    index = pos
  }
}
let arr = [6, 7, 2, 3, 1, 4, 5]
bubbleSort(arr)
console.log(arr)

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

快速排序

function partition(arr, low, high) {
  let key = arr[low]
  while (low < high) {
    // from right to left to find a value that lower than key
    while (low < high && arr[high] >= key) high--
    ;[arr[low], arr[high]] = [arr[high], arr[low]]
    // from left to right to find a value thar large than key
    while (low < high && arr[low] <= key) low++
    ;[arr[low], arr[high]] = [arr[high], arr[low]]
  }
  return low
}
function quickSortFunc(arr, low, high) {
  if (low < high) {
    // binary iterations
    let local = partition(arr, low, high)
    quickSortFunc(arr, low, local - 1)
    quickSortFunc(arr, local + 1, high)
  }
}
function quickSort(arr) {
  quickSortFunc(arr, 0, arr.length - 1)
}
let arr = [6, 7, 2, 3, 1, 4, 5]
quickSort(arr)
console.log(arr)

结果：
Array(7) [1, 2, 3, 4, 5, 6, 7]

归并排序

function merge(arr1, arr2) {
  let result = [],
    length1 = arr1.length,
    length2 = arr2.length,
    index1 = 0,
    index2 = 0,
    reindex = 0
  while (index1 < length1 && index2 < length2) {
    if (arr1[index1] < arr2[index2]) {
      result[reindex++] = arr1[index1++]
    } else {
      result[reindex++] = arr2[index2++]
    }
  }
  while (index1 < length1) result[reindex++] = arr1[index1++]
  while (index2 < length2) result[reindex++] = arr2[index2++]

  return result
}
let arr1 = [2, 4, 6, 8, 10],
  arr2 = [1, 3, 5, 7, 9]
let result = merge(arr1, arr2)
console.log(result)

结果：
Array(10) [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]