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

This article introduces the "introduction and use of Java algorithm and sorting" related knowledge, in the actual case operation process, many people will encounter such a dilemma, and then let the editor lead you to learn how to deal with these situations! I hope you can read it carefully and be able to achieve something!

I. Preface

What is an algorithm? An algorithm is some kind of set, a set of simple instructions, a set of assigned simple instructions. Determine the important indicators of the algorithm:

First, whether it can solve the problem.

The running time of the second algorithm, that is, how long it takes to solve the problem and get the result.

There are also some necessary space resources, such as memory, etc.

In many cases, writing a working program is not enough. Because under big data, the running time is an important issue.

The performance of the algorithm is represented by the large O mark method. The large O marking method is the relative growth rate of the mark, and the accuracy is rough. For example, 2N and 3N + 2 are both O (N). That is, linear growth is often said, and exponential growth is often said.

Typical growth rate

A typical approach to providing performance is divide-and-conquer, or branch divide and conquer strategy:

Divide the problem into two roughly equal subproblems and solve them recursively, which is the part of the division.

In the treatment stage, the solutions of the two sub-problems are patched together, and a small amount of additional work may be done to get the solution of the whole problem.

Second, sort

The scheduling problem is an ancient but always popular problem. From the ACM contact to the present work, every time it involves algorithms, or reading some algorithms in the JDK source code, there are often sorting algorithms.

The purpose of the sorting algorithm is to rearrange an array (or sequence) with the data in the order from large to small (or from small to large). What are the benefits of changing the data from disorder to order?

Application level: solving problems

The simplest thing is that you can find the maximum or minimum value.

Solve the problem of "one occurrence", that is, the same logo elements are connected together.

Match items in two or more files

Find information by key code value

System level: reduce the entropy of the system and increase the order of the system (Volume 3 of Donald Knuth's classic Art of computer programming (The Art of Computer Programming))

According to Wikipedia, the sort done in the main memory is called the internal sort. The sort that needs to be done on disk and other storage is called external sorting external sorting.

An interface is an abstract type, a collection of abstract methods (compareTo), declared in interface. Therefore, the sorted object belongs to the Comparable type, that is, it implements the Comparable interface, and then calls the compareTo method implemented by the object to sort it after comparison.

Sorting under these conditions is called comparison-based sorting (comparison-based sorting)

Third, insert sort

Vernacular: bear big (one), bear two, bear three. Queue (sort) according to height from lowest to highest. At this time, Bear N joins the team, and it starts with the tail of the team. If it is higher than the bear body in front of it, compare it with the position being compared, from tail to head in turn & swap position. Finally changed to the position that should bear N is. This is the principle of insertion sorting.

Insert sort (insertion sort)

One of the simplest sort. Ps: just take a look at the bubble sort. Learning is not recommended.

It consists of N-1 sorting process.

If such an element is sorted, there is no need for sorting. That is, N = 1 (1-1 = 0)

Each sort ensures that the elements from the first position to the current position are sorted.

As shown in the figure: each element is compared forward and ends in its own position.

The code is parsed as follows:

Start the comparison forward from the second element of the array. Smaller than the first element, swap positions

If the second element is compared, then the third and the fourth. and so on

When comparing to the last element, complete the sort

The time complexity is O (N ^ 2), the best scenario is that the sort has been arranged, that is O (N), because the judgment condition of the loop can not be satisfied; the most extreme is the reverse array, that is O (N ^ 2). So the time complexity of the algorithm is O (N ^ 2).

Run the main method and the result is as follows:

[2, 3, 1, 4, 3] [1, 2, 3, 3, 4]

Then consider optimization, how will it be optimized? Inserting the sort optimization version is not a forward comparison. Compared with the previous half, a two-point comparison would be better. You can try the specific code by yourself.

IV. Insertion sorting in Array.sort source code

The above use their own insertion algorithm for sorting, in fact, JDK provides an Array.sort method to facilitate sorting. The case code is as follows:

Run the main method and the result is as follows:

[2, 3, 1, 4, 3] [1, 2, 3, 3, 4]

So how does Arrays.sort work? JDK 1.2 has Arrays, and JDK 1.8 optimizes a version of the sort algorithm. It is roughly as follows:

If the number of elements is less than 47, use insert sort

If the number of elements is less than 286, use quick sort

Timsort algorithm integrates merge sort and insert sort.

In the source code, we can see that mergeSort integrates the insertion sorting algorithm, which is the same as the above implementation. There is no line of explanation here.

This is the end of the introduction and use of Java algorithm and sorting. Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.