/*
 * @Author: laifeipeng 
 * @Date: 2019-02-20 10:00:36 
 * @Last Modified by: laifeipeng
 * @Last Modified time: 2019-02-21 11:57:58
 */

/********* 1、冒泡排序 **********/
// 很常見很容易理解的排序算法， 排序思路：遍歷數(shù)組，每次遍歷就將最大（或最?。┲低浦磷钋?。越往后遍歷查詢次數(shù)越少
const bubbleSort = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 for (let i = 0; i < len; i++) {
 for (let j = len - 1; j > i; j--) {
  if (list[j] < list[j - 1]) {
  [list[j - 1], list[j]] = [list[j], list[j - 1]];
  }
 }
 }
 return list;
}

/********* 2、改進(jìn)版冒泡排序 **********/
// 對上述冒泡排序的一種優(yōu)化， 優(yōu)化思路：當(dāng)一次遍歷前后數(shù)組不產(chǎn)生變化時，說明該數(shù)組已經(jīng)有序，結(jié)束排序。
const bubbleSort2 = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 for (let i = 0; i < len; i++) {
 let exchange = false;
 for (let j = len - 1; j > i; j--) {
  if (list[j] < list[j - 1]) {
  [list[j - 1], list[j]] = [list[j], list[j - 1]];
  exchange = true;
  }
 }
 if (!exchange) return list
 }
 return list;
}

/********* 3、選擇排序 **********/
// 在無序區(qū)中選出最小的元素，然后將它和無序區(qū)的第一個元素交換位置。
const selectionSort = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 for (let i = 0; i < len; i++) {
 let k = i
 for (let j = len - 1; j > i; j--) {
  if (list[j] < list[k]) k = j;
 }
 if (k !== i) {
  [list[k], list[i]] = [list[i], list[k]];
 }
 }
 return list;
}

/********* 4、直接插入排序 **********/
// 每次選擇無序區(qū)第一個元素插入到有序區(qū)，并排序
const insertSort = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 for (let i = 1; i < len; i++) {
 const tmp = list[i];
 let j = i - 1;
 while (j >= 0 && tmp < list[j]) {
  list[j + 1] = list[j];
  j--;
 }
 list[j + 1] = tmp;
 }
 return list;
}

/********* 5、二分插入排序 **********/
// 插入排序的一種優(yōu)化實現(xiàn)， 通過二分法減少遍歷時間（以前是從某邊開始依次比較，現(xiàn)在從中間開始比較，減少比較次數(shù)）
// 注意，數(shù)組很大才能提現(xiàn)二分插入的優(yōu)勢
const insertSort2 = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 for (let i = 1; i < len; i++) {
 const tmp = list[i];
 let low = 0;
 let high = i - 1;
 let j = i - 1;
 while (low <= high) {
  const mid = ~~((low + high) / 2);
  if (tmp < list[mid]) {
  high = mid - 1;
  } else {
  low = mid + 1;
  }
 }
 while (j > high) {
  list[j + 1] = list[j];
  j--;
 }
 list[j + 1] = tmp;
 }
 return list;
}

/********* 6、快速排序 **********/
const quickSort1 = arr => {
 const list = arr.slice(); //為了保證這個函數(shù)是純函數(shù)，拷貝一次數(shù)組
 if (list.length <= 1) return list;
 const pivot = list.splice(0, 1)[0]; //選第一個作為基數(shù)，并把基數(shù)從數(shù)組里面刪除
 const left = [];
 const right = [];
 for (let i = 0, len = list.length; i < len; i++) { //從0開始
 if (list[i] < pivot) {
  left.push(list[i]);
 } else {
  right.push(list[i]);
 }
 }
 return [...quickSort(left), pivot, ...quickSort(right)];
}

// 上面const pivot = list.splice(0, 1)[0]; 如果想直接改為list[0],那么后面循環(huán)的時候要從i=1開始
const quickSort2 = arr => {
 const list = arr.slice(); //為了保證這個函數(shù)是純函數(shù)，拷貝一次數(shù)組
 if (list.length <= 1) return list;
 const pivot = list[0]; //選第一個作為基數(shù)
 const left = [];
 const right = [];
 for (let i = 1, len = list.length; i < len; i++) { //從1開始
 if (list[i] < pivot) {
  left.push(list[i]);
 } else {
  right.push(list[i]);
 }
 }
 return [...quickSort(left), pivot, ...quickSort(right)];
}

/********* 7、原地算法快速排序 **********/
const quickSort = arr => {
 const list = arr.slice() // 為了保證這個函數(shù)是純函數(shù)拷貝一次數(shù)組
 const sort = (arr, left = 0, right = arr.length - 1) => {
 if (left >= right) {//如果左邊的索引大于等于右邊的索引說明整理完畢
  return;
 }
 let i = left;
 let j = right;
 const baseVal = arr[j]; // 取無序數(shù)組最后一個數(shù)為基準(zhǔn)值
 while (i < j) {   //把所有比基準(zhǔn)值小的數(shù)放在左邊大的數(shù)放在右邊
  while (i < j && arr[i] <= baseVal) { //找到一個比基準(zhǔn)值大的數(shù)交換
  i++;
  }
  arr[j] = arr[i]; // 將較大的值放在右邊如果沒有比基準(zhǔn)值大的數(shù)就是將自己賦值給自己（i 等于 j）
  while (j > i && arr[j] >= baseVal) { //找到一個比基準(zhǔn)值小的數(shù)交換
  j--;
  }
  arr[i] = arr[j]; // 將較小的值放在左邊如果沒有找到比基準(zhǔn)值小的數(shù)就是將自己賦值給自己（i 等于 j）
 }
 arr[j] = baseVal; // 將基準(zhǔn)值放至中央位置完成一次循環(huán)（這時候 j 等于 i ）
 sort(arr, left, j - 1); // 將左邊的無序數(shù)組重復(fù)上面的操作
 sort(arr, j + 1, right); // 將右邊的無序數(shù)組重復(fù)上面的操作
 }
 sort(list);
 return list;
}

/********* 8、希爾排序 **********/
// 排序思路：先將整個待排序記錄序列分割成若干個子序列，在序列內(nèi)分別進(jìn)行直接插入排序，待整個序列基本有序時，再對全體記錄進(jìn)行一次直接插入排序。
const shellSort = arr => {
 const list = arr.slice(); //保證函數(shù)為純函數(shù)
 const len = list.length;
 let gap = ~~(len / 2);
 while (gap > 0) {
 for (let i = gap; i < len; i++) {
  const tmp = list[i];
  let j = i - gap;
  while (j >= 0 && tmp < list[j]) {
  list[j + gap] = list[j];
  j = j - gap;
  }
  list[j + gap] = tmp;
 }
 gap = ~~(gap / 2);
 }
 return list;
}

const logStep = (i, leftArr, rightArr) => 
console.log(`%c 第${i}趟排序：%c ${arrStr(leftArr)} %c${arrStr(rightArr)} `, 'color:green', 'color:red', 'color:blue');

// 交換下標(biāo)為i,k的數(shù)組元素
[list[k], list[i]] = [list[i], list[k]];