关于算法:常见排序算法实现TS-版

1. 公共办法封装

• Comparator 实现见前文前端比拟办法的优雅封装
• MinHeap 实现见前文数据结构之 Heap 实现（TS 版）

1.1 排序 Class 实现

// utils/sort/Sort.ts

import Comparator, {TypeCompareParam} from '../comparator/Comparator'
import type {TypeCompareFun} from '../comparator/Comparator'

export interface ICallbacks {
  // If provided then all elements comparisons will be done through this callback.
  compareCallback?: TypeCompareFun
  // If provided it will be called each time the sorting function is visiting the next element.
  visitingCallback?: (a?: any) => void
}

export default class Sort {
  protected callbacks: ICallbacks
  protected comparator: Comparator

  constructor(originalCallbacks?: ICallbacks) {this.callbacks = Sort.initSortingCallbacks(originalCallbacks)
    this.comparator = new Comparator(this.callbacks.compareCallback)
  }

  static initSortingCallbacks(originalCallbacks: ICallbacks): ICallbacks {const callbacks = originalCallbacks || {}
    const stubCallback = () => {}

    callbacks.compareCallback = callbacks.compareCallback || undefined
    callbacks.visitingCallback = callbacks.visitingCallback || stubCallback

    return callbacks
  }

  public sort(array?: TypeCompareParam[]) {throw new Error('sort method must be implemented')
  }
}

1.2 数据交换

// utils/swap/swap.ts

import {TypeCompareParam} from '../comparator/Comparator'

// 通过解构运算符进行数据交换
// 本我的项目中采纳此形式
export function swap(arr: TypeCompareParam[], i: number, j: number) {;[arr[j], arr[i]] = [arr[i], arr[j]]
}

// 依据数组下标进行数据交换
// 此形式为传统实现形式
export function swap2(arr: TypeCompareParam[], i: number, j: number) {if (i === j) {return}
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

/**
 * 用异或运算符实现替换
 *
 * 因为是二进制操作，所以仅反对数字替换，这里用二进制示意其值
 * 如：A: 4(100), B: 2(010)，那么：* 第一次：A = A(100) ^ B(010) = 001
 * 第二次：B = A(001) ^ B(010) = 100
 * 第三次：A = A(001) ^ B(100) = 010
 *
 * 留神：此办法要求 i !== j，因为没有两头变量保留值，会导致如果是雷同索引的话，信息会失落
 */
export function swap3(arr: number[], i: number, j: number) {if (i === j) {return}
  arr[i] = arr[i] ^ arr[j]
  arr[j] = arr[i] ^ arr[j]
  arr[i] = arr[i] ^ arr[j]
}

2. 排序实现

2.1 冒泡排序（Bubble Sort）

冒泡排序，有时也称为下沉排序，是一种简略的排序算法，它重复遍历列表，比拟相邻元素并在它们的程序谬误时替换它们，直到列表被排序。
该算法是一种比拟排序，以较小或较大元素“冒泡”到列表顶部的形式命名。
这个算法，不是一种实用的排序算法，它在事实世界的应用中体现不佳，次要用作教育工具。

动画演示：

代码实现：

// sorting/bubble-sort/BubbleSort.ts
import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'
import {swap} from '../../utils/swap/swap'

export default class BubbleSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Flag that holds info about whether the swap has occur or not.
    let swapped = false
    // Clone original array to prevent its modification.
    const array = [...originalArray]

    for (let i = 1; i < array.length; i += 1) {
      swapped = false

      // Call visiting callback.
      this.callbacks.visitingCallback(array[i])

      for (let j = 0; j < array.length - i; j += 1) {
        // Call visiting callback.
        this.callbacks.visitingCallback(array[j])

        // Swap elements if they are in wrong order.
        if (this.comparator.lessThan(array[j + 1], array[j])) {swap(array, j, j + 1)

          // Register the swap.
          swapped = true
        }
      }

      // If there were no swaps then array is already sorted and there is no need to proceed.
      if (!swapped) {return array}
    }

    return array
  }
}

复杂度：

2.2 抉择排序（Selection Sort）

