JS implementation O(logN*N) sort: fast row, heap row
Another sort of O(logN*N) : merge sort, see juejin.cn/post/703107…
Fast row
The implementation of fast sorting is based on partition and divide and conquer.
The Dutch flag
The Dutch flag is made up of red, white and blue stripes, as shown below:
Given an integer array, given a value of K, this value must be in the original array, require less than K element in the array on the left of the array, is greater than the right of the K element in the array is equal to the middle of the K element in the array, eventually returns an integer array, of which only two values, respectively is equal to K array part about two values.
For example, given an array: [2, 3, 1, 9, 7, 6, 1, 4, 5], given a value of 4, then processing the original array may result in one of the following situations: [2, 3, 1, 1, 4, 9, 7, 6, 5], it should be noted that the part less than 4 does not need to be ordered, and the part greater than 4 does not need to be ordered, return the left and right subscripts equal to 4, namely [4, 4].
Solution process:
- Left is used to record the right subscript of an area less than 4, starting with -1, indicating that it does not exist
- Right is used to record the left subscript of a region greater than 4, starting with 9 to indicate that it does not exist
- Index is the index of the element being traversed, with an initial value of 0
- The array is traversed from arr[index], that is, ARr [0]
- If arr[index] > 4, swap arr[++left] and arr[index++]
- If arr[index] < 4, swap arr[–right] and arr[index]
- If arr[index] = 4, do not swap, L++, just iterate over the next value
- When index >= right, exit the loop.
Code implementation:
function swap (arr, index1, index2) {
if (index1 === index2) {
return
}
let temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
function partition(arr, criterion) {
let index = 0
let left = -1
let right = arr.length
while (index < right) {
if (arr[index] < criterion) {
swap(arr, ++left, index++)
} else if (arr[index] > criterion) {
swap(arr, --right, index)
} else {
index++
}
}
return [left + 1, right - 1]
}
partition([2.3.1.9.7.6.1.4.5].4)
Copy the codeThe implementation of fast row
The solution of Dutch problem is the partition process in fast sorting. Each partition process determines the sorting result of a value (criterion). Partition returns an array, which is the subscript of the base element (sorted). Fast sorting can be used as O(logN * N) algorithm, because the base element needs to be randomly selected, not affected by the data best case and worst case, so the long-term expectation of the algorithm can be O(logN * N).
The quicksort code is as follows:
function swap (arr, index1, index2) {
if (index1 === index2) {
return
}
let temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
function partition(arr, left, right) {
// the rightmost term of the array is the baseline
const criterion = arr[right]
let index = left
while (index <= right) {
if (arr[index] < criterion) {
swap(arr, left++, index++)
} else if (arr[index] > criterion) {
swap(arr, right--, index)
} else {
index++
}
}
return [left, right]
}
function process(arr, left, right) {
if (left >= right) {
return
}
// 1 Select an arbitrary reference value in the left and right range for stratification
const random = (Math.random() * (right - left + 1) | 0) + left
// 2 Swaps the selected base value with the rightmost term
swap(arr, random, right)
const [leftPart, rightPart] = partition(arr, left, right)
process(arr, left, leftPart - 1)
process(arr, rightPart + 1, right)
}
function quickSort (arr) {
process(arr, 0, arr.length - 1)}Copy the codeThe time complexity of quicksort is O(logN * N), and the space complexity is O(logN).
Heap sort
First, understand the heap structure. A heap is a complete binary tree with the following properties: the value of each node is greater than or equal to the value of its left and right children, called the big top heap; Or the value of each node is less than or equal to the value of its left and right children, called the small top heap. The diagram below:
- LeftChild = parentNode * 2 + 1 (index of leftChild: index of parent * 2 + 1)
- RightChild = parentNode * 2 + 2 (index of rightChild: index of parentNode * 2 + 1)
The big top heap above, which can be represented by an array, looks like this:
There are two common operations on a heap:
HeapInsert inserts data into the heap
The heap is represented by an array, and when you insert data somewhere in the array, you insert data into the heap. After each insertion, you need to adjust the heap so that the current heap is either a big top heap or a small top heap.
Adjustment process, according to the need to adjust the element index, find his parent node, parent-child node size ratio, if does not conform to the big top heap or small top heap (the value of each node is greater than or equal to the value of its left and right child nodes, called the big top heap; Or if each node has a value less than or equal to the value of its left and right children, called the small top heap, they switch places and keep moving up. The code looks like this (big top heap) :
function swap (arr, index1, index2) {
if (index1 === index2) {
return
}
let temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
// Adjust upward
function heapInsert(Arr, index) {
let child = index
let parent = (index / 2) | 0
// The value of the child node > the value of the parent node, which does not conform to the definition of the small top heap, swap places
while (arr[child] > arr[parent]) {
swap(arr, child, parent)
child = parent
parent = (child / 2) | 0}}Copy the codeHeapify pulls data to the top of the heap and adjusts the heap structure downward
In the adjustment process, according to the element index that needs to be adjusted, the child node is searched down, and the size ratio between the parent node and (the larger of the left and right child nodes (the smaller of the small top heap) is found. If it does not conform to the large or small top heap, the position is changed and the adjustment continues down. The code looks like this (big top heap) :
// Adjust downward
function heapify(Arr, index) {
let parent = index
let heapSize = arr.length
let leftChild = parent * 2 + 1
while (leftChild < heapSize) {
// Find the larger of the left and right child nodes
let largest = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ? leftChild + 1 : leftChild
if (arr[largest] > arr[parent]) {
swap(arr, largest, parent)
}
parent = largest
leftChild = parent * 2 + 1}}Copy the codeWith heapify and heapInsert, we can now sort arrays.
- Iterating from the 0th item of the array to the last item of the array, increasing the length of the heap and adjusting it to the heap structure, heapInsert
- Heapify continually removes the top element from the heap, placing it at the end of the array, while reducing the heap length and adjusting to the new heap
The code is as follows:
function swap (arr, index1, index2) {
if (index1 === index2) {
return
}
let temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
/ / big heap
function heapSort(arr) {
let heapSize = 0
// Adjust downward
function heapify(index) {
let parent = index
let leftChild = parent * 2 + 1
while (leftChild < heapSize) {
let largest = leftChild + 1 < heapSize && arr[leftChild + 1] > arr[leftChild] ? leftChild + 1 : leftChild
if (arr[largest] > arr[parent]) {
swap(arr, largest, parent)
}
parent = largest
leftChild = parent * 2 + 1}}// Adjust upward
function heapInsert(index) {
let child = index
let parent = (index / 2) | 0
while (arr[child] > arr[parent]) {
swap(arr, child, parent)
child = parent
parent = (child / 2) | 0}}let index = 0
// Form a heap structure from the 0th item of the array - from the last item of the array
for (; index < arr.length; index++) {
heapInsert(index) // Heapify can also be used here for better efficiency
heapSize++
}
index = 0
// Continuously take out the top of the heap and place it at the end of the array, reduce the heap length, and adjust to the new heap
for (; index < arr.length; index++) {
swap(arr, 0, heapSize - 1)
heapSize--
heapify(0)}}Copy the codeThe heaprow time is O(logN * N), space is O(1).
Priority queue
Depending on the effect of the heap, you can implement Max/min priority queues in JAVA and other languages with JS as follows:
class PriorityQueue {
constructor(compare = (a, b) => a - b) {
this.compare = compare;
this.queue = [];
}
// Add data
offer(value) {
this.queue.push(value)
this._heapInsert()
}
// Pop heap top data
poll() {
if (!this.queue.length) {
return null
}
const top = this.queue.shift()
this._heapify()
return top
}
_swap (arr, index1, index2) {
if (index1 === index2) {
return
}
let temp = arr[index1]
arr[index1] = arr[index2]
arr[index2] = temp
}
_heapify() {
let parent = 0
let left = parent * 2 + 1
while (left < this.queue.length) {
let operator = (left + 1 < this.queue.length) && this.compare(this.queue[left + 1].this.queue[left]) > 0 ? left + 1 : left
if (this.compare(this.queue[operator], this.queue[parent]) > 0) {
this._swap(this.queue, operator, parent)
}
parent = operator
left = parent * 2 + 1}}_heapInsert() {
let child = this.queue.length - 1
let parent = (child / 2) | 0
while (this.compare(this.queue[child], this.queue[parent]) > 0) {
this._swap(this.queue, child, parent)
child = parent
parent = (child / 2) | 0}}}Copy the code