Shulou(Shulou.com)06/03 Report--

This article mainly introduces "how to master merge and sort". In daily operation, I believe that many people have doubts about how to master merge and sort. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful for you to answer the questions of "how to master merge and sort"! Next, please follow the editor to study!

Merge sort (Merge Sort)

Merging sorting is a sorting algorithm that must be skillfully mastered, and it is a high-frequency test spot for interviews. let's pick and sort together. The principle is very simple, and we can understand it at once.

Inside Yuan Ji Restaurant

The 23rd Dionysus tournament begins!

Chef Yuan wants to select one of the best chefs from his top 4 stores to participate in the Gospel Competition. The selection rules are as follows.

The first competition: each branch selects two cooks, and first carries on the competition in the store to select the winner in the store.

Second competition: then the winner in the store challenges the winner of another branch on behalf of the branch (semi-final)

The third competition: the last two winners compete to choose the final winner.

The schematic diagram is as follows

The Chef God Championship

The above examples should be familiar to all of you. In fact, the process of merging sorting is somewhat similar to that of Dionysus tryouts. Let's take a look at merging sorting.

The word merge means merge, merge, and the definition in our data structure is to combine two or more ordered tables into a new ordered table. And what we are talking about here is the sorting method realized by using the idea of merger.

The idea of divide and conquer is used in merging and sorting. As the name implies, divide and conquer, decompose a big problem into several small sub-problems to solve. If the small sub-problems are solved, the big ones will be solved. A special article will be written to describe it after divide and conquer, which is briefly mentioned here.

Let's use a picture to describe the data transformation of merge sorting, as shown in the following figure.

Merge and sort

We have a brief understanding of the idea of merging and sorting. From the above description, we can know that the merging process of the algorithm is relatively difficult to achieve, which is also the focus of this algorithm. Let's first take a look at the specific steps of the merging function through a video. After watching our video, we can get a general idea.

Video number

Do you understand the merger steps in the video? if you don't understand, there is no need to worry. Let's disassemble it together. The merger process is divided into three steps.

Step 1: create an extra large collection to store the merge results, and the length is the sum of the two small sets, as can be seen in the video

Step 2: we compare the values pointed to by the two pointers from left to right, save the smaller one in the large set, move the pointer after the storage, and continue to compare until all the elements of a small set are stored in the large set. See the picture below

Merge

Step 3: when all the elements of a small set are put into a large set, you need to save all the remaining elements in another small set into the large set, as shown in the following figure

Well, after watching the video and diagrams, can you write a general idea? after understanding the principle of the algorithm, the code is very simple to write.

Let's look at the code next.

Note: System.arraycopy () is used here, and you can also use other methods. The five parameters are source array, destination array, starting index of source array, starting index of destination array, and length of replication.

Class Solution {public int [] sortArray (int [] nums) {mergeSort (nums,0,nums.length-1); return nums;} public void mergeSort (int [] arr, int left, int right) {if (left)

> 1); mergeSort (arr,left,mid); mergeSort (arr,mid+1,right); merge (arr,left,mid,right);}} / / merge public void merge (int [] arr,int left, int mid, int right) {/ / the first step, define a new temporary array int [] temparr = new int [right-left + 1] Int temp1 = left, temp2 = mid + 1; int index = 0; / / corresponding to the second step, compare the values pointed to by each pointer, and store the small ones in the large set while (temp1)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.