它具备 O(n2) 工夫复杂度，使其在大型列表上效率低下，并且通常比相似的插入排序体现更差。
抉择排序以其简略性着称，在某些状况下，特地是在辅助内存无限的状况下，它比更简单的算法具备性能劣势。

动画演示：

代码实现：

// sorting/selection-sort/SelectionSort.ts
import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'
import {swap} from '../../utils/swap/swap'

export default class SelectionSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Clone original array to prevent its modification.
    const array = [...originalArray]

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

      // Call visiting callback.
      this.callbacks.visitingCallback(array[i])

      // Find minimum element in the rest of array.
      for (let j = i + 1; j < array.length; j += 1) {
        // Call visiting callback.
        this.callbacks.visitingCallback(array[j])

        if (this.comparator.lessThan(array[j], array[minIndex])) {minIndex = j}
      }

      // If new minimum element has been found then swap it with current i-th element.
      if (minIndex !== i) {swap(array, i, minIndex)
      }
    }

    return array
  }
}

复杂度计算：

比拟的总数是：

通过 等差数列求和 失去：

稳定性剖析：

抉择排序是不稳固的。

算法的稳定性定义为，对于待排序列中雷同项的原来秩序不能被算法扭转则称该算法稳固。
比方待排序列为:(2) 3 6 [2] 4 5 ...序列中的 (2) 排在 [2] 后面，不能因为算法把 [2] 排到 (2) 后面。

抉择排序算法，举个简略的例子，就晓得它是否稳固。
例如:(7) 2 5 9 3 4 [7] 1 ...当咱们利用抉择排序算法进行升序排序时候，(7)和 1 调换，(7)就跑到了 [7] 的前面了，原来的秩序扭转了，这样就不稳固了。

复杂度：

2.3 插入排序（Insertion Sort）

插入排序是一种简略的排序算法，它一次构建一个最终排序的数组（或列表）。
与更高级的算法（如疾速排序、堆排序或合并排序）相比，它在大型列表上的效率要低得多。

动画演示：

代码实现：

// sorting/insertion-sort/InsertionSort.ts
import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'
import {swap} from '../../utils/swap/swap'

export default class InsertionSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {const array = [...originalArray]

    // Go through all array elements...
    for (let i = 1; i < array.length; i += 1) {
      let currentIndex = i

      // Call visiting callback.
      this.callbacks.visitingCallback(array[i])

      // Check if previous element is greater than current element.
      // If so, swap the two elements.
      while (array[currentIndex - 1] !== undefined &&
        this.comparator.lessThan(array[currentIndex], array[currentIndex - 1])
      ) {
        // Call visiting callback.
        this.callbacks.visitingCallback(array[currentIndex - 1])

        // Swap the elements.
        swap(array, currentIndex, currentIndex - 1)

        // Shift current index left.
        currentIndex -= 1
      }
    }

    return array
  }
}

复杂度：

2.4 堆排序（Heap Sort）

堆排序是一种基于 比拟 的排序算法。堆排序能够被认为是一种改良的抉择排序。与抉择排序一样，堆排序将其输出分为已排序和未排序区域，并通过从中提取最大元素并将其插入已排序区域来迭代地放大未排序区域。与抉择排序不同，堆排序不会浪费时间对未排序区域进行线性工夫扫描；相同，堆排序在堆数据结构中保护未排序区域，以便在每个步骤中更快地找到最大元素。
首先将列表转换为最大堆来筹备列表。而后，该算法反复地将列表的第一个值与最初一个值替换，将堆操作中思考的值范畴缩小一个，并将新的第一个值筛选到其在堆中的地位。反复此过程，直到堆列表为空。

动画演示：

代码实现：

// sorting/heap-sort/HeapSort.ts

import MinHeap from '../../data-structures/heap/MinHeap'
import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'

export default class HeapSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {const sortedArray = []
    const minHeap = new MinHeap(this.callbacks.compareCallback)

    // Insert all array elements to the heap.
    originalArray.forEach((element) => {
      // Call visiting callback.
      this.callbacks.visitingCallback(element)

      minHeap.add(element)
    })

    // Now we have min heap with minimal element always on top.
    // Let's poll that minimal element one by one and thus form the sorted array.
    while (!minHeap.isEmpty()) {const nextMinElement = minHeap.poll()

      // Call visiting callback.
      this.callbacks.visitingCallback(nextMinElement)

      sortedArray.push(nextMinElement)
    }

