冒泡排序

重复地访问过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

  1. var arr = [3, 4, 1, 2];
  2. function bubbleSort2(arr) {
  3.   for (var j = 0; j < arr.length - 1; j++) {
  4.     // 这里要根据外层for循环的 j，逐渐减少内层 for循环的次数
  5.     for (var i = 0; i < arr.length - 1 - j; i++) {
  6.       if (arr[i] > arr[i + 1]) {
  7.         [arr[i] ,arr[i + 1]] = [arr[i + 1], arr[i]];
  8.       }
  9.     }
  10.   }
  11.   return arr;
  12. }

冒泡排序例子

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

  1. function SelectSort(arr){
  2.     let minIndex;
  3.   for(let i = 0; i < arr.length; i++){
  4.       minIndex = i;
  5.     for(let j = i + 1; j < arr.length; j++){
  6.         if(arr[j] < arr[minIndex]){
  7.           minIndex = j
  8.       }
  9.     }
  10.     [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]
  11.   }
  12.   return arr
  13. }
  14. console.log(SelectSort([4,1,2,4,7,89,3,2]))

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向扫描

  1. function insertSort(arr){
  2.     for(let i = 1; i < arr.length; i++){
  3.       let key = arr[i];
  4.     let j = i - 1;
  5.     while(j >= 0 && arr[j] > key){
  6.         arr[j + 1] = arr[j];
  7.       j--;
  8.     }
  9.     arr[j + 1] = key;
  10.   }
  11.   return arr
  12. }
  13. console.log(insertSort([4,1,2,4,7,89,3,2]))

归并排序

采用分治法，将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

  1. function mergeSort(arr) {
  2.   var len = arr.length
  3.   if (len < 2) {
  4.      return arr
  5.   }
  6.   var middle = Math.floor(len / 2);
  7.   var left = arr.splice(0, middle);
  8.   var right = arr
  9.   return merge(mergeSort(left), mergeSort(right));
  10. }
  12. function merge(left, right) {
  13.   var result = [];
  14.   while (left.length && right.length) {
  15.     if(left[0] <= right[0]) {
  16.       result.push(left.shift())
  17.     } else {
  18.       result.push(right.shift());
  19.     }
  20.   }
  21.   return result.concat(left, right);
  22. }
  24. console.log(mergeSort([4,1,2,4,7,89,3,2]))

快速排序

通过一趟排序将待拍记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

  1. function quickSort(arr){
  2.     if(arr.length <= 1){
  3.       return arr;
  4.   }
  5.   let pivotIndex = Math.floor(arr.length / 2);
  6.   let pivot = arr.splice(pivotIndex, 1)[0];
  7.   let left = [];
  8.   let right = [];
  9.   for(let i = 0; i < arr.length; i++){
  10.       if(arr[i] < pivot){
  11.         left.push(arr[i]);
  12.     } else {
  13.         right.push(arr[i])
  14.     }
  15.   }
  16.   return [...quickSort(left), pivot, ...quickSort(right)];
  17. }
  18. console.log(quickSort([4,1,2,4,7,89,3,2]))