Table of Contents
 Common Sorting Algorithms
 Getting Started
 Sorting Chained Tables
 Merge intervals
 Advanced Topics:
 kth largest element in an array
 Finding the median of two positively ordered arrays
 Summary
1. Common Sorting Algorithms
Common sorting algorithms include Insertion Sort [O(n^2)], Summation Sort [O(nlogn)], Heap Sort [O(nlogn)], and Quick Sort [O(nlogn) > O(n^2)].
If you are not familiar with the sorting algorithms, you can learn them on Visualgo Algorithmic Data Structures, which has videos and algorithm definitions, so I won’t repeat them in the article.
2. Introductory topics
1) Sorted Chained Lists
Power button topic 148:
This is leetcode question 148, which is simple: sort an unordered linked table, with the advanced requirement: sort the linked table in O(nlogn)
time complexity and constantlevel space complexity.
Among the sorting algorithms The algorithms with O(nlongn) time complexity are subsumption sort, heap sort, and fast sort, but the worst time complexity of fast sort is O(n^2) which is not applicable in this problem, and heap sort is a better sorting algorithm for chained lists compared to subsumption sort.
So, we use the subsumption sort to realize this question, which is based on the idea of Partition Recursion with the following steps:
 divide the chain table from the middle node into two, you can use fast and slow pointer way to realize;
 sort the two subchained tables separately;
 the sorted list for the merger, you can get a complete sorted list.
The Go code is as follows:
1 

The code is very simple and efficient to write in recursive fashion:
2) Merging intervals
Force Buckle Topic 56:
The general idea is to merge an array of intervals so that there are no overlapping intervals after the merge. Suppose there are intervals [1,3] and [2,6], which should be merged into [1,6].
The idea of solving this problem is to compare the 2nd element of all the subarrays with the 1st element of the array that follows, and if there is a crossover, find a larger element to be the 2nd element of the new array. That is, when comparing [1, 3] 和 [2, 6]
, we first compare 3 is greater than 2, so we can see that there is a crossover between the two arrays, and 6 is greater than 3, so the 2nd element of the new array is 6 => [1, 6]
.
How can we be sure that the first element is unique? For example, if we have 2 arrays: [3, 5], [1, 8]
, we’ll have to determine the size of the first element when we merge them, so for simplicity we can sort all the arrays first, making sure that the array with the smaller first element comes first. In Go, you can implement array sorting with simple functions:
1  sort.Slice(arr, func(i, j int) bool { 
Next, we can write the full code:
1  import "sort" 
More than 94% efficient golang commits:
3. Advanced Topics
1) Finding the Kth largest element of an array
Power Buckle topic 215:
K largest element of the array, this question is the Internet factory interview questions, I have been tested in the byte, Baidu interview, so you must be proficient.
The meaning of the topic is very simple, is to find the kth largest element of the array sorted, such as [1,2,3,4,5], k = 2, then the second largest element is 4. If there is a topic with the same elements, we do not have to pay attention to, for example, [5,5,4,3,1], k = 2, then the second largest element is 5, rather than 4.
The advanced requirement is: design and implement an algorithm with O(n)
time complexity to solve this problem.
This problem is a classic one in sorting algorithms, in which, if we don’t require time complexity, we can just use all kinds of sorting algorithms to first sort the array and then get the kth largest element. However, whether in interviews or in daily use, we need to pursue the optimal time complexity of the algorithm, and efficient sorting algorithms are heap sort (nlogn), subsumption sort (nlogn) and quick sort (nlogn > n^2).
How to satisfy the time complexity O(n)?
Quick sort
The answer is mentioned in 9.2 of Introduction to Algorithms, Third Edition, where the randomized_select
algorithm is a selection algorithm that expects linear time, and is modeled after fast sort, where the idea is still recursive partitioning. Unlike fast sort, however, the randomized_select
algorithm deals only with one side of the partition, which we describe in code:
1  func findKthLargest(nums []int, k int) int { 
Submission of results:
We found that the optimized algorithm randomized_select time complexity for fast sort exceeds 99% of users.
Heap Sort
Next we implement it again with heap sort, which is a sorting algorithm designed to take advantage of the data structure heap. A heap is a structure that approximates a complete binary tree and simultaneously satisfies the heap form: i.e., a child node’s key value is always less than (or greater than) the key value of its parent node:
 Small top heap: each node’s value is less than or equal to the value of its child node;
 big top heap: each node’s value is greater than or equal to the value of its child node.
This question is to find the largest kth number, so we build a big top heap, each time we find the largest number, remove the largest number (implementation: the top of the heap and the end of the heap elements are interchanged, and then the size of the heap will be subtracted by one), and then find the k1th number, the code is as follows:
1  func findKthLargest(nums []int, k int) int { 
As you can see, heap sort has a time complexity of O(nlogn), which is a bit more timeconsuming than randomized_select
for fast sort:
2) Find the median of two positively ordered arrays
Force Buckle topic 4:
The general idea of the question is to find the median of two ordered arrays nums1 and nums2, and requires a time complexity of , which assumes that the two arrays will not be empty at the same time.
For this problem, the first and easiest way to think of is to merge the two arrays and take out the median. However, the operation of merging the arrays has a complexity of m+n, which does not meet the requirements of the question. Seeing the time complexity of log, we associate it with binary search. 1.
 When the total number of two arrays is odd, the middle number is the median; when the total number is even, the mean of the two middle numbers is the median. 2;
 know the length of the array, to find the median of the two arrays combined, only need to bisect the search to find the middle position of the array of 1 or 2 elements;
 As the location of the middle number to determine, so the two arrays only need to ** bisect the search for an array ** can be, in order to minimize the complexity of our search for the length of the smaller arrays;
 the most critical: bisection cut should be how to determine whether the end, we assume that there is an array A and array B (length of m and n, respectively), the first bisection cut on the array A, that cut point i, and j [due to i + j = (m + n)/2, so j = (m + n)/2  i] need to be satisfied, * * A [i], B [j] the lefthand side of the elements should be smaller than the righthand side of the elements, which can be guaranteed that i and j are one of the median elements**.
The graphical representation is as follows:
1 twopoint split:
2 twopoint splits:
After splitting again, left = 3, right = 3, and the dichotomous cut of array A is complete. At this point, the cut subscripts for arrays A and B are i = left = 3, j = mid  left = 2, respectively.
The median result will only come from these i, j, i1, j1
numbers. 1. when the total number of arrays is odd, the median is the larger of the left partition (i.e. i1 and j1):
 when the total number of arrays is odd, the median is the larger of the left partition (i.e., i1 and j1);
 when the total number of arrays is even, the median is the average of the largest number in the left partition and the smallest number in the right partition.
In addition, we have to consider boundary cases, such as when i, j is 0, the subscript i1 or j1 does not exist; when i, j is m, n, the subscript i or j does not exist. Since the title states that m and n will not be 0 at the same time, at least one of i and j must exist.
The Go code is as follows:
1  func findMedianSortedArrays(nums1, nums2 []int) float64 { 
Submission of results:
4. Summary
A few of the classic questions in the Power Buckle Sorting category are above, and their probability of being encountered in interviews or written exams is very high. In Huawei’s machine test questions, the frequency is also very high, except for the last question, which is a bit less difficult, the rest of the questions basically appear at least once in 10 interviews.