    return sortedArray
  }
}

复杂度剖析：

这张图显示了自下而上构建堆（“heapify”）与自上而下构建堆之间的工夫复杂度差别。
每个圆圈中的数字示意将相应节点增加到堆中所需的最大替换次数。
通过将两侧的数字相加，很显著，自下而上的构建次数比自上而下的次数少。

复杂度：

2.5 归并排序（Merge Sort）

归并排序是一种高效的、通用的、基于比拟的排序算法。
大多数实现都会产生稳固的排序，这意味着该实现会保留排序输入中相等元素的输出程序。
是一种分而治之的算法。

动画演示：

代码实现：

// sorting/merge-sort/MergeSort.ts

import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'

export default class MergeSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Call visiting callback.
    this.callbacks.visitingCallback(null)

    // If array is empty or consists of one element then return this array since it is sorted.
    if (originalArray.length <= 1) {return originalArray}

    // Split array on two halves.
    const middleIndex = Math.floor(originalArray.length / 2)
    const leftArray = originalArray.slice(0, middleIndex)
    const rightArray = originalArray.slice(middleIndex, originalArray.length)

    // Sort two halves of split array
    const leftSortedArray = this.sort(leftArray)
    const rightSortedArray = this.sort(rightArray)

    // Merge two sorted arrays into one.
    return this.mergeSortedArrays(leftSortedArray, rightSortedArray)
  }

  mergeSortedArrays(leftArray: TypeCompareParam[], rightArray: TypeCompareParam[]): TypeCompareParam[] {const sortedArray: TypeCompareParam[] = []

    // Use array pointers to exclude old elements after they have been added to the sorted array.
    let leftIndex = 0
    let rightIndex = 0

    while (leftIndex < leftArray.length && rightIndex < rightArray.length) {
      let minElement = null

      // Find the minimum element between the left and right array.
      if (this.comparator.lessThanOrEqual(leftArray[leftIndex], rightArray[rightIndex])) {minElement = leftArray[leftIndex]
        // Increment index pointer to the right
        leftIndex += 1
      } else {minElement = rightArray[rightIndex]
        // Increment index pointer to the right
        rightIndex += 1
      }

      // Add the minimum element to the sorted array.
      sortedArray.push(minElement)

      // Call visiting callback.
      this.callbacks.visitingCallback(minElement)
    }

    // There will be elements remaining from either the left OR the right
    // Concatenate the remaining elements into the sorted array
    return sortedArray.concat(leftArray.slice(leftIndex)).concat(rightArray.slice(rightIndex))
  }
}

复杂度：

2.6 疾速排序（Quick Sort）

疾速排序是一种分而治之的算法。
疾速排序首先将一个大数组分成两个较小的子数组：低元素和高元素。而后疾速排序能够递归地对子数组进行排序。

步骤是：

1. 从数组中抉择一个元素，称为枢轴。
2. 分区：对数组从新排序，使所有值小于枢轴的元素都在枢轴之前，而所有值大于枢轴的元素都在它之后（相等的值能够去任何一种形式）。在此分区之后，枢轴处于其最终地位。这称为分区操作。
3. 递归地将上述步骤利用于具备较小值的元素的子数组，并别离利用于具备较大值的元素的子数组。

动画演示：

代码实现：

这里展现两种实现形式。

// sorting/quick-sort/QuickSort.ts

import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'

export default class QuickSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Clone original array to prevent it from modification.
    const array = [...originalArray]

    // If array has less than or equal to one elements then it is already sorted.
    if (array.length <= 1) {return array}

    // Init left and right arrays.
    const leftArray = []
    const rightArray = []

    // Take the first element of array as a pivot.
    const pivotElement = array.shift()
    const centerArray = [pivotElement]

    // Split all array elements between left, center and right arrays.
    while (array.length) {const currentElement = array.shift()

      // Call visiting callback.
      this.callbacks.visitingCallback(currentElement)

      if (this.comparator.equal(currentElement, pivotElement)) {centerArray.push(currentElement)
      } else if (this.comparator.lessThan(currentElement, pivotElement)) {leftArray.push(currentElement)
      } else {rightArray.push(currentElement)
      }
    }

    // Sort left and right arrays.
    const leftArraySorted = this.sort(leftArray)
    const rightArraySorted = this.sort(rightArray)

    // Let's now join sorted left array with center array and with sorted right array.
    return leftArraySorted.concat(centerArray, rightArraySorted)
  }
}

