This is the 27th day of my participation in the August More Text Challenge
Just a quick overview of the knowledge point
This is an interview algorithm article!! This article is not suitable for zero base!! Zero foundation to learn sorting first!! Sorting algorithm
Time complexity
-
O(n^2^) : Insert sort, bubble sort, select sort
-
O(nlog 2 ^n^) : quicksort, heap sort, merge sort
-
O(n) : radix sort, counting sort
-
Special case: Hill sort time complexity depends on how you take the step size. The time is between O(nlog 2^ n^) and O(n^2^)
Spatial complexity
-
O(1) : Insert sort, select sort, bubble sort, hill sort
-
O(Log2NLog_2NLog2N) -o (n) : quick sort
-
O(n) : merge sort
-
O(m) : radix sort. Count sorting
-
Special case: heap sort is O(logN) if it’s written recursively, O(1) if it’s not written recursively.
The stability of
- Stable sorting algorithm
Insert sort, bubble sort, merge sort, count sort, radix sort
- Unstable sorting algorithm
Hill sort, quick sort, selection sort, heap sort
The interview questions
1. Merge ordered arrays
Combine two ordered arrays into one array. The first array space can hold exactly two array elements.
It’s faster to sort backwards.
function foo(a, b) {
let alen = a.length
let blen = b.length
let index = alen + blen - 1
while(alen! =0&& blen ! =0) {
if (a[alen - 1] <= b[blen - 1]) {
a[index] = b[blen - 1]
index--
blen--
} else {
a[index] = a[alen - 1]
index--
alen--
}
}
if(blen! = =0) {for(let i=0; i<blen; i++){ a[i] = b[i] } }return a
}
Copy the code
2. The shortest array length to sort
function foo(a) {
let max = a[0],
min = a[a.length - 1],
maxIndex = 0,
minIndex = a.length - 1
for (let i = 0; i < a.length; i++) {
if (a[i] > max) {
max = a[i]
} else {
maxIndex = i
}
}
for (let i = a.length - 1; i >= 0; i--) {
if (a[i] <= min) {
min = a[i]
} else {
minIndex = i
}
}
return maxIndex-minIndex
}
Copy the code3. The question of the Dutch flag
Analysis: This idea can refer to fast sorting.
function fun(a) {
let index0 = -1,
index2 = a.length
for (let i = 0; i < a.length; i++) {
if (a[i] === 0) {
a[++index0] = [a[i], a[i] = a[index0]][0]}else if (a[i] === 2) {
a[--index2] = [a[i], a[i] = a[index2]][0]
i-- // Start from the swapped position again to avoid swapping 0
}
if (i + 1 === index2) {
break}}return a
}
Copy the code4. Find a value in a sorted two-dimensional array
Find a number in a two-dimensional array with rows and columns sorted from smallest to largest.
The lowest time complexity method is to start from the top right corner!! (Of course I don’t know if the lower left corner is also acceptable, I think the lower left corner is also :accept:)
For example, in my diagram, I find 3.
function fun(a, num) {
var rows = 0
var cols = a[0].length - 1
while(rows ! == a.length && cols ! = = -1) {
var flag = a[rows][cols]
if (flag > num) {
cols--
}else if(flag<num){
rows++
}else{
return true}}return false
}
Copy the code5. Find the maximum difference between two adjacent numbers after sorting
This is the idea of bucket sorting.
Ideas:
-
Find the maximum and minimum values in the array
-
(Max – Min)/Array length = Bucket value range
-
Number of buckets = original array length + 1
-
Put the largest number into the last bucket
-
Iterate through the number group and add the remaining numbers to the bucket according to the value range
-
Subtracting two adjacent buckets that are not empty (the first number of the next bucket minus the last number of the previous bucket)
For example array arr = [1, 2, 3, 4, 7, 8, 9]
function foo(a) {
// The container to hold the bucket
let bin = []
// Find the maximum and minimum values and calculate the range of each bucket
let max = Math.max(... arr)let min = Math.min(... arr)let gap = (max - min) / a.length
// Initialize the number of buckets to the size of the array +1
for (let i = 0; i <= a.length; i++) {
bin[i] = []
}
// Put the maximum value into the last bucket
bin[a.length].push(max)
// Count each number into a bucket
for (let i = 0; i < a.length; i++) {
for (let j = 0; j < a.length; j++) {
if (min + gap * j <= a[i] && a[i] < min + gap * (j + 1)) {
bin[j].push(a[i])
break}}}// The difference between buckets
var gapArr = []
for (let i = 0; i < bin.length - 1; i++) {
let j = i + 1
Bin [j][0] - undefined = NaN
if(bin[i].length === 0)
continue
// If the bucket is empty, exit the loop to prevent undefined - bin[I].pop() = NaN
while (bin[j].length === 0 && j < bin.length - 1)
j++
// If neither bucket is empty, calculate the difference between the two buckets using the first number of the latter and the last number of the former
gapArr.push(bin[j][0] - bin[i].pop())
}
return Math.max(... gapArr) }Copy the codeInterview high-frequency sorting algorithm source
Quick sort
function QuickSort(a){
if(a.length <=1) {return a
}
let left = []
let right = []
let pivot = a[0]
for(let i=1; i<a.length; i++){if(pivot>a[i]){
left.push(a[i])
}else{
right.push(a[i])
}
}
left = QuickSort(left)
right = QuickSort(right)
return left.concat(pivot,right)
}
Copy the codeHeap sort
A heap is usually referred to as a complete binary tree.
-
Large root heap: Each node has a value greater than or equal to the value of its left and right children (called the large root heap)
-
Small root heap: Each node has a value less than or equal to the value of its left and right children (called a small root heap)
Thought:
-
Given n records, the records are initially treated as a sequential binary tree,
-
And then adjust it to a big top heap,
-
Then the last element of the heap is exchanged with the top element of the heap (the root of the binary tree), and the last element of the heap is the largest record.
-
The first (n-1) elements (that is, excluding the maximum record) are then recalibrated into a large top heap,
-
Then swap the top element with the last element of the current heap to get the second largest record.
-
Repeat this process until there is only one element left in the adjusted heap
Principle:
- Set the initial keyword sequence (R1, R2… Rn) is constructed into the big top heap, which is the initial unordered region;
2. The top element R[1] is exchanged with the last element R[n], and the new unordered region (R1, R2… Rn-1) and a new ordered region (Rn), and R[1, 2… n-1]≤R[n];
- Since the new heap top R[1] after the swap may violate the heap properties, the current unordered region (R1,R2… Rn-1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2… Rn-2) and the new ordered region (Rn-1, Rn). This process is repeated until the number of elements in the ordered region is (n-1), and the whole sorting process is complete.
function HeapSort(a) {
let n = a.length;
n--;
for (let i = Math.floor(n / 2); i >= 0; i--) {
sift(a, i, n); / / adjust the heap
}
for (let i = 0; i < n; i++) {
a[0] = [a[n - i], a[n - i] = a[0]] [0] Swap the first one with the last one in the heap
sift(a, 0, n - i - 1); // The heap is reduced by one
}
return a
}
function sift(a, low, high) {
let i = low,
j = 2 * i + 1;
while (j <= high) // Must have =, to ensure that the heap can be reconstructed when there are two nodes left
{
if (j < high && a[j] < a[j + 1]) // Compare the left and right children and choose the older one
{
j++;
}
if (a[i] >= a[j]) // Meet the heap condition
{
break;
} else // The heap does not meet the condition
{
a[i] = [a[j], a[j] = a[i]][0]
i = j;
j = 2 * i + 1; }}}Copy the codeHill sorting
function ShellSort(a) {
let len = a.length,
temp, j
for (let d = Math.floor(len / 2); d > 0; d = Math.floor(d /= 2)) {
for (let i = d; i < len; i++) {
temp = a[i];
for (j = i - d; j >= 0&& temp < a[j]; j = j - d) { a[j + d] = a[j]; } a[j + d] = temp; }}return a
}
Copy the codeThe code below is from the Front-end Programmer Interview Algorithm Guide.
Merge sort
Analysis and Solutions:
Merge sort is to use recursion and divide-and-conquer technology to divide the data sequence into smaller and smaller half-sublists, then sort the half-sublists, and finally merge the sorted half-sublists into larger and larger ordered sequences by recursive method. In merge sort, “return” refers to recursion, that is, recursively split the array into a single array. For example, the array [2, 6, 1, 0] will be divided into two sub-arrays [2, 6] and [1, 0], and then split the array into [2], [6], [1] and [0]. A “union” is a grouping of separate pieces of data into an array in the smallest or largest order. Combining [2] and [6] above into an array is [2,6], combining [1] and [0] into an array is [0, 1], then combining [2,6] and [0, 1] into an array is [0, 1, 2,6].
Specifically, the principle of the merge sort algorithm is as follows: for a given set of records (assuming that there are n record), the first of the length of every two adjacent to one subsequence to merge, get n / 2 (rounded up) orderly sequence length is 2 or 1, then the two merge, execute the process over and over again, until we get an ordered sequence. So, the key to merge sort is two steps: first, list the molecules; The second step is to merge the half-child table. Taking the array [49, 38,65, 97, 76, 13, 27] as an example, the sorting process is as follows:
The algorithm principle is as follows:
1) Divide the input sequence of length N into two subsequences of length N /2;
2) Merge sort is applied to these two subsequences respectively;
3) Merge the two sorted subsequences into a final sorted sequence. According to the above implementation principle, the implementation code is as follows:
Count sorting
Counting sort is a stable sorting algorithm. Counting sort uses an extra array, countArr, where the ith element is the number of elements in the array arr to be sorted with a value equal to I. The elements in arR are then sorted into the correct positions according to the array countArr. Note that it can only sort integers.
The algorithm principle is as follows:
1) Find the largest and smallest elements in the array to be sorted;
CountArr [I] is the number of occurrences of elements equal to I in the array. CountArr [I] is the number of occurrences of elements equal to I.
3) Starting from the first element of arR to be sorted, place arr[I] in the correct position, that is, if there are several preceding elements less than or equal to it, it will be placed in the corresponding position.
According to the above implementation principle, the implementation code is as follows:
Algorithm complexity analysis:
When the input element is n integers between 0 and k, its running time is O(n+k). Counting sort is not comparison sort, so sorting is faster than any comparison sort algorithm.
Best case: T(n)=O(n+k).
Worst case: T(n)=O(n+k).
Average case: T(n)=O(n+k).
Bucket sort
Bucket sort works by dividing the data into a finite number of buckets, assuming that the input data is evenly distributed, and sorting each Bucket separately, with the possibility of using another sorting algorithm or continuing to use Bucket sort recursively.
The algorithm principle is as follows:
1) Set a quantitative array as an empty bucket;
2) Iterate over the input data and put the data into the corresponding bucket one by one;
3) Sort each bucket that is not empty;
4) Merge sorted data from never-empty buckets.
According to the above implementation principle, the array [20,0,39,66,40,78,46,36,60,100] as an empty bucket, the implementation code is as follows:
Algorithm complexity analysis: It is best to use linear time O(n) for bucket sorting. Its time complexity depends on the time complexity of sorting data between buckets, because the time complexity of other parts is O(n). Obviously, the smaller the bucket, the less data there is between the buckets, and the less time it takes to sort. But the corresponding space consumption will increase.
Best case: T(n)=O(n+k).
Worst case: T(n)=O(n+k).
Average case: T(n)=O(n2).
I am a girl Ann, today is also a day to study hard ~