常用排序算法

2023 年 2 月 25 日 星期六
/ ,
26

常用排序算法

封装 ArrayList 类

通过封装 ArrayList，我们可以让所有排序算法作为其原型方法对其内部数组进行统一验证，而不用写多个函数一个个测试。

class ArrayList {
  constructor() {
    this.arr = [];
  }
  push(value) {
    this.arr.push(value);
  }
  toString() {
    return this.arr.join(',');
  }
// 把数组的第i项和第j项交换位置
  swap(i, j) {
    this.arr[i] = [this.arr[j], (this.arr[j] = this.arr[i])][0];
  }
}

冒泡排序

在排序算法中属于执行效率较低的方法，但也最容易理解，通过当前项和下一项的两两比较，如果当前项比下一项要大(或小)，就与之交换位置，并且循环多次直至排序完成。就像冒泡泡慢慢冒出水面一样。

算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示

bubbleSort.gif
bubbleSort.gif

算法实现

// 冒泡排序
bubbleSort() {
  let len = this.arr.length;
  for (let i = 0; i < len - 1; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (this.arr[j] > this.arr[j + 1]) {
        this.swap(j, j + 1);
      }
    }
  }
}

选择排序

选择排序是一种原地比较排序算法，它会在未排序的部分找到最小（或最大）元素，然后放到起始位置。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

动图演示

selectionSort.gif
selectionSort.gif

算法实现

selectionSort() {
  let len = this.arr.length;
  for (let i = 0; i < len - 1; i++) {
    let minIndex = i;
    for (let j = i + 1; j < len; j++) {
      if (this.arr[j] < this.arr[minIndex]) {
        minIndex = j;
      }
    }
    this.swap(i, minIndex);
  }
}

插入排序

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

insertionSort() {
  let len = this.arr.length;
  for (let i = 1; i < len; i++) {
    let preIndex = i - 1;
    let current = this.arr[i];
    while (preIndex >= 0 && this.arr[preIndex] > current) {
      this.arr[preIndex + 1] = this.arr[preIndex];
      preIndex--;
    }
    this.arr[preIndex + 1] = current;
  }
}

希尔排序

希尔排序是插入排序的一种更高效的改进版本，也称为缩小增量排序。

shellSort() {
  let len = this.arr.length;
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    for (let i = gap; i < len; i++) {
      let j = i;
      let current = this.arr[i];
      while (j - gap >= 0 && current < this.arr[j - gap]) {
        this.arr[j] = this.arr[j - gap];
        j -= gap;
      }
      this.arr[j] = current;
    }
  }
}

归并排序

归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个典型应用。

mergeSort() {
  const merge = (left, right) => {
    const result = [];
    while (left.length && right.length) {
      if (left[0] < right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    return result.concat(left, right);
  };

  const sort = (arr) => {
    if (arr.length < 2) {
      return arr;
    }
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    return merge(sort(left), sort(right));
  };

  this.arr = sort(this.arr);
}

快速排序

快速排序是一种分而治之的算法，它把大的拆分为小的，小的拆分为更小的。

quickSort() {
  const sort = (arr) => {
    if (arr.length < 2) { return arr; }
    let pivot = arr[0];
    let left = [];
    let right = [];
    for (let i = 1; i < arr.length; i++) {
      if (arr[i] < pivot) {
        left.push(arr[i]);
      } else {
        right.push(arr[i]);
      }
    }
    return sort(left).concat([pivot], sort(right));
  };

  this.arr = sort(this.arr);
}

堆排序

堆排序是一种基于比较的排序算法，通过构建二叉堆，可以利用堆的特性进行高效的元素选择。

heapSort() {
  let len = this.arr.length;

  const heapify = (arr, i, len) => {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let largest = i;
    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }
    if (right < len && arr[right] > arr[largest]) {
      largest = right;
    }
    if (largest !== i) {
      this.swap(i, largest);
      heapify(arr, largest, len);
    }
  };

  // 构建堆
  for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
    heapify(this.arr, i, len);
  }

  // 从堆中逐个取出元素
  for (let i = len - 1; i > 0; i--) {
    this.swap(0, i);
    heapify(this.arr, 0, i);
  }
}

计数排序

计数排序是一种非基于比较的排序算法，适用于一定范围内的整数排序。

countingSort() {
  let maxValue = Math.max(...this.arr);
  let bucket = new Array(maxValue + 1).fill(0);
  let sortedIndex = 0;

  this.arr.forEach((num) => {
    bucket[num]++;
  });

  bucket.forEach((count, num) => {
    while (count > 0) {
      this.arr[sortedIndex++] = num;
      count--;
    }
  });
}

桶排序

桶排序是计数排序的扩展，它将元素分散到多个有序的桶中。

bucketSort(bucketSize = 5) {
  if (this.arr.length === 0) {
    return;
  }

  let i;
  let minValue = this.arr[0];
  let maxValue = this.arr[0];
  for (i = 1; i < this.arr.length; i++) {
    if (this.arr[i] < minValue) {
      minValue = this.arr[i];
    } else if (this.arr[i] > maxValue) {
      maxValue = this.arr[i];
    }
  }

  // 初始化桶
  const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
  let buckets = new Array(bucketCount);
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  // 将元素分配到各个桶中
  for (i = 0; i < this.arr.length; i++) {
    buckets[Math.floor((this.arr[i] - minValue) / bucketSize)].push(this.arr[i]);
  }

  // 对每个桶进行排序，然后合并到原数组
  this.arr.length = 0;
  for (i = 0; i < buckets.length; i++) {
    buckets[i].sort((a, b) => a - b); // 对每个桶内部进行排序
    for (let j = 0; j < buckets[i].length; j++) {
      this.arr.push(buckets[i][j]);
    }
  }
}

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数进行比较排序。

radixSort() {
  const getMax = (arr) => Math.max(...arr);
  const digitCount = (num) => (num === 0 ? 1 : Math.floor(Math.log10(Math.abs(num))) + 1);
  const getDigit = (num, i) => Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;

  let max = getMax(this.arr);
  let maxDigitCount = digitCount(max);

  for (let k = 0; k < maxDigitCount; k++) {
    let digitBuckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < this.arr.length; i++) {
      let digit = getDigit(this.arr[i], k);
      digitBuckets[digit].push(this.arr[i]);
    }
    this.arr = [].concat(...digitBuckets);
  }
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...