// sorting/quick-sort/QuickSortInPlace.ts

import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'
import {swap} from '../../utils/swap/swap'

export default class QuickSortInPlace extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  /** Sorting in place avoids unnecessary use of additional memory, but modifies input array.
   *
   * This process is difficult to describe, but much clearer with a visualization:
   * @see: http://www.algomation.com/algorithm/quick-sort-visualization
   */
  sort(originalArray: TypeCompareParam[],
    inputLowIndex = 0,
    inputHighIndex = originalArray.length - 1,
    recursiveCall = false
  ) {
    // Copies array on initial call, and then sorts in place.
    const array = recursiveCall ? originalArray : [...originalArray]

    /**
     * The partitionArray() operates on the subarray between lowIndex and highIndex, inclusive.
     * It arbitrarily chooses the last element in the subarray as the pivot.
     * Then, it partially sorts the subarray into elements than are less than the pivot,
     * and elements that are greater than or equal to the pivot.
     * Each time partitionArray() is executed, the pivot element is in its final sorted position.
     */
    const partitionArray = (lowIndex: number, highIndex: number) => {const pivot = array[highIndex]
      // visitingCallback is used for time-complexity analysis.
      this.callbacks.visitingCallback(pivot)

      let partitionIndex = lowIndex
      for (let currentIndex = lowIndex; currentIndex < highIndex; currentIndex += 1) {if (this.comparator.lessThan(array[currentIndex], pivot)) {swap(array, partitionIndex, currentIndex)
          partitionIndex += 1
        }
      }

      // The element at the partitionIndex is guaranteed to be greater than or equal to pivot.
      // All elements to the left of partitionIndex are guaranteed to be less than pivot.
      // Swapping the pivot with the partitionIndex therefore places the pivot in its
      // final sorted position.
      swap(array, partitionIndex, highIndex)

      return partitionIndex
    }

    // Base case is when low and high converge.
    if (inputLowIndex < inputHighIndex) {const partitionIndex = partitionArray(inputLowIndex, inputHighIndex)
      const RECURSIVE_CALL = true
      this.sort(array, inputLowIndex, partitionIndex - 1, RECURSIVE_CALL)
      this.sort(array, partitionIndex + 1, inputHighIndex, RECURSIVE_CALL)
    }

    return array
  }
}

复杂度：

2.7 希尔排序（Shell Sort）

希尔排序，是一种就地比拟排序。它能够被看作是插入排序的泛化。
该算法首先对彼此相距很远的元素对进行排序，而后逐步减小要比拟的元素之间的差距。
从相距很远的元素开始，它能够比简略的近邻替换更快地将一些不适合的元素挪动到适合的地位。

动画演示：

工作原理：

For our example and ease of understanding, we take the interval of 4.
Make a virtual sub-list of all values located at theinterval of 4 positions.
Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 44}:

We compare values in each sub-list and swap them (if necessary) in the original array.
After this step, the new array should look like this:

Then, we take interval of 2 and this gap generates two sub-lists {14, 27, 35, 42}, {19, 10, 33, 44}:

We compare and swap the values (uses insertion sort), if required, in the original array.
After this step, the array should look like this:

Finally, we sort the rest of the array using interval of value 1.
Shell sort uses insertion sort to sort the array.

代码实现：

// sorting/shell-sort/ShellSort.ts

import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'
import {swap} from '../../utils/swap/swap'

export default class ShellSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Prevent original array from mutations.
    const array = [...originalArray]

    // Define a gap distance.
    let gap = Math.floor(array.length / 2)

    // Until gap is bigger then zero do elements comparisons and swaps.
    while (gap > 0) {
      // Go and compare all distant element pairs.
      for (let i = 0; i < array.length - gap; i += 1) {
        let currentIndex = i
        let gapShiftedIndex = i + gap

        while (currentIndex >= 0) {
          // Call visiting callback.
          this.callbacks.visitingCallback(array[currentIndex])

          // Compare and swap array elements if needed.
          if (this.comparator.lessThan(array[gapShiftedIndex], array[currentIndex])) {swap(array, gapShiftedIndex, currentIndex)
          }

          gapShiftedIndex = currentIndex
          currentIndex -= gap
        }
      }

      // Shrink the gap.
      gap = Math.floor(gap / 2)
    }

    // Return sorted copy of an original array.
    return array
  }
}

