JS 排序算法：冒泡、选择、插入、归并、快速、希尔、堆、计数

返回：函数算法 | 返回 js 常见方法

1. 冒泡排序算法实现（javascript）

//冒泡排序算法(javascript)
//author：Hengda
//arr数组
//mode  false 升序 ture 降序
function bubbleSort( arr, mode ){

    var i, j, temp, len = arr.length;
    for( i = len - 1 ; i > 0; i-- ){
        for( j = 0; j < i; j++ ){
            if( mode ? arr[ j + 1 ] < arr[ j ] : arr[ j + 1 ] > arr[ j ] ){
                temp = arr[ j + 1 ];
                arr[ j + 1 ] = arr[ j ];
                arr[ j ] = temp;
            }
        }
    }
    return arr;
}
2. 计数排序算法实现（javascript）

//计数排序算法(javascript)
//author：Hengda
//arr数组
//mode  false 升序 ture 降序
function countingSort( arr, mode ){
    //i,j为控制变量，temp为交换变量，len为数组的长度
    var i, j, temp, len = arr.length;
    var countArr = [];//用于原始数组中统计各元素出现的次数
    var fillPos;//标记下一个回填位置
    var countArrLen;//计数数组的长度
    //统计
    for( i = 0; i < len; i++ ){
        if( countArr[ arr[ i ] ] != null ){
            countArr[ arr[ i ] ] ++;
        }else{
            countArr[ arr[ i ] ] = 1;
        }
    }

    //将数据重新排列回填到原始数组中
    //统计
    var fillPos = 0;//回填起始位置
    var countArrLen = countArr.length;

    if( mode ){
        //
        for( i = countArrLen - 1; i >=0; i-- ){
            //
            if( countArr[ i ] != null ){
                //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
                for( j = 0; j < countArr[ i ]; j++ ){
                    arr[ fillPos++ ] = i;
                }
            }
        }

    }else{
        //
        for( i = 0; i < countArrLen; i++ ){
            //
            if( countArr[ i ] != null ){
                //回填countArr[ i ]个当前值i到原始数组，回填起始位置为fillPos
                for( j = 0; j < countArr[ i ]; j++ ){
                    arr[ fillPos++ ] = i;
                }
            }
        }
    }

    //排序完成
    return arr;
}

3. 堆排序算法实现（javascript）

//功能：     堆排序(javascript)
//author：   Hengda
//arr：      待排序数组
//mode：     true 从大到小排序，false 从小到大排序
function heapSort(arr, mode) {
  var len = arr.length; //数组的长度
  var temp; //用于交换节点值
  var endHeapNodeNo; //堆末尾节点在数组中的下标

  //将数组调整为二叉堆
  for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapNodeSink(arr, i, len, mode);
  }

  for (var heapLen = len; heapLen > 0; heapLen--) {
    endHeapNodeNo = heapLen - 1; //堆的最后一个节点的序号

    //交换堆顶和堆尾元素
    temp = arr[endHeapNodeNo];
    arr[endHeapNodeNo] = arr[0];
    arr[0] = temp;

    //对除了堆尾元素组成的堆进行堆顶下沉操作
    heapNodeSink(arr, 0, heapLen - 1, mode);
  }
  return arr;
}

//堆中某节点按升序或者降序递归下沉
//author：   Hengda
//arr：      待排序数组
//nodeNo：   二叉树中指定节点的序号/堆数组中的下标
//heapLen：  堆的长度
//mode：     true 大的下沉，false 小的下沉
function heapNodeSink(arr, nodeNo, heapLen, mode) {
  var leftChild = (nodeNo + 1) * 2 - 1; //做孩子
  var rightChild = leftChild + 1; //右孩子
  var maxminNo = nodeNo; //最大值的序号
  var temp; //用户变量值得交换

  if (mode) {
    //
    if (heapLen > leftChild && arr[maxminNo] > arr[leftChild]) {
      maxminNo = leftChild; //更新最大节点序号
    }
    if (heapLen > rightChild && arr[maxminNo] > arr[rightChild]) {
      maxminNo = rightChild; //更新最大节点序号
    }
  } else {
    if (heapLen > leftChild && arr[maxminNo] < arr[leftChild]) {
      maxminNo = leftChild; //更新最大节点序号
    }
    if (heapLen > rightChild && arr[maxminNo] < arr[rightChild]) {
      maxminNo = rightChild; //更新最大节点序号
    }
  }

  //最大值所在节点有变化，则交换
  if (maxminNo != nodeNo) {
    //交换
    temp = arr[maxminNo];
    arr[maxminNo] = arr[nodeNo];
    arr[nodeNo] = temp;

    //继续下沉操作
    heapNodeSink(arr, maxminNo, heapLen, mode);
  }
}

4. 插入排序算法实现（javascript）

