js排序的几种方式有哪些（前端常见的几种排序算法）

总结几种排序算法。算法在任何一门编程语言都可以实现，学好算法重点是思想，而不是语言，我们这里使用js进行演示。

当然js内部也提供了Array.prototype.sort方法进行排序我们不做具体介绍，详见：
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

1.冒泡排序

实现原理：

1.依次比较相邻的两个数，如果第1个值大于第2个值，交换位置。如果第1个值小于第2个值，不交换位置。一轮下来，最后一个是最大的数
2.每下一轮开始除了最后一个之外的数重复第一步，直到只剩一个数

如图所示：

冒泡排序

代码：

function bubbleSort(array){
  var len = array.length;
  var i;
  var j;
  var stop;

  for (i = 0; i < len - 1; i++){
    for (j = 0, stop = len - 1 - i; j < stop; j++){
      if (array[j] > array[j + 1]){
        exchange(array, j, j + 1);
      }
    }
  }
  return array;
}

function exchange(array, p1, p2){
  var temp = array[p1];
  array[p1] = array[p2];
  array[p2] = temp;
}

2.快速排序

实现原理：

1.以一个数为基准(中间的数)，比基准小的放到左边，比基准大的放到右边
2.再按此方法对这两部分数据分别进行快速排序（递归原理）
3.不能再分后退出递归，并重新将数组合并

如图所示:

快速排序

代码：

var quickSort = function(array) {　　
// 当被分的数组只剩一个时，退出递归
if (array.length <= 1) {
return array;
   }

// 中间基准值的index
var middleIndex = Math.floor(array.length / 2);　　
// 基准值
var middle = array.splice(middleIndex, 1)[0];　　
var left = [];　　
var right = [];　　
// 小的放左边，大的放右边
for (var i = 0; i < array.length; i++) {　　　　
    if (array[i] < middle) {　　
          left.push(array[i]);　
    } else {
          right.push(array[i]);　
       }　　
   }　　
// 递归
// 把数组合并在一起
  return quickSort(left).concat([middle], quickSort(right));
};

3.选择排序

实现原理：

1.找出最小的数，和第一个交换位置
2.在剩下的数中，找出最二小的数，放在第二个
3.依次类推，排出顺序

如图所示：

选择排序

代码：

function selectSort(array){

    var len = array.length,
        min;

    for (i=0; i < len; i++){
        // 将当前位置设为最小值
        min = i;

        // 检查数组其余部分是否更小
        for (j=i+1; j < len; j++){
            if (array[j] < array[min]){
                min = j;
            }
        }

        // 如果当前位置不是最小值，将其换为最小值
        if (i != min){
            exchange(array, i, min);
        }
    }

    return array;
}
function exchange(array, p1, p2){
    var temp = array[p1];
    array[p1] = array[p2];
    array[p2] = temp;
}

4.插入排序

实现原理：

1.把数组分为[已排序]和[未排序]两部分,第一个数为[已排序]，其余为[未排序]
2.从[未排序]抽出第一个数，和[已排序]部分比较，插入到合适的位置

如图所示：

插入排序

代码：

function insertSort(array) {

    var len  = array.length,     // 数组长度
        value,                      // 当前比较的值
        i,                          // 未排序部分的当前位置
        j;                          // 已排序部分的当前位置
    for (i=0; i < len; i++) {
        // 储存当前位置的值
        value = array[i];
        /*
         * 当已排序部分的当前元素大于value，
         * 就将当前元素向后移一位，再将前一位与value比较
         */
        for (j=i-1; j > -1 && array[j] > value; j--) {
            array[j+1] = array[j];
        }
        array[j+1] = value;
    }

    return array;
}

5.合并排序

实现原理：

1.不断将数组对半分，直到每个数组只有一个
2.将分出来的部分重新合并
3.合并的时候按顺序排列

如图所示：

合并排序

// 被拆分的数组重新合并
function merge(left, right) {
    var result = [],
        left_index = 0,
        right_index = 0;

    // 将两个数组合并
    // 合并的时候按从小到大的顺序
    while (left_index < left.length && right_index < right.length) {
        if (left[left_index] < right[right_index]) {
            result.push(left[left_index++]);
        } else {
            result.push(right[right_index++]);
        }
    }

    // 和其他数组拼接
    return result.concat(left.slice(left_index)).concat(right.slice(right_index));
}

function mergeSort(array) {
    // 只有一个数的时候退出递归
    if (array.length < 2) {
        return array;
    }

    var middle = Math.floor(array.length / 2),
        left = array.slice(0, middle),
        right = array.slice(middle);

    // 递归
    // 不断拆分只到一个数组只有一个数
    return merge(mergeSort(left), mergeSort(right));
}