复杂度：

2.8 计数排序（Counting Sort）

在计算机科学中，计数排序是一种依据小整数键值对象汇合进行排序的算法。也就是说，它是一个整数排序算法。
它通过计算具备每个不同键值的对象的数量，并对这些计数来确定每个键值在输入序列中的地位。
它的运行工夫与项目数和最大最小键值之差呈线性关系，因而只适宜在键的变动不显著大于项目数的状况下间接应用。

动画演示：

1. 咱们计算输出数组的所有元素的计数 A。而后将后果存储在计数数组 C 中。咱们的计数形式如下所示。

2. 咱们计算每个键值在输入序列中的地位。

3. 在这一步中，咱们借助结构的计数数组 C（即咱们在第二步中结构的内容）将输出数组元素搁置在排序地位。咱们应用后果数组 B 来存储排序后的元素。

代码实现：

import Sort, {ICallbacks} from '../../utils/sort/Sort'

// 仅反对数字元素排序，因为要计算最大元素和最小元素的差值作为键的品种
type TCompareParam = number

export default class CountingSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TCompareParam[],
    smallestElement: TCompareParam = undefined,
    biggestElement: TCompareParam = undefined
  ) {
    // Init biggest and smallest elements in array in order to build number bucket array later.
    let detectedSmallestElement = smallestElement || 0
    let detectedBiggestElement = biggestElement || 0

    if (smallestElement === undefined || biggestElement === undefined) {originalArray.forEach((element) => {
        // Visit element.
        this.callbacks.visitingCallback(element)

        // Detect biggest element.
        if (this.comparator.greaterThan(element, detectedBiggestElement)) {detectedBiggestElement = element}

        // Detect smallest element.
        if (this.comparator.lessThan(element, detectedSmallestElement)) {detectedSmallestElement = element}
      })
    }

    // Init buckets array.
    // This array will hold frequency of each number from originalArray.
    const buckets = Array(detectedBiggestElement - detectedSmallestElement + 1).fill(0)

    originalArray.forEach((element) => {
      // Visit element.
      this.callbacks.visitingCallback(element)

      buckets[element - detectedSmallestElement] += 1
    })

    // Add previous frequencies to the current one for each number in bucket
    // to detect how many numbers less then current one should be standing to
    // the left of current one.
    for (let bucketIndex = 1; bucketIndex < buckets.length; bucketIndex += 1) {buckets[bucketIndex] += buckets[bucketIndex - 1]
    }

    // Now let's shift frequencies to the right so that they show correct numbers.
    // I.e. if we won't shift right than the value of buckets[5] will display how many
    // elements less than 5 should be placed to the left of 5 in sorted array
    // INCLUDING 5th. After shifting though this number will not include 5th anymore.
    buckets.pop()
    buckets.unshift(0)

    // Now let's assemble sorted array.
    const sortedArray = Array(originalArray.length).fill(null)
    for (let elementIndex = 0; elementIndex < originalArray.length; elementIndex += 1) {
      // Get the element that we want to put into correct sorted position.
      const element = originalArray[elementIndex]

      // Visit element.
      this.callbacks.visitingCallback(element)

      // Get correct position of this element in sorted array.
      const elementSortedPosition = buckets[element - detectedSmallestElement]

      // Put element into correct position in sorted array.
      sortedArray[elementSortedPosition] = element

      // Increase position of current element in the bucket for future correct placements.
      buckets[element - detectedSmallestElement] += 1
    }

    // Return sorted array.
    return sortedArray
  }
}

复杂度：

2.9 基数排序（Radix Sort）

基数排序是一种 非比拟 整数排序算法，它通过按 共享雷同无效地位和值 的单个数字对键进行分组来应用整数键对数据进行排序。
地位符号是必须的，但因为整数能够示意字符串（例如，名称或日期）和非凡格局的浮点数，所以基数排序不限于整数。
也叫做桶排序。

