O(n2)O(n^2)O(n2) order sorting algorithm; In this paper, we will learn about four O(nlogn)O(nlogn)O(nlogn) -level sorting algorithms.
The so-called sorting algorithm is to resort one or more groups of data according to the established pattern through a specific algorithm factor. The new sequence follows certain rules and reflects certain rules, so the processed data is easy to screen and calculate, and greatly improves the computational efficiency. For sorting, we first require it to have a certain stability, that is, when two identical elements appear in a sequence at the same time, after a certain sorting algorithm, their relative positions before and after the sorting will not change. In other words, even if two identical elements are sorted differently, they should not be confused.
Hill sorting
In July 1959, Donald Shell, PhD of mathematics department of University of Cincinnati, published hill sorting algorithm in COMMUNICATIONS of the ACM, which became one of the first algorithms to reduce the time complexity to O(n2)O(n^2)O(n2). Although the original hill sort is still O(n2)O(n^2)O(n2), the optimized Hill sort can reach O(N1.3)O(N ^{1.3})O(N1.3) or even O(N7/6)O(N ^{7/6})O(N7/6).
Hill sort is an optimization of insert sort in essence, which makes use of the simplicity of insert sort and overcomes the shortcoming of insert sort that only exchanges two adjacent elements each time. Its basic idea is:
- The array to be sorted is divided into multiple sub-arrays at a certain interval, and each group is sorted by insertion. By grouping by interval, I mean not taking a contiguous array, but taking one value at a certain jump interval to form a group
- Gradually narrow the interval for the next round of sorting
- In the last round, the interval is 11, which is equivalent to using insert sort directly. However, after the previous “macro control”, the array is basically ordered, so the insertion sort can be completed with a small number of swaps
For example, a hill sort on an array [8, 3, 34, 6, 4, 1, 44, 45, 43, 2, 23] would look like this:
The first pass (5-interval sort) : divide the subarray according to the interval 5, and divide it into five groups, namely [8, 1, 23],[3, 44],[34, 45],[6, 43],[4, 2]. Insert sort them and they become [1, 8, 23],[3, 44],[34, 45],[6, 43],[2, 4] respectively. Then the whole array becomes [1, 3, 34, 6, 2, 8, 44, 45, 43, 4, 23].
Second time (2 interval sort) : divide the subarray according to interval 2, and divide it into two groups, respectively [1, 34, 2, 44, 43, 23],[3, 6, 8, 45, 4]. Insert sort them, then they become [1, 2, 23, 34, 43, 44],[3, 4, 6, 8, 45], then the whole array becomes [1, 3, 2, 4, 23, 6, 34, 8, 43, 45, 44]. There is a very important property here: when we do 2-spaced sorting, the array is still 5-spaced sorted. That is, sorting with smaller intervals does not make the previous step worse.
Third time (11 interval sort, equal to direct insert sort) : divide the subarray by interval 1, into a group, that is, the entire array. Insert sort, and after the first two sorts, the array is pretty much in order, so it takes a little bit of swapping to sort it. After sorting the array becomes [1, 2, 3, 4, 6, 8, 23, 34, 43, 44, 45], the whole sorting is complete.
const sort = arr= > {
const len = arr.length;
if (len < 2) {
return arr;
}
let gap = Math.floor(len / 2);
while (gap > 0) {
for (let i = gap; i < len; i++) {
let j = i;
let cur = arr[i];
while (j >= 0 && cur < arr[j - gap]) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = cur;
}
gap = Math.floor(gap / 2);
}
return arr;
}
Copy the codeHeap sort
The heap sort process is as follows:
- Build a big top heap with a list of numbers and take out the top number of the heap (put it at the end of the array to be sorted);
- Adjust the remaining numbers to build a new big top heap, and take out the top number again;
- Repeat, complete the whole sorting.
function sort(arr) {
for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length)
}
for (let j = arr.length - 1; j > 0; j--) {
[arr[0], arr[j]] = [arr[j], arr[0]]
adjustHeap(arr, 0, j)
}
}
function adjustHeap(arr, i, length) {
let tmp = arr[i]
for (let k = i * 2 + 1; k < length; k = k * 2 + 1) {
if (k + 1 < length && arr[k] < arr[k + 1]) {
k++;
}
if (arr[k] > tmp) {
arr[i] = arr[k];
i = k;
} else {
break; } arr[i] = tmp; }}Copy the codeQuick sort
Quicksort algorithm was proposed by C. A. R. Hoare in 1960. It also has O(nlogn)O(nlogn)O(nlogn) O(nlogn)O(nlogn)O(nlogn) O(nlogn)O(nlogn)O(nlogn) O(nlogn)O(nlogn)O(nlogn) O(nlogn)O(nlogn)O, but it is more efficient in most cases, so quicksort is very widely used. In addition, the idea of divide and conquer adopted by quicksort is very practical, making quicksort favored by the interviewer, so it is particularly important to master the idea of quicksort.
The basic idea of quicksort algorithm is as follows:
-
Take a number out of the array, call it pivot
-
Walk through the array, placing the numbers larger than the base to its right and the numbers smaller than the base to its left. When the loop is complete, the array is divided into left and right regions
-
Treat the left and right areas as two arrays and repeat the first two steps until the sorting is complete
-
In fact, every iteration of quicksort puts the cardinality in the final position. The first round traverses 1 base, the second round traverses 2 bases (one for each region, but only one if a region is empty), the third round traverses 4 bases (again, worst case, only one base), and so on. The total number of traversal times is lognLognlogn ~ NNN times, and the time complexity of each traversal is O(n)O(n)O(n) O(n)O(n)O(n) O(n^2)O(n2). The average time complexity is O(nlogn)O(nlogn)O(nlogn).
const partition = (arr, start, end) = > {
let pivot = arr[start]; // take the first number as the base
let left = start + 1; // Start with the second number
let right = end; / / right border
// Exit the loop when left and right meet
while (left < right) {
// Find the first position greater than the cardinality
while (left < right && arr[left] <= pivot) left++;
// Swap the two numbers so that the left partition is less than or equal to the cardinality and the right partition is greater than or equal to the cardinality
if (left != right) {
[arr[left], arr[right]] = [arr[right], arr[left]];
right--;
}
}
// If left and right are equal, compare ARR and pivot separately
if (left == right && arr[right] > pivot) right--;
// Switch cardinals and intermediate numbers
if(right ! = start) [arr[left], pivot] = [pivot, arr[left]];// Returns the index of the median value
return right;
}
const quickSort = (arr, start, end) = > {
if (start >= end) return;
const middle = partition(arr, start, end)
quickSort(arr, start, middle - 1);
quickSort(arr, middle + 1, end);
}
const sort = arr= > {
quickSort(arr, 0, arr.length -1);
}
Copy the codeMerge sort
Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are joined into one ordered table, it is called 2-way merge.
Algorithm description
- The input sequence of length N is divided into two subsequences of length N /2.
- Merge sort is used for these two subsequences respectively.
- Combine two sorted subsequences into a final sorted sequence.
const merge = (left, right) = > {
let result = [];
while (left.length > 0 && right.length > 0) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else{ result.push(right.shift()); }}while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
}
const sort = (arr) = > {
let len = arr.length;
if (len < 2) {
return arr;
}
const middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(sort(left), sort(right));
};
Copy the code