((arr) => {
    for(let i=0;i<arr.length;i++){
        for(let j=i+1;j<arr.length;j++){
            if(arr[j]<arr[i]){//从左往右升序排列
                //交换位置
                let tmp=arr[i];
                arr[i]=arr[j];
                arr[j] = tmp;
            }
        }
    }
    console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]

((arr) => {
    let N = arr.length;
    for(let i=0;i<N;i++){
        let min=arr[i+1],minIndex=i+1;//记录第(i+1)~(N-1)项中的最小值以及对应的索引
        for(let j=i+1;j<N;j++){
            if(arr[j]<min){//从左往右升序排列
                minIndex=j;
                min = arr[j];
            }            
        }
        if (arr[minIndex] < arr[i]) {
            //交换位置
            let tmp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tmp;
        }
    }
    console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>>[1,2,4,5,7,8,9]

//todo

((arr) => {
    var result = [];
​
    buildMinHeap(arr);
​
    for (let i = 0, length = arr.length; i < length; i++) {        
        //将堆（完全二叉树）的根结点拿走，放入result数组，此时result是已排序好的。
        result.push(arr[0]);
​
        //将堆（完全二叉树）的根结点和最末尾的结点交换
        swap(0, length-result.length);        
        //然后下沉，重排树，让根节点是最小的。注意【数组范围】是length-result.length
        sink(arr, 0, length - result.length);
    }
​
    //根据给定的数组建一个最小堆
    function buildMinHeap(arr) {
        let length = arr.length;
        let currentIndex;//当前要处理的下沉结点对应的数组索引
        //请注意，currentIndex为什么是从 Math.floor((length - 2) / 2) 开始？
        //读者可以画个草稿图归纳一下。
        //这会让算法的循环次数由N次变为logN，这正是堆排序更高效的关键所在。
        for (currentIndex = Math.floor((length - 2) / 2); currentIndex >= 0; currentIndex--) {
            console.log("正在处理的下沉结点索引为:"+currentIndex);
            sink(arr, currentIndex, length);
        }
    }
​
    /**
     * 下沉算法
     * @param arr 数组
     * @param currentIndex 要处理的结点的索引，该结点有子结点
     * @param length 数组范围
     */
    function sink(arr, currentIndex, length) {
​
        let minIndex=currentIndex;//较小值的索引，默认为currentIndex
​
        let leftChildIndex  = 2*currentIndex+1;//完全二叉树 左子结点索引
        let rightChildIndex = 2*currentIndex+2;//完全二叉树 右子结点索引
​
        //左侧下沉
        if(leftChildIndex < length && arr[leftChildIndex] < arr[minIndex])
            minIndex = leftChildIndex;
​
        //右侧下沉
        if (rightChildIndex < length && arr[rightChildIndex] < arr[minIndex])
            minIndex = rightChildIndex;
​
        if(minIndex!=currentIndex){
            swap(minIndex,currentIndex);
            //递归，继续下沉，时间复杂度为O(N)
            sink(arr,minIndex,length);
        }
    }
​
    //交换位置
    function swap(x, y) {
        let tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
​
    console.log(result);
​
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]

((arr) => {
   /**
   * @param    left    数组的最左侧项的索引
   * @param    right    数组的最右侧项的索引
   */
   function quicksort(left, right) {
      let i/*左指针索引*/, j/*右指针索引*/, temp/*基准数*/;
      if (left > right)
         return;
      temp = arr[left];//取数组第一个项为基准数
      i = left;
      j = right;
      while (i != j) { //若左右两个指针没碰头        
         while (arr[j] >= temp && i < j)//顺序很重要，要先从右边开始找，直到找到比temp小的为止
            j--;
         while (arr[i] <= temp && i < j)//再找左边的，直到找到比temp大的数为止
            i++;
         if (i < j)//交换这两个数在数组中的位置，让小的在左边，大的在右边
         {
            let t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
         }
      }
      //然后将基准数与小的数换位，将小的数放在最左边，基准数放中间
      arr[left] = arr[i];
      arr[i] = temp;
      
      quicksort(left, i - 1);//递归。继续处理左边的，这里是一个递归的过程
      quicksort(i + 1, right);//递归。继续处理右边的 ，这里是一个递归的过程
   }
​
   quicksort(0, arr.length - 1);
   console.log(arr);
})([1, 5, 4, 2, 9, 7, 8]);//>> [1, 2, 4, 5, 7, 8, 9]