//插入排序算法(javascript)
//算法原理
//author：Hengda
//2020/1/25
//arr 待排序数组
//mode true 从大到小排列，false 从小到大排列
function insertionSort(arr, mode) {
  var i,
    j,
    temp,
    len = arr.length; //len为待排序数组长度 temp为交换变量 i j为控制变量。

  //从数组的第二个元素开始逐个往后处理。
  for (i = 1; i < len; i++) {
    //将当前被处理元素值记录下来。
    temp = arr[i];
    //以下标倒序逐一比较当前元素位置之前的所有元素，如果比当前元素大，则逐一向后覆盖一个元素。
    for (j = i - 1; j >= 0 && (mode ? arr[j] < temp : arr[j] > temp); j--) {
      arr[j + 1] = arr[j];
    }
    //将点前被处理元素的值填入最终空缺的位置即 （j + 1） 注意这个 j 已经被for循环做了-1操作，所以这里需要+1。
    arr[j + 1] = temp;
  }

  //遍历完成后，整个数组即为有序数组。
  return arr;
}

5. 归并排序算法实现（javascript）

//归并排序算法(javascript)
//author：Hengda
//arr数组
//start 数组中待排序段落的起止位置，len为数据段的长度
//mode  false 升序 ture 降序
function mergeSort(arr, start, len, mode) {
  var i, j, temp;

  //计算左侧数据段的位置和长度
  var lstart = start;
  var llen = Math.floor(len / 2);

  //计算右侧数据段的位置和长度
  var rstart = lstart + llen;
  var rlen = len - llen;

  //分别对左右分段进行进行插入排序
  if (llen > 4) mergeSort(arr, lstart, llen);
  if (rlen > 4) mergeSort(arr, rstart, rlen);

  //对当前数据段进行插入排序
  for (i = start + 1; i < len + start; i++) {
    temp = arr[i];
    for (j = i - 1; j >= start && (mode ? arr[j] < temp : arr[j] > temp); j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = temp;
  }
  return arr;
}

6. 选择排序算法实现（javascript）

//选择排序算法(javascript)
//author：Hengda
//arr数组
//mode  false 升序 ture 降序
function selectionSort(arr, mode) {
  //i,j为控制变量，miniMaxNo为标记发现的最大或者最小元素的下标，temp为交换变量，len为数组的长度
  var i,
    j,
    minMaxNo,
    temp,
    len = arr.length;
  //
  for (i = 0; i < len; i++) {
    //当前位置初始为最小或最大数的位置
    minMaxNo = i;
    //遍历后续所有元素与minMaxNo对应的元素做比较，如果比minMaxNo大或者小，则更新minMaxNo的值为新元素的下标
    for (j = i; j < len; j++) {
      if (mode ? arr[j] > arr[minMaxNo] : arr[j] < arr[minMaxNo]) {
        minMaxNo = j;
      }
    }
    //将最终确定的最大或者最小值与当前被处理位置i对应的元素值做交换
    temp = arr[minMaxNo];
    arr[minMaxNo] = arr[i];
    arr[i] = temp;
  }
  //排序完成
  return arr;
}

7. 希尔排序算法实现（javascript）

//希尔排序算法(javascript)
//author：Hengda
//arr数组
//mode  false 升序 ture 降序
function shellSort(arr, mode) {
  //1,j,k为控制变量，gap为分组间隙初始化为1，temp用于交换数据，len数组的长度
  var i,
    j,
    k,
    gap = 1,
    temp,
    len = arr.length;
  //计算合适的分组元素间隙，这里计算得到gap的最大值，这里的5也可以是其他数，值不同，实际排序速度也不同
  while (gap < len / 5) {
    gap = gap * 5 + 1;
  }

  //开始排序
  while (gap > 0) {
    //以下按分组排序，该排序原理为插入排序，如看不明白，可参考插入排序算法逻辑
    for (i = gap; i < len; i++) {
      temp = arr[i];
      for (
        j = i - gap;
        j >= 0 && (mode ? arr[j] < temp : arr[j] > temp);
        j -= gap
      ) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }

    //缩小分组间隔值
    gap = Math.floor(gap / 5);
  }

  return arr;
}

8. 快速排序算法实现（javascript）

//快速排序(javascript)
//author：Hengda
//arr数组
//start 待排序数据段的起始下标（含）
//end 待排序数据段终止下标（含）
//mode false 升序 ture 降序
function quickSort(arr, start, end, mode) {
  var i, j, temp;
  var divValue;

  if (start < end) {
    //初始化基准值
    baseValue = arr[end];
    j = start;

    //遍历整段数据元素，小于等于基准值的放在基准准直左侧（正序），大于等于基准值的放在基准值左侧（倒序）
    for (i = start; i <= end; i++) {
      //与基准值作比较
      if (mode ? arr[i] >= baseValue : arr[i] <= baseValue) {
        //从左端开始依次排列放置，当前排列位置为$j，把原位置的元素向后交换
        temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        //更新下一个应排列的位置
        j++;
      }
    }
    //循环中$j在最后的++操作并未使用，这里需要减去，使$j正确标记左右分界元素
    j--;

    //分界元素在两端是，则靠近分界元素的一端无需再排序
    //分界元素也无需再参与排序，因为左侧的一定小于等于分界元素，右侧的也一定大于等于分界元素
    //分别对分界元素左右两侧的数据段继续排序
    if (j > start) quickSort(arr, start, j - 1, mode);
    if (j < end) quickSort(arr, j + 1, end, mode);
  }
  return arr;
}