排序算法

一、快速排序

快速排序是处理大数据最快的排序算法之一，它也是一种分而治之的算法，通过递归方式将数据依次分解为包含较小元素和较大元素的不同子序列，会不断重复这个步骤，直到所有的序列全部为有序的，最后将这些子序列一次拼接起来，就可得到排序好的数据。

该算法首先要从数列中选出一个元素作为基数（pivot）。接着所有的数据都将围绕这个基数进行，将小于改基数的元素放在它的左边，大于或等于它的数全部放在它的右边，对左右两个小数列重复上述步骤，直至各区间只有1个数。

function quickSort(arr) {
  if (arr.length < 2) return arr;
  let mid = Math.floor(arr.length / 2)
  let midValue = arr.splice(mid, 1)
  let left = [] 
  let right= [] 
  for (let i of arr) {
    if (i < midValue) {
      left.push(i)
    } else {
      right.push(i)
    }
  }
  return quickSort(left).concat(midValue, quickSort(right))
}
console.log(quickSort([2, 5, 7, 3, 1, 5, 8, 3, 9, 2, 0]))`

二、冒泡排序

冒泡排序是比较经典的算法之一，也是排序最慢的算法之一，因为它的实现是非常的容易的。

冒泡排序的算法思想如下（升序排序）：

  1. 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样最终最大数被交换到最后的位置
  3. 除了最后一个元素以外，针对所有的元素重复以上的步骤
  4. 重复步骤1~3，直到排序完成
function bubbleSort(arr) {
  let i = arr.length;
  for (i; i > 0; i--) {
    for (let j = 0; j < i - 1; j++) {
      console.log(j)
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}
console.log(bubbleSort([2, 4, 6, 80, 100, 5, 0]))

三、选择排序

选择排序是一种比较简单直观的排序算法。它的算法思想是，从数组的开头开始遍历，将第一个元素和其他元素分别进行比较，记录最小的元素，等循环结束之后，将最小的元素放到数组的第一个位置上，然后从数组的第二个位置开始继续执行上述步骤。当进行到数组倒数第二个位置的时候，所有的数据就完成了排序。

选择排序同样会用到嵌套循环，外循环从数组第一个位置移到倒数第二个位置；内循环从第二个位置移动到数组最后一个位置，查找比当前外循环所指向的元素还要小的元素，每次内循环结束后，都会将最小的值放到合适的位置上。

function selectionSort(arr) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let min = arr[i];
    let index = i;
    for (let j = i + 1; j < len; j++) {
      if (min > arr[j]) {
        min = arr[j];
        index = j;
      }
    }
    [arr[i], arr[index]] = [min, arr[i]];
  }
  return arr
}
console.log(selectionSort([2, 4, 6, 80, 100, 5, 0, 1]))

四、插入排序

插入排序有点类似人类按字母顺序对数据进行排序，就如同你打扑克牌一样，将摸来的扑克按大小放到合适的位置一样。它的原理就是通过嵌套循环，外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的元素进行比较；如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

实现步骤如下：

  1. 从第一个元素开始，该元素默认已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置
  6. 重复步骤2~5，直到排序完成
unction insertSort(arr) {
  let len = arr.length;
  for (let i = 1; i < len; i++) {
    let tmp = arr[i];
    let j = i - 1;
    while (j >= 0 && tmp < arr[j]) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = tmp
  }
  return arr
}
console.log(insertSort([2, 4, 6, 80, 100, 5, 0]))

五、归并排序

将两个的有序数列合并成一个有序数列，我们称之为"归并"，归并排序的思想就是将一系列排序好的子序列合并成一个大的完整有序的序列。

实现步骤如下：

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；
  2. 对这两个子序列分别采用归并排序；
  3. 将两个排序好的子序列合并成一个最终的排序序列
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr
  }
  let mid = Math.floor(arr.length / 2);
  let left = arr.slice(0, mid);
  let right = arr.slice(mid);
  return merge(mergeSort(left), mergeSort(right));

  function merge(left, right) {
    let result = [];
    while (left.length > 0 && right.length > 0) {
      if (left[0] > right[0]) {
        result.push(right.shift())
      } else {
        result.push(left.shift())
      }
    }
    return result.concat(left, right)
  }
}
console.log(mergeSort([2, 4, 6, 80, 100, 5, 0]))

results matching ""

    No results matching ""