Auxiliary function
const Compare = {
LESS_THAN: -1.BIGGER_THAN: 1.EQUALS: 0,}function defaultCompare(a, b) {
if (a === b) {
return Compare.EQUALS
}
return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN
}
function swap(array, a, b) {
;[array[a], array[b]] = [array[b], array[a]]
}
Copy the code1. Bubble sort
Bubble sort compares two adjacent items and, if the first is larger than the second, swaps them. Items move up to the correct order, like bubbles rising to the surface, hence the name bubble sort.
function bubbleSort(array, compareFn = defaultCompare) {
let len = array.length
for (let i = 0; i < len; i++) {
for (let j = 0; j < len - 1 - i; j++) {
if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
swap(array, j, j + 1)}}}return array
}
Copy the code2. Select sort
Selection sort algorithm is a sort of address-comparison algorithm, the idea is to first find the smallest number in the data structure in the first place, then find the second smallest position in the second place, and so on.
function selectionSort(array, compareFn = defaultCompare) {
const { length } = array
let indexMin
for (let i = 0; i < length - 1; i++) {
indexMin = i
// Find the smallest term
for (let j = i; j < length; j++) {
if (compareFn(array[indexMin], array[j]) === Compare.BIGGER_THAN) {
indexMin = j
}
}
// Swap the smallest term with the ith term
if(i ! == indexMin) { swap(array, i, indexMin) } }return array
}
Copy the code3. Insert sort
Insert sort builds the last sorted array, one item at a time. Let’s say the first term is sorted. He then compares it with the second term to see if it needs to be switched, and the third term compares it with the first two terms to see if it needs to be switched, and so on
function insertionSort(array, compareFn = defaultCompare) {
const { length } = array
let temp
for (let i = 1; i < length; i++) {
let j = i
//temp: Saves the entry to be inserted
temp = array[i]
// Find the position where the left side is smaller than temp and the right side is larger than temp
while (j > 0 && compareFn(array[j - 1], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - 1]
j--
}
// Find the right place to insert
array[j] = temp
}
return array
}
Copy the code4. Hill sort
Hill sort is an optimized version of insertion sort. Divide a large array into smaller arrays for insertion sort.
function shellSort(array, compareFn = defaultCompare) {
const { length } = array
let gap = Math.floor(length / 2)
while (gap >= 1) {
for (let i = gap; i < length; i++) {
const temp = array[i]
let j = i
while (j > gap - 1 && compareFn(array[j - gap], temp) === Compare.BIGGER_THAN) {
array[j] = array[j - gap]
j -= gap
}
array[j] = temp
}
gap = Math.floor(gap / 2)}return array
}
Copy the code5. Merge sort
Merge sort is a divide-and-conquer algorithm. The idea is to cut the original array into smaller arrays until each of the smaller arrays has only one location, and then merge the smaller arrays into larger ones. Until there’s only one big array that’s sorted.
// Take care of merging and sorting to produce large arrays
function merge(left, right, compareFn) {
let i = 0
let j = 0
const result = []
while (i < left.length && j < right.length) {
result.push(compareFn(left[i], right[j]) === Compare.LESS_THAN ? left[i++] : right[j++])
}
return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}
function mergeSort(array, compareFn = defaultCompare) {
if (array.length > 1) {
const { length } = array
const middle = Math.floor(length / 2)
const left = mergeSort(array.slice(0, middle), compareFn)
const right = mergeSort(array.slice(middle, length), compareFn)
array = merge(left, right, compareFn)
}
return array
}
Copy the code6. Quicksort
- First, you choose a value from the array as the pivot, the value in the middle of the array.
- Create two Pointers (references), one on the left to the first value of the array and one on the right to the last value of the array. Move the left pointer until we find a value greater than the pivot, then move the right pointer until we find a value less than the pivot, then swap them and repeat the process until the left pointer passes the right. This process will place any value less than the pivot before the pivot, and any value greater than the pivot after it. This step is called a partition operation.
- The algorithm then repeats the previous two steps for the partitioned small array (a subarray of values smaller than the pivot and a subarray of values larger than the pivot) until the array is completely sorted.
// Partition operation
function partitiion(array, left, right, compareFn) {
const pivot = array[Math.floor((right + left) / 2)]
let i = left
let j = right
while (i <= j) {
// Move left until an element larger than pivot is found
while (compareFn(array[i], pivot) === Compare.LESS_THAN) {
i++
}
//rigth until an element smaller than pivot is found
while (compareFn(array[j], pivot) === Compare.BIGGER_THAN) {
j--
}
if (i <= j) {
swap(array, i, j)
i++
j--
}
}
console.log(i, '888')
return i
}
function quick(array, left, right, compareFn) {
let index
if (array.length > 1) {
index = partitiion(array, left, right, compareFn)
if (left < index - 1) {
quick(array, left, index - 1, compareFn)
}
if (index < right) {
quick(array, index, right, compareFn)
}
}
return array
}
function quickSort(array, compareFn = defaultCompare) {
return quick(array, 0, array.length - 1, compareFn)
}
Copy the code7. Counting sort
Counting sort is a distributed sort. Distributed sorting takes organized secondary data structures (buckets) and merges them to get sorted arrays. Counting sort uses a temporary array that stores the number of occurrences of each element in the original array. After all the elements have been evaluated, the temporary array is sorted and iterated to build a sorted result array.
Count sort is a good algorithm for sorting integers (it’s an integer sort algorithm) with a time complexity of O(n+ K), where K is the size of the temporary count array, but it does need more memory to hold the temporary array.
function findMaxValue(array) {
let max = array[0]
for (let i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i]
}
}
return max
}
function countingSort(array) {
if (array.length < 2) return array
const maxValue = findMaxValue(array)
const counts = new Array(maxValue + 1)
array.forEach((element) = > {
if(! counts[element]) { counts[element] =0
}
counts[element]++
})
console.log(counts)
let sortedIndex = 0
counts.forEach((count, i) = > {
while (count > 0) {
array[sortedIndex++] = i
count--
}
})
return array
}
Copy the code8. Bucket sorting
Bucket sorting is also a distributed sorting algorithm, which divides elements into buckets (smaller arrays), sorts each bucket using a simple sorting algorithm, and then merges all the buckets into a result array.
// Create buckets and distribute elements into different buckets
function createBuckets(array, bucketSize) {
let minValue = array[0]
let maxValue = array[0]
// Find the maximum and minimum values
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i]
} else if (array[i] > maxValue) {
maxValue = array[i]
}
}
// Number of buckets
const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1
// Buckets is a matrix (multidimensional array) where each location contains another array
const buckets = []
for (let i = 0; i < bucketCount; i++) {
buckets[i] = []
}
// Distribute elements into buckets
for (let i = 0; i < array.length; i++) {
const bucketIndex = Math.floor((array[i] - minValue) / bucketSize)
buckets[bucketIndex].push(array[i])
}
return buckets
}
// Perform the insert algorithm on each bucket and merge all buckets into an array of sorted results
function sortBuckets(buckets) {
const sortedArray = []
for (let i = 0; i < buckets.length; i++) {
if(buckets[i] ! =null) { insertionSort(buckets[i]) sortedArray.push(... buckets[i]) } }return sortedArray
}
function bucketSort(array, bucketSize = 5) {
if (array.length < 2) return array
const buckets = createBuckets(array, bucketSize)
return sortBuckets(buckets)
}
Copy the code9. Radix sort
Radix sort is also a distributed sort, which distributes integers into buckets based on the significant digit or radix. The cardinality is based on the notation of the values in the array.
const getBucketIndex = (value, minValue, significantDigit, radixBase) = >
Math.floor(((value - minValue) / significantDigit) % radixBase);
const countingSortForRadix = (array, radixBase, significantDigit, minValue) = > {
let bucketsIndex;
const buckets = [];
const aux = [];
for (let i = 0; i < radixBase; i++) {
buckets[i] = 0;
}
for (let i = 0; i < array.length; i++) {
bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
buckets[bucketsIndex]++;
}
for (let i = 1; i < radixBase; i++) {
buckets[i] += buckets[i - 1];
}
for (let i = array.length - 1; i >= 0; i--) {
bucketsIndex = getBucketIndex(array[i], minValue, significantDigit, radixBase);
aux[--buckets[bucketsIndex]] = array[i];
}
for (let i = 0; i < array.length; i++) {
array[i] = aux[i];
}
return array;
};
function radixSort(array, radixBase = 10) {
if (array.length < 2) {
return array;
}
let minValue = array[0]
let maxValue = array[0]
for (let i = 1; i < array.length; i++) {
if (array[i] < minValue) {
minValue = array[i]
} else if (array[i] > maxValue) {
maxValue = array[i]
}
}
let significantDigit = 1;
while ((maxValue - minValue) / significantDigit >= 1) {
array = countingSortForRadix(array, radixBase, significantDigit, minValue);
significantDigit *= radixBase;
}
return array;
}
Copy the code