“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

Ah, good morning, everyone ah, you can see this series now add luffy prefix, not because I am a fan of pirates, but this is big full stack of tertiary study a series that, in order to respond to, I will in the future for a period of time are combined with luffy, friends to progress together, and the Denver nuggets that ascension is not dragon, ha ha.

Today we’re going to look at the last two classic non-comparative sorting algorithms.

  • RadixSort (radixSort)
  • bucketSort

The code for this article is here.

RadixSort (radixSort)

Radix sort is also a kind of non-comparison integer sort algorithm, its principle is to cut the integer into different numbers according to the number, and then compare according to each number respectively. Because radix sort is based on counting sort, it is also a stable sort.

Time complexity

There are two ways to implement radix sort

Method 1: time complexity O(d * (n + k)) D is the number of digits of the maximum value, and k is the base.

Method 2: Time complexity is O(DN)

Algorithm steps

  1. Find the largest value in the array to be sorted
  2. Sort (0-9) by counting the ones digit from 0 to 9
  3. From the tens place to the hundreds place… Until the maximum number of digits proceed 2 steps

The illustration process

! [radixSort](/Users/fin-9061/Library/Mobile Documents/com apple CloudDocs/knowledge/algorithms commonly used sorting algorithms. Assets/radixSort. GIF)

Code implementation

Method 1: Directly use the previous counting sort

function radixSort(arr) {
  let max = arr[0]
  for (let i = 0; i < arr.length; i++) { // Find the maximum value
    if (arr[i] > max) max = arr[i]
  }
  for (let i = 1; i <= max; i *= 10) {
    countingSort(arr, i) // Sort the cardinality from smallest to largest
  }
  function countingSort(arr, divider) {
    const counts = new Array(10).fill(0)
    for (let i = 0; i < arr.length; i++) {
      counts[Math.floor(arr[i] / divider) % 10] + +// Save the base number of corresponding digits
    }
    for (let j = 1; j < counts.length; j++) {
      counts[j] += counts[j - 1] // If you do not understand this step, please go to the improved version of the counting array in white algorithm learning Note 03
    }
    const res = []
    for (let k = arr.length - 1; k >= 0; k--) {
      res[--counts[Math.floor(arr[k] / divider) % 10]] = arr[k] // Assign according to the relation arr element in res
    }
    for (let i = 0; i < res.length; i++) {
      arr[i] = res[i] // copy the ordered sequence to arR}}}// const radixArr = getRandomArr();
const radixArr = [999999.888888.7.9.323.454.33333.1.2]
console.log('before radix sorting ===>', radixArr)
radixSort(radixArr)
console.log('after radix sorting ===>', radixArr)


Copy the code

Method two: use a two-dimensional array to store values of the same cardinality

function radixSort2(arr) {
  let max = arr[0]
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > max) max = arr[i]
  }
  const counter = [] // Store a two-dimensional array of cardinality positions
  for (let i = 1; i < max; i *= 10) {
    let index = 0
    // Sort the base bit
    for (let j = 0; j < arr.length; j++) {
      const radix = Math.floor(arr[j] / i) % 10
      if(! counter[radix]) counter[radix] = [] counter[radix].push(arr[j]) }// Reassign the arR
    for (let k = 0; k < counter.length; k++) {
      while (counter[k] && counter[k].length > 0) {
        arr[index++] = counter[k].shift()
      }
    }
  }
}
const radixArr2 = [999999.888888.7.9.323.454.33333.1.2]
console.log('before radix2 sorting ===>', radixArr2)
radixSort2(radixArr2)
console.log('after radix2 sorting ===>', radixArr2)


Copy the code

Bucket Sort

Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. To make bucket sorting efficient, we need to do two things:

  1. Increase the number of barrels as much as extra space is available
  2. The mapping function used can evenly distribute the N input data to K buckets (the data evenly distributed to each bucket is the fastest, the data evenly distributed to the same bucket is the slowest).

At the same time, the comparison sorting algorithm is very important to the performance of bucket elements.

Algorithm steps

  1. Create a number of buckets (such as arrays, linked lists)
  2. According to certain rules (different types of data, different rules), the elements in the sequence are evenly distributed to the corresponding buckets
  3. Sort each bucket individually
  4. Merges all elements that are not empty buckets into an ordered sequence

The illustration process

! [20190219081232815](/Users/fin-9061/Library/Mobile Documents/com apple CloudDocs/knowledge/algorithms commonly used sorting algorithms. Assets/bucketSort. PNG)

Code implementation

Since bucket sorting is flexible, we will use only one example here

function bucketSort(arr, size) {
  if (arr.length === 0) {
    return arr
  }

  let minValue = arr[0]
  let maxValue = arr[0]
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < minValue) {
      minValue = arr[i] // The minimum value of input data
    }
    if (arr[i] > maxValue) {
      maxValue = arr[i] // The maximum value of the input data}}// Initialize the bucket
  let DEFAULT_BUCKET_SIZE = 5 // Set the default number of buckets to 5
  const bucketSize = size || DEFAULT_BUCKET_SIZE
  let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
  let buckets = new Array(bucketCount)
  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = []
  }

  // Allocate data to buckets using mapping functions
  for (let i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i])
  }

  arr.length = 0
  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]) // Sort each bucket, using insert sort
    for (let j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j])
    }
  }

  return arr
}
const bucketArr = getRandomArr()
console.log('before bucket sorting ===>', bucketArr)
bucketSort(bucketArr)
console.log('after bucket sorting ===>', bucketArr)
Copy the code

Ok, so now we have a total of four articles, and we have learned 10 classic sorting methods. Have you learned them all? Did not learn to read the article several times, have a question welcome to the message area.

If you feel good, you can like it, or follow me, AND I will continue to update the front-end and algorithm learning articles.

Refer to the content

Github.com/hustcc/JS-S…