Recognize the ordering of O (nlogn)

1 Merge sort

1. The whole is a simple recursion , Order on the left 、 Order on the right 、 Make it whole and orderly

2. In the process of making it whole and orderly, we use the method of exclusive order （ Left and right comparison , Put the smaller value into an external array , Then the called data pointer moves down one bit , In case of equality, the data on the left is taken by default , If the array data on one side is extracted , Save all the remaining data to the external array ）

3. utilize master Formula to solve the time complexity

4. The essence of merging and sorting

Time complexity O(N*logN), Extra space complexity O(N)

2 Extension of merge sort

Small sum problem and reverse order pair problem

Small and problem

In an array , The number smaller than the current number on the left of each number is added up , It's called the small sum of this array . Find the small sum of an array .

Example ：[1, 3, 4, 2, 5] 

1 On the left 1 Small number , No, ;3 On the left 3 Small number ,1;4 On the left 4 Small number ,1、3;2 On the left 2 Small number ,1;5 On the left 5 Small number ,1、3、4、2;

So Xiaohe is 1+1+3+1+1+3+4+2 = 16

The calculation process is similar to that of merge sorting , However, it needs to be sorted and small at the same time , And when the left and right data are equal, you need to copy the data on the right to the outer order array first .

Reverse order pair problem

In an array , If the number on the left is larger than the number on the right , Then fold two numbers to form a reverse order pair , Please print all pairs in reverse order .

3 The Dutch flag

Question 1

Given an array arr, And a number num, Please put less than or equal to num The number of is on the left side of the array , Greater than num To the right of the array . Requires extra space complexity O(1), Time complexity O(N)

Question two

Given an array arr, And a number num, Please put less than num The number of is on the left side of the array , be equal to num The number of is in the middle of the array , Greater than num To the right of the array . Requires extra space complexity O(1), Time complexity O(N)

4 Quick sort without improvement

1. Take the last number in the array range as the partition value , Then divide the array into three parts through the Dutch flag problem ;

left < Division value , middle == Division value , On the right side > Division value

2. For the left range and the right range , Recursive execution

analysis

1. The closer the partition value is to both sides , The more complex ; The closer the partition value is to the middle , The lower the complexity

2. It's easy to give the worst example , Therefore, the time complexity of quick sort without improvement is O(N^2) 

5 Random quick sort （ Improved quick sorting ）

1. In the array range , Select a number as the partition value with equal probability , Then divide the array into three parts through the Dutch flag ;

left < Division value , middle == Division value , On the right side > Division value

2. For the left range and the right range , Recursive execution

3. The time complexity is O(N*logN)