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

/********* 1、冒泡排序 **********/
// 很常見很容易理解的排序算法， 排序思路：遍歷數組，每次遍歷就將最大（或最?。┲低浦磷钋啊Ｔ酵蟊闅v查詢次數越少
const bubbleSort = arr => {
 const list = arr.slice(); //保證函數為純函數
 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、改進版冒泡排序 **********/
// 對上述冒泡排序的一種優化， 優化思路：當一次遍歷前后數組不產生變化時，說明該數組已經有序，結束排序。
const bubbleSort2 = arr => {
 const list = arr.slice(); //保證函數為純函數
 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、選擇排序 **********/
// 在無序區中選出最小的元素，然后將它和無序區的第一個元素交換位置。
const selectionSort = arr => {
 const list = arr.slice(); //保證函數為純函數
 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、直接插入排序 **********/
// 每次選擇無序區第一個元素插入到有序區，并排序
const insertSort = arr => {
 const list = arr.slice(); //保證函數為純函數
 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、二分插入排序 **********/
// 插入排序的一種優化實現， 通過二分法減少遍歷時間（以前是從某邊開始依次比較，現在從中間開始比較，減少比較次數）
// 注意，數組很大才能提現二分插入的優勢
const insertSort2 = arr => {
 const list = arr.slice(); //保證函數為純函數
 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(); //為了保證這個函數是純函數，拷貝一次數組
 if (list.length <= 1) return list;
 const pivot = list.splice(0, 1)[0]; //選第一個作為基數，并把基數從數組里面刪除
 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],那么后面循環的時候要從i=1開始
const quickSort2 = arr => {
 const list = arr.slice(); //為了保證這個函數是純函數，拷貝一次數組
 if (list.length <= 1) return list;
 const pivot = list[0]; //選第一個作為基數
 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() // 為了保證這個函數是純函數拷貝一次數組
 const sort = (arr, left = 0, right = arr.length - 1) => {
 if (left >= right) {//如果左邊的索引大于等于右邊的索引說明整理完畢
 return;
 }
 let i = left;
 let j = right;
 const baseVal = arr[j]; // 取無序數組最后一個數為基準值
 while (i < j) { //把所有比基準值小的數放在左邊大的數放在右邊
 while (i < j && arr[i] <= baseVal) { //找到一個比基準值大的數交換
 i++;
 }
 arr[j] = arr[i]; // 將較大的值放在右邊如果沒有比基準值大的數就是將自己賦值給自己（i 等于 j）
 while (j > i && arr[j] >= baseVal) { //找到一個比基準值小的數交換
 j--;
 }
 arr[i] = arr[j]; // 將較小的值放在左邊如果沒有找到比基準值小的數就是將自己賦值給自己（i 等于 j）
 }
 arr[j] = baseVal; // 將基準值放至中央位置完成一次循環（這時候 j 等于 i ）
 sort(arr, left, j - 1); // 將左邊的無序數組重復上面的操作
 sort(arr, j + 1, right); // 將右邊的無序數組重復上面的操作
 }
 sort(list);
 return list;
}

/********* 8、希爾排序 **********/
// 排序思路：先將整個待排序記錄序列分割成若干個子序列，在序列內分別進行直接插入排序，待整個序列基本有序時，再對全體記錄進行一次直接插入排序。
const shellSort = arr => {
 const list = arr.slice(); //保證函數為純函數
 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');

// 交換下標為i,k的數組元素
[list[k], list[i]] = [list[i], list[k]];