原创 六种前端排序算法代码演示

排序算法是前端算法中一个十分经典的算法，因此它也是前端面试中常见的考察重点。如今前端行业火爆，就业市场对前端人才的要求也越来越高，排序算法是每个前端从业者都必须掌握的基础知识。众所周知，排序算法有六种，分别是冒泡排序、选择排序、快速排序、归并排序、基数排序。下面我为大家逐一用代码演示这六大排序算法，感兴趣的朋友一起来看看吧！

 

1、冒泡排序

（1）概念

冒泡排序，顾名思义，就像鱼吐泡泡，泡泡越往上越大。第一次循环，开始比较当前元素与下一个元素的大小，如果比下一个元素小或者相等，则不需要交换两个元素的值；若比下一个元素大的话，则交换两个元素的值。然后，遍历整个数组，第一次遍历完之后，相同操作遍历第二遍。

（2）性能

时间复杂度：平均时间复杂度是O(n^2)；空间复杂度：由于辅助空间为常数，所以空间复杂度是O(1)。

（3）代码演示

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function bubbleSort(arr){

  for(let i = 0; i < arr.length - 1; i++){

    for(let j = 0; j < arr.length - i - 1; j++){

      if(arr[j] > arr[j + 1]){

        swap(arr, j, j+1);

      }

    }

  }

  return arr;

}

function swap(arr, i, j){

  let temp = arr[i];

  arr[i] = arr[j];

  arr[j] = temp;

}

console.log(arr);

2、选择排序

（1）概念

选择排序，即每次都选择最小的，然后换位置。第一遍，从数组中选出最小的，与第一个元素进行交换；第二遍，从第二个元素开始，找出最小的，与第二个元素进行交换；依次循环，完成排序。

（2）性能

时间复杂度：平均时间复杂度是O(n^2)，这是一个不稳定的算法，因为每次交换之后，它都改变了后续数组的顺序。空间复杂度：辅助空间是常数，空间复杂度为O(1)。

（3）代码演示

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function swap(arr, i, j){

  var temp = arr[i];

  arr[i] = arr[j];

  arr[j] = temp;

}

function selectionSort(arr){

  for(let i = 0; i < arr.length - 1; i++){

    let index = i;

    for(let j = i+1; j < arr.length; j++){

      if(arr[index] > arr[j]){

        index = j;

      }

    }

    swap(arr, i, index);

  }

  return arr;

}

console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ] 

3、插入排序

（1）概念

插入排序就是将元素插入到已排序好的数组中。首先，循环原数组，然后，将当前位置的元素，插入到之前已排序好的数组中，依次操作。

（2）性能

时间复杂度：平均算法复杂度为O(n^2)；空间复杂度：辅助空间为常数，空间复杂度是O(1)。

（3）代码演示

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];

function insertSort(arr){

  for(let i = 0; i < arr.length; i++){

    let temp = arr[i];

    for(let j = 0; j < i; j++){

      if(temp < arr[j] && j === 0){

        arr.splice(i, 1);

        arr.unshift(temp);

        break;

      }else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){

        arr.splice(i, 1);

        arr.splice(j+1, 0, temp);

        break;

      }

    }

  }

  return arr;

}

console.log(insertSort(arr));  //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

4、快速排序

（1）概念

快速排序，从它的名字就应该知道它很快，时间复杂度很低，性能很好。它将排序算法的时间复杂度降低到O。

（2）性能

时间复杂度：平均时间复杂度O(nlogn)，只有在特殊情况下会是O(n^2)，不过这种情况非常少；空间复杂度：辅助空间是logn，所以空间复杂度为O。

（3）代码演示

const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];

function quickSort(arr){

  if(arr.length <= 1){

    return arr;

  }

  let temp = arr[0];

  const left = [];

  const right = [];

  for(var i = 1; i < arr.length; i++){

    if(arr[i] > temp){

      right.push(arr[i]);

    }else{

      left.push(arr[i]);

    }

  }

  return quickSort(left).concat([temp], quickSort(right));

}

console.log(quickSort(arr));

5、归并排序

（1）概念

归并排序，即将数组分成不同部分，然后注意排序之后，进行合并。首先，将相邻的两个数进行排序，形成n/2对，然后在每两对进行合并，不断重复，直至排序完。

（2）性能

时间复杂度：平均时间复杂度是O；空间复杂度：辅助空间为n，空间复杂度为O(n)。

（3）代码演示

//迭代版本

const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

function mergeSort(arr){

  const len = arr.length;

  for(let seg = 1; seg < len; seg += seg){

    let arrB = [];

    for(let start = 0; start < len; start += 2*seg){

      let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);

      let start1 = start, end1 = mid;

      let start2 = mid, end2 = heig;

      while(start1 < end1 && start2 < end2){

        arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);

      }

      while(start1 < end1){

        arrB.push(arr[start1++]);

      }

      while(start2 < end2){

        arrB.push(arr[start2++]);

      }

    }

    arr = arrB;

  }

  return arr;

}

console.log(mergeSort(arr));

6、基数排序

（1）概念

基数排序，就是将数的每一位进行一次排序，最终返回一个正常顺序的数组。首先，比较个位的数字大小，将数组的顺序变成按个位依次递增的，之后再比较十位，再比较百位的，直至最后一位。

（2）性能

时间复杂度：平均时间复杂度O(k*n)，最坏的情况是O(n^2)。

（3）代码演示

const arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127, 10000];

function radixSort(arr){

  let maxNum = Math.max(...arr);

  let dis = 0;

  const len = arr.length;

  const count = new Array(10);

  const tmp = new Array(len);

  while(maxNum >=1){

    maxNum /= 10;

    dis++;

  }

  for(let i = 1, radix = 1; i <= dis; i++){

    for(let j = 0; j < 10; j++){

      count[j] = 0;

    }

    for(let j = 0; j < len; j++){

      let k = parseInt(arr[j] / radix) % 10;

      count[k]++;

    }

    for(let j = 1; j < 10; j++){

      count[j] += count[j - 1];

    }

    for(let j = len - 1; j >= 0 ; j--){

      let k = parseInt(arr[j] / radix) % 10;

      tmp[count[k] - 1] = arr[j];

      count[k]--;

    }

    for(let j = 0; j < len; j++){

      arr[j] = tmp[j];

    }

    radix *= 10;

  }

  return arr;

}

console.log(radixSort(arr));

以上就是六种前端排序算法的代码演示，大家都看明白了吗？排序算法是前端学习中的基础部分，只要大家明白它的原理，再多动手敲敲代码，相信掌握前端排序算法并不困难。如果大家喜欢本篇文章，欢迎关注博学谷资讯栏目，本栏目将每天为大家更新更多的前端资讯。