动画演示：

代码实现：

import {TypeCompareParam} from '../../utils/comparator/Comparator'
import Sort, {ICallbacks} from '../../utils/sort/Sort'

// Using charCode (a = 97, b = 98, etc), we can map characters to buckets from 0 - 25
const BASE_CHAR_CODE = 97
const NUMBER_OF_POSSIBLE_DIGITS = 10
const ENGLISH_ALPHABET_LENGTH = 26

export default class RadixSort extends Sort {constructor(originalCallbacks?: ICallbacks) {super(originalCallbacks)
  }

  sort(originalArray: TypeCompareParam[]) {
    // Assumes all elements of array are of the same type
    const isArrayOfNumbers = this.isArrayOfNumbers(originalArray)

    let sortedArray = [...originalArray]
    const numPasses = this.determineNumPasses(sortedArray)

    for (let currentIndex = 0; currentIndex < numPasses; currentIndex += 1) {
      const buckets = isArrayOfNumbers
        ? this.placeElementsInNumberBuckets(sortedArray as number[], currentIndex)
        : this.placeElementsInCharacterBuckets(sortedArray as string[], currentIndex, numPasses)

      // Flatten buckets into sortedArray, and repeat at next index
      sortedArray = buckets.reduce((acc, val) => {return [...acc, ...val]
      }, [])
    }

    return sortedArray
  }

  placeElementsInNumberBuckets(array: number[], index: number) {
    // See below. These are used to determine which digit to use for bucket allocation
    const modded = 10 ** (index + 1)
    const divided = 10 ** index
    const buckets = this.createBuckets(NUMBER_OF_POSSIBLE_DIGITS)

    array.forEach((element) => {this.callbacks.visitingCallback(element)
      if (element < divided) {buckets[0].push(element)
      } else {
        /**
         * Say we have element of 1,052 and are currently on index 1 (starting from 0). This means
         * we want to use '5' as the bucket. `modded` would be 10 ** (1 + 1), which
         * is 100. So we take 1,052 % 100 (52) and divide it by 10 (5.2) and floor it (5).
         */
        const currentDigit = Math.floor((element % modded) / divided)
        buckets[currentDigit].push(element)
      }
    })

    return buckets
  }

  placeElementsInCharacterBuckets(array: string[], index: number, numPasses: number) {const buckets = this.createBuckets(ENGLISH_ALPHABET_LENGTH)

    array.forEach((element) => {this.callbacks.visitingCallback(element)
      const currentBucket = this.getCharCodeOfElementAtIndex(element, index, numPasses)
      buckets[currentBucket].push(element)
    })

    return buckets
  }

  getCharCodeOfElementAtIndex(element: string, index: number, numPasses: number) {
    // Place element in last bucket if not ready to organize
    if (numPasses - index > element.length) {return 0}

    /**
     * iterate backwards through element
     */
    const charPos = numPasses - index - 1

    return element.toLowerCase().charCodeAt(charPos) - BASE_CHAR_CODE
  }

  /**
   * Number of passes is determined by the length of the longest element in the array.
   * For integers, this log10(num), and for strings, this would be the length of the string.
   */
  determineNumPasses(array: TypeCompareParam[]) {return this.getLengthOfLongestElement(array)
  }

  getLengthOfLongestElement(array: TypeCompareParam[]) {if (this.isArrayOfNumbers(array)) {return Math.floor(Math.log10(Math.max(...(array as number[])))) + 1
    }

    return (array as string[]).reduce((acc, val) => {return val.length > acc ? val.length : acc}, -Infinity)
  }

  isArrayOfNumbers(array: TypeCompareParam[]) {
    // Assumes all elements of array are of the same type
    return this.isNumber(array[0])
  }

  createBuckets(numBuckets: number) {
    /**
     * Mapping buckets to an array instead of filling them with
     * an array prevents each bucket from containing a reference to the same array
     */
    return new Array(numBuckets).fill(null).map(() => [])
  }

  isNumber(element: TypeCompareParam) {return Number.isInteger(element)
  }
}

复杂度：

后记

欢送关注，获取更多。微信公众号：微微编程世界。