Recognize the sorting algorithm of O(NlogN)
1. Analyze recursive behavior and estimate its time complexity
Recursive process: the recursive process is a multi fork tree. The process of calculating the nodes of all trees is to use the stack for post order traversal. Each node can continue to return upward only after summarizing information to itself through all its sub nodes. The stack space is the height of the whole tree.
Example ① use recursive method to find the maximum value in an array.
int process(vector<int> &nums, int L, int R) {
if (L == R) {
return nums[L];
}
//>>The operation is a bit operation. Moving one bit to the right is equivalent to dividing by 2. The speed is faster than the starting operation.
int mid = L + ((R - L) >> 1);
int leftMax = process(nums, L, mid);
int rightMax = process(nums, mid + 1, R);
return max(leftMax, rightMax);
}
int main() {
vector<int> nums{3, 2, 5, 6, 7, 4};
int max = process(nums, 0, nums.size() - 1);
cout << max;
}
The recursive logic diagram of calling process (Num, 0, 5) for array [3, 2, 5, 6, 7, 4] is shown in the figure below, where p(a,b) represents process (Num, a, b)
Master formula:
T
(
N
)
=
a
×
T
(
N
/
b
)
+
O
(
N
d
)
T(N)= a×T(N/b)+O(N^d)
T(N)=a×T(N/b)+O(Nd)
T(N) indicates that the data scale of the target problem is N-level; T(N/b) indicates that the data scale of the recursive subprocess is the scale of N/b; a indicates the number of times the sub process is called; O(N^d) represents the remaining process time complexity.
Recursion satisfying master formula can solve the time complexity with the following formula:
- Log (B, a) > D - > complexity is O(N^log(b, a)})
- Log (B, a) = D - > complexity is O(N^d * logN)
- Log (B, a) < D - > complexity is O(N^d)
The recursion that satisfies such a process can use the master formula to solve the time complexity.
For example, ① can be expressed by master formula as: T(N) = 2 * T(N/2) + O(1)
2. Merge and sort
Merge sort:
- The whole is a simple recursion. The left side is in order, the right side is in order, and the whole is in order
- The external sorting method (i.e. the process of merge function) is used in the process of making it ordered as a whole
- master formula is used to solve the time complexity
void merge(vector<int>& nums, int L, int M, int R) {
vector<int> help(R - L + 1, 0);
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R) {
help[i++] = nums[p1] <= nums[p2] ? nums[p1++] : nums[p2++];
}
while (p1 <= M) {
help[i++] = nums[p1++];
}
while (p2 <= R) {
help[i++] = nums[p2++];
}
for (i = 0; i < help.size(); ++i) {
nums[L + i] = help[i];
}
}
void process(vector<int>& nums, int L, int R) {
if (L == R) {
return;
}
int mid = L + ((R - L) >> 1);
process(nums, L, mid);
process(nums, mid + 1, R);
merge(nums, L, mid, R);
}
int main() {
vector<int> nums{ 3, 2, 5, 6, 7, 4 };
process(nums, 0, 5);
for (int i : nums) {
cout << i << " ";
}
}
//The output result is 2 3 4 5 6 7
The master formula for merging and sorting can be expressed as: T(N) = 2T(N / 2) + O(N).
a = 2, b = 2, d = 1. Therefore, the time complexity of merging and sorting is O(NlogN) and the space complexity is O(N).
Example ②: small sum problem. In an array, the numbers on the left of each number that are smaller than the current number are added up, which is called the small sum of the array to find the small sum of an array.
Example: array [1, 3, 4, 2, 5]. There is no number smaller than 1 on the left; 3 the digit 1 smaller than 3 on the left; 4 the number 1 and 3 smaller than 4 on the left; 2 the number 1 smaller than 2 on the left; 5 the numbers smaller than 5 on the left are 1, 3 and 4; Therefore, the small sum is 1 + 1 + 3 + 1 + 1 + 3 + 4 + 2 = 16
//You can find the small sum by merging
//On the contrary, 3, 4, 2 and 5 on the right of 1 are larger than 1, resulting in 4 small ones and 4; 3. 4 and 5 on the right are larger than 3, resulting in 2 small and 6 of 3; 4 on the right, 5 is larger than 4, resulting in a small sum of 4; To the right of 2, there is a 5 larger than 2, resulting in a small sum of 2.
//The merging process 1 and the four numbers on the right are compared once. As long as the left is larger than the right, a small sum of the numbers on the left is generated
int merge(vector<int>& nums, int L, int M, int R) {
vector<int> help(R - L + 1, 0);
int i = 0;
int p1 = L;
int p2 = M + 1;
int res = 0;
while (p1 <= M && p2 <= R) {
if (nums[p1] <= nums[p2]) {
help[i++] = nums[p1];
res += nums[p1] * (R - p2 + 1);
++p1;
} else {
help[i++] = nums[p2++];
}
}
while (p1 <= M) {
help[i++] = nums[p1++];
}
while (p2 <= R) {
help[i++] = nums[p2++];
}
for (i = 0; i < help.size(); ++i) {
nums[L + i] = help[i];
}
return res;
}
int process(vector<int>& nums, int L, int R) {
if (L == R) {
return 0;
}
int mid = L + ((R - L) >> 1);
return process(nums, L, mid) + process(nums, mid + 1, R) + merge(nums, L, mid, R);
}
3. Quick sort
Immediate quick sort (improved quick sort)
- In the array range, select a number randomly with equal probability as the partition value, and then divide the array into three parts through the Dutch flag problem: left < partition value, middle = = partition value, right > partition value
- The left range and the right range are recursively
- The time complexity is O(NlogN) and the space complexity is O(logN).
//For the Dutch flag problem, an array is divided into three regions with a number as the boundary
//Functions dealing with nums[L,...R]
//Default to num[R]
//Return to the area (left boundary, with boundary).
vector<int> partition(vector<int> &nums, int L, int R) {
int less = L - 1; //< right boundary of area
int more = R; //>Left boundary of area
while (L < more) { //L represents the position num [R] - > division value of the current number of signatures
if (nums[L] < nums[R]) {
swap(nums[++less], nums[L++]);
} else if (nums[L] > nums[R]) {
swap(nums[--more], nums[L]);
} else {
++L;
}
}
swap(nums[more], nums[R]);
return vector<int>{less + 1, more};
}
void quickSort(vector<int> &nums, int L, int R) {
if (L < R) {
int random = rand() % (R - L + 1) + L;
swap(nums[random], nums[R]);
vector<int> p = partition(nums, L, R);
quickSort(nums, L, p[0] - 1); //< area
quickSort(nums, p[1] + 1, R); //>District
}
}
int main() {
vector<int> nums{ 3, 2, 5, 6, 7, 4 };
quickSort(nums, 0, nums.size() - 1);
for (int i : nums) {
cout << i << " ";
}
}
//The output result is 2 3 4 5 6 7
4. Heap sorting
heap
- Heap structure is a complete binary tree structure implemented by array.
- In a complete binary tree, if the maximum value of each subtree is at the top, it is a large root heap.
- In a complete binary tree, if the minimum value of each subtree is at the top, it is a small root heap.
- Heap structure heapInsert and heapify operations are important.
- Increase and decrease of heap structure.
- The priority queue structure is the heap structure.
- Heap ordering is far less important than heap structure
//A number is now in the index position and continues to move upward
void heapInsert(vector<int>& nums, int index) {
while (nums[index] > nums[(index - 1) / 2]) {
swap(nums[index], nums[(index - 1) / 2]);
index = (index - 1) / 2;
}
}
//Can a number move down when it is in the index position
void heapify(vector<int>& nums, int index, int heapSize) {
int left = index * 2 + 1; //Left child subscript
while (left < heapSize) { //When there were children below
//Which of the two children has the largest value, give the subscript to large
int largest = left + 1 < heapSize && nums[left + 1] > nums[left] ? left + 1 : left;
//Between the father and the older child, whose value is greater, give the subscript to larger
largest = nums[largest] > nums[index] ? largest : index;
if (largest == index) {
break;
}
swap(nums[largest], nums[index]);
index = largest;
left = index * 2 + 1;
}
}
void heapSort(vector<int>& nums) {
if (nums.size() < 2) {
return;
}
//It is equivalent to turning the array into a large root heap
for (int i = 0; i < nums.size(); ++i) { //O(N)
heapInsert(nums, i); //O(logN)
}
int heapSize = nums.size();
swap(nums[0], nums[--heapSize]);
while (heapSize > 0) { //O(N)
heapify(nums, 0, heapSize); //O(logN)
swap(nums[0], nums[--heapSize]); //O(1)
}
}
int main() {
vector<int> nums{ 3, 2, 5, 6, 7, 4 };
heapSort(nums, 0, nums.size() - 1);
for (int i : nums) {
cout << i << " ";
}
}
//The output result is 2 3 4 5 6 7