十大经典算法JavaScript实现

Ai 摘要：本文介绍了三种经典排序算法的JavaScript实现：冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换将最大值逐步移至末尾；选择排序每次遍历选择最小值放到已排序序列末尾；插入排序则将未排序元素插入到已排序序列的合适位置。每种算法均配有思路说明、动态演示图和完整代码实现，其中冒泡排序还提供了优化版本。这些算法适用于小型数据集排序，时间复杂度均为O(n²)。

一，冒泡排序

冒泡排序即把最小的元素经过交换位置慢慢浮到前端。

思路1，从左到右依次比较相邻元素的大小，把较大的元素放到右边。 2，从第一组即索引为0，1的元素开始比较，大的放右边。再比较索引为1，2的元素。经过一轮，数组的最右边是该数组的最大值。 3，重复上一步的步骤，前一轮得到的最大值不参与比较。 4，按照上述规则，每一轮会减少一个元素，直至排列完成。

演示

Description

代码实现

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

function bubbleSort(arr) {
  let temp = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}
console.log(bubbleSort(arr));
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];

优化

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

function bubbleSort(arr) {
  let temp = 0;
  for (let i = 0; i < arr.length - 1; i++) {
    // 记录是否发生位置交换
    let isExchange = false;
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        isExchange = true;
      }
    }
    // 如果没有发生交换也就是本次遍历始终 arr[j] <= arr[j + 1]
    if (!isExchange) {
      break;
    }
  }
  return arr;
}
console.log(bubbleSort(arr)); 
//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];

二，选择排序

每次遍历选择一个最小值放到最前方。

思路

1，在未排序序列中找到一个最小值放到排序序列的起始位置。
2，在剩余未排序序列中继续寻找最小值放到已排序列的末尾端。
3，重复n次。

演示

Description

代码实现

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 找到最小值，保存下来最小值和其索引
    let nth = i,
      num = arr[i],
      temp = 0;
    for (let j = i + 1; j < arr.length; j++) {
      if (num > arr[j]) {
        num = arr[j];
        nth = j;
      }
    }
    // 交换两个值
    if (i !== nth) {
      temp = arr[i];
      arr[i] = arr[nth];
      arr[nth] = temp;
    }
  }
  return arr;
}
console.log(selectionSort(arr));
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50];

三，插入排序

在未排序的数据中从后往前找，找到合适的位置插入

思路

1，将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2，从头到尾依次扫描未排序序列，将扫描到的每个元素与有序序列的每个元素进行比较，小于哪个有序序列的元素就进行交换，相当于插入到该元素索引位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

演示

Description

代码实现

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
function insertionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let num = arr[i],
      j = i;
    while (num < arr[j - 1] && j > 0) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = num;
  }
  return arr;
}
console.log(insertionSort(arr));