# 排序算法

// 冒泡排序，两层循环
function bubbleSort(arr){
  var len = arr.length
  for(var i = len - 1;i > 0;i--){
    for(var j = 0;j < i;j++){
      if(arr[j] > arr[j + 1]){
        var tmp = arr[j]
        arr[j] = arr[j + 1]
        arr[j + 1] = tmp
      }
    }
  }
  return arr;
}

function selectSort(array) {
  var length = array.length, i, j, minIndex, minValue, temp;
  for (i = 0; i < length - 1; i++) {
    minIndex = i;
    minValue = array[minIndex];
    for (j = i + 1; j < length; j++) {//通过循环选出最小的
      if (array[j] < minValue) {
        minIndex = j;
        minValue = array[minIndex];
      }
    }
    // 交换位置
    temp = array[i];
    array[i] = minValue;
    array[minIndex] = temp;
  }
  return array
}

function insertSort(arr) {
  for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
    for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
      if(arr[j] < arr[j-1]) {
        [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
      } else {
        break;
      }
    }
  }
  return arr;
}

function shellSort(arr,gap) {
    //为了方便观察过程，使用时去除
    console.log(arr)
    //最外层循环，一次取不同的步长，步长需要预先给出
    for(let i = 0; i<gap.length; i++) {  
        let n = gap[i]; //步长为n
        //接下类和插入排序一样，j循环依次取后面的数
        for(let j = i + n; j < arr.length; j++) { 
          //k循环进行比较，和直接插入的唯一区别是1变为了n
            for(let k = j; k > 0; k-=n) { 
                if(arr[k] < arr[k-n]) {
                    [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                    console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)
                    //为了观察过程
                } else {
                    continue;
                }
            }
        }
    }
    return arr;
}
var arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];
var gap = [3,2,1];
console.log(shellSort(arr,gap))

// 假设有以下数组，对其进行归并排序使其按从小到大的顺序排列：
var arr = [8,7,6,5];
// 对其进行分解，得到两个数组：
[8,7]和[6,5]
// 然后继续进行分解，分别再得到两个数组，直到数组只包含一个元素：
[8]、[7]、[6]、[5]
// 开始合并数组，得到以下两个数组：
[7,8]和[5,6]
// 继续合并，得到
[5,6,7,8]
// 排序完成

function mergeSort(arr) {
    function main(arr) {
        // 记得添加判断，防止无穷递归导致callstack溢出，此外也是将数组进行分解的终止条件。
        if(arr.length === 1) return arr;
        // 从中间开始分解，并构造左边数组和右边数组。
        let mid = Math.floor(arr.length/2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);
        // 开始递归调用。
        return merge(arguments.callee(left), arguments.callee(right));
    }
    // 数组的合并函数，left是左边的有序数组，right是右边的有序数组。
    function merge(left, right) {
        // il是左边数组的一个指针，rl是右边数组的一个指针。
        let il = 0,
            rl = 0,
            result = [];
        // 同时遍历左右两个数组，直到有一个指针超出范围。
        while(il < left.length && rl < right.length) {
            //count++;
            // 左边数组的当前项如果小于右边数组的当前项，那么将左边数组的当前项推入result，反之亦然，同时将推入过的指针右移。
            if(left[il] < right[rl]) {
                result.push(left[il++]);
            }
            else {
                result.push(right[rl++]);
            }
        }
        // 记得要将未读完的数组的多余部分读到result。
        return result.concat(left.slice(il)).concat(right.slice(rl));
    }
    return main(arr)
}

// 数组
var arr = [1,2,3,4,5,6,7];
// 堆结构
        1
      /   \
    2       3
  /   \   /   \
4      5 6     7

function heapSort(arr) {
    //console.time('HeapSort');
    buildHeap(arr);
    for(let i=arr.length-1; i>0; i--) {
        // 从最右侧的叶子节点开始，依次与根节点的值交换。
        [arr[i], arr[0]] = [arr[0], arr[i]];
        // 每次交换之后都要重新构建堆结构，记得传入i限制范围，防止已经交换的值仍然被重新构建。
        heapify(arr, i, 0);
    }
    //console.timeEnd('HeapSort');
    return arr;
    function buildHeap(arr) {
        // 可以观察到中间下标对应最右边叶子节点的父节点。
        let mid = Math.floor(arr.length / 2);
        for(let i=mid; i>=0; i--) {
            // 将整个数组构建成堆结构以便初始化。
            heapify(arr, arr.length, i);
        }
        return arr;
    }
    // 从i节点开始下标在heapSize内进行堆结构构建的函数。
    function heapify(arr, heapSize, i) {
        // 左子节点下标。
        let left = 2 * i + 1,
            // 右子节点下标。
            right = 2 * i + 2,
            // 假设当前父节点满足要求（比子节点都大）。
            largest = i;
        // 如果左子节点在heapSize内，并且值大于其父节点，那么left赋给largest。
        if(left < heapSize && arr[left] > arr[largest]) {
            largest = left;
        }
        // 如果右子节点在heapSize内，并且值大于其父节点，那么right赋给largest。
        if(right < heapSize && arr[right] > arr[largest]) {
            largest = right;
        }
        if(largest !== i) {
            // 如果largest被修改了，那么交换两者的值使得构造成一个合格的堆结构。
            [arr[largest], arr[i]] = [arr[i], arr[largest]];
            // 递归调用自身，将节点i所有的子节点都构建成堆结构。
            arguments.callee(arr, heapSize, largest);
        }
        return arr;
    }
}