排序算法是最常见的算法,V8引擎中Array中使用的sort方法是经过优化的,是综合快速排序和插入排序的优化方法。
排序算法的演进大概是7种。

js实现的7种排序算法

冒泡排序

冒泡排序,算是最原始的排序。

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j+1]) { //相邻元素两两对比
        var temp = arr[j+1]; //元素交换
        arr[j+1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));

遍历每一个元素,每循环一次将最大数通过交换置于当前循环的最后一个位置,冒泡排序是稳定的,平均的算法复杂度为o(n2)。

插入排序

插入排序,可以这么理解,在一个数组中我们不知道哪个是最小值,那么就假定第一个就是最小值,然后取第二个值与第一个值比较产排序后的序列,然后再取第三个值与排序后的序列进行比较插入到对应的位置,依次类推。

function insertionSort(array) {
  console.time('插入排序耗时:');
  for (var i = 1; i < array.length; i++) {
    var key = array[i];
    var j = i - 1;
    while ( array[j] > key) {
      array[j + 1] = array[j];
         j--;
    }
    array[j + 1] = key;
  }
  console.timeEnd('插入排序耗时:');
  return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertionSort(arr));

插入排序是稳定的,平均时间复杂度为o(n2)。

选择排序

选择排序,类似于冒泡排序,但是在每次循环的过程中,先找到最小数的位置,然后再与本轮循环的最前数进行交换。

function selectionSort(arr) {
  var len = arr.length;
  var minIndex, temp;
  console.time('选择排序耗时');
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) { //寻找最小的数
        minIndex = j; //将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  console.timeEnd('选择排序耗时');
  return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(selectionSort(arr));

选择排序是不稳定的,时间复杂度同样是o(n2)。

希尔排序

希尔排序是插入排序的改进版本,在每次循环的比较过程中,增加了一层增量的概念。然而增量的选择,以及时间复杂度的最优的证明上依然是一个数学难题,一般我们选择二分增量。

function shellSort(arr) {
  var len = arr.length,
  temp,
  gap = 1;
  console.time('希尔排序耗时:');
  while(gap < len/5) { //动态定义间隔序列
    gap =gap*5+1;
  }
  for (gap; gap > 0; gap = Math.floor(gap/5)) {
    for (var i = gap; i < len; i++) {
      temp = arr[i];
      for (var j = i-gap; j >= 0 && arr[j] > temp; j-=gap) {
        arr[j+gap] = arr[j];
      }
      arr[j+gap] = temp;
    }
  }
  console.timeEnd('希尔排序耗时:');
  return arr;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(shellSort(arr));

希尔排序是不稳定的,但是在时间复杂度是第一次突破n2,进入o(nlogn)的时代。

归并排序

归并排序其实可以类比二分法,二分法其实就是二等分的意思,简而言之就是不断和新序列的中间值进行比较。归并排序似乎有异曲同工之妙,什么意思呢,就是将一个原始序对等分为两部分,然后不断地对等分新的序列,直至序列的长度为1或者2,那么想,如果一个序列为1,那就没有比较的意义了,它本身就是之最,如果是两个呢,那直接比较不就完了,把比较之后的值推送到一个新的数组。就这样不断地细分,不断的产生子序列,然后把穿产生的新序列作为新的父序列,然后同等级的父序列再比较产生新的祖序列,依次类推。

function mergeSort(arr) { //采用自上而下的递归方法
  var len = arr.length;
  if(len < 2) {
    return arr;
  }
  var middle = Math.floor(len / 2),
  left = arr.slice(0, middle),
  right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right){
  var result = [];
  console.time('归并排序耗时');
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }
  while (left.length){
    result.push(left.shift());
  }
  while (right.length){
    result.push(right.shift());
  }
  console.timeEnd('归并排序耗时');
  return result;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));

归并排序也是不稳定的,时间复杂度为o(nlogn)。

快速排序

快速排序是生活中比较常用的一种排序算法,它的特点就像名字一样速度快、效率高。快速排序采用的思想是分治思想,先简单的介绍一下分治的思想。分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。

这里采用的是左右指针方法,左右指针法实现思路:在一段区间内我们有一个值key,从左边区间进行遍历,直到找到一个大于key的值就停下,然后再从右边找小于key的值,找到一个也停下来。我们将左右的值进行交换,这样左边那个大于key的值就被换到了右边,而右边那个比key小的值就被换到了左边。当左右两个指针相遇的时候就说明所有元素都与key做过了比较。然后再将左指针所在的元素赋值给key。此时按照上述方法进行递归实现[left, key]和[key+1, right]。

function quickSort(array, left, right) {
  console.time('1.快速排序耗时');
  if (left < right) {
    var x = array[right], i = left - 1, temp;
    for (var j = left; j <= right; j++) {
      if (array[j] <= x) {
        i++;
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
    console.log(array) ;
    console.log(left,i) ;
    quickSort(array, left, i - 1);
    console.log(array)
    console.log(i,right)
    quickSort(array, i + 1, right);
  }
  console.timeEnd('1.快速排序耗时');
  console.log(array)
  return array;
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));

快速排序的是目前使用最为广泛的排序算法,同样也是不稳定的,时间复杂度为o(nlogn)。

堆排序

堆排序通过建堆,再对堆进行排序。首先明白什么是堆,堆其实可以这么理解,类似金字塔,一层有一个元素,两层有两个元素,三层有四个元素,每层从数组中取元素,从左到右的顺序放到堆相应的位置上,也就是说每一层元素个数为2n-1 ;(n 代表行数),这就完成了建堆。
这里的堆排序使用的是最大堆,即n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为最大堆(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)。

function heapSort(array) {
  console.time('堆排序耗时');
  //建堆
  var heapSize = array.length, temp;
  for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {  
    heapify(array, i, heapSize);
  }
  //堆排序
  for (var j = heapSize - 1; j >= 1; j--) {
    temp = array[0];
    array[0] = array[j];
    array[j] = temp;
    console.log(array)
    heapify(array, 0, --heapSize);
  }
  console.timeEnd('堆排序耗时');
  return array;
}
function heapify(arr, x, len) {
  var l = 2 * x + 1, r = 2 * x + 2, largest = x, temp;
  if (l < len && arr[l] > arr[largest]) {
    largest = l;
  }
  if (r < len && arr[r] > arr[largest]) {
    largest = r;
  }
  if (largest != x) {
    temp = arr[x];
    arr[x] = arr[largest];
    arr[largest] = temp;
    console.log(arr)
    heapify(arr, largest, len);
  }
}
var arr=[91,60,96,13,35,65,46,65,10,30,20,31,77,81,22];
console.log(heapSort(arr));

堆排序和归并排序有点类似,都是细分到最小单元,从最小单元比较,但是同归并排序有两大点不同,一是堆排序并不像归并那么无序,只是一味的平分数组,而堆排序则是按原始序列排出金字塔式的结构,把最大值一层层往上冒,冒到金字塔最顶端的时候把它踢出来,这样达到排序的效果。
堆排序的时间是不稳定的,时间复杂度同样是o(nlogn)。

写在最后:

排序算法的实现多种多样,这里例举了7种最为基本的排序算法,通过几天的学习,基本可以拿到即可手写代码,算是算法启蒙吧,前端路,徐徐行。