The example of this article tells the sorting method of Java insertion. Share it for everyone for your reference. The specific analysis is as follows:
There is an existing data sequence that requires a number in this already -ranked data sequence, but this data sequence is still orderly after insertion. At this time, the insertion sorting method is required. This article mainly introduces Java implementation sorted.
The basic operation of inserting sorting is to insert a data into an orderly data that has been arranged, so as to obtain a new, number of order plus order. The comparison and exchange time complexity is O (n^2). The algorithm is adaptable. For the data that is basically orderly, the time complexity is O (N), the algorithm is stable, and the overhead is very low. The algorithm is suitable for the situation where the data is basically orderly or the amount of data is small.
The inserting algorithm divides the number to be sorted into two parts: the first part contains all the elements of this array, except for the last element, and the second part only contains this element. After the first part is sorted, insert this final element into the position of the first part at this moment.
Algorithm description
Generally speaking, insertion sorting is implemented on the array with in-Place. The specific algorithm description is as follows:
1. From the first element, this element can be considered sorted
2. Take out the next element and scan from the sorted element sequence from backward
3. If this element (sorted) is greater than the new element, the element is moved to the next position
4. Repeat step 3 until the position of the sorted element is less than or equal to the location of the new element
5. Insert new elements into the next position
6. Repeat step 2
If the cost of the comparison operation is large than the operation, the two -point search method can be used to reduce the number of comparative operations. This algorithm can be considered as a variant of inserting sorting, called dual -point search sorting.
Code implementation
public void insertionsort ]; In = OUT; Boolean Flag = In> 0 && A [In-1]> = Temp; While (FLAG) {if (a [in-1]> = test) {if (in> 0) {a [in] = a [in-1]; count1 ++; --n;}} count2 ++; flag = in> 0 && a [in 1]> = test;} a [in] = temp;} system.out.println ("" copy number of replicas times For: " + count1 +" comparison times are: " + count2);}Inserting the sorting method is better in the case of a certain order. However, if the data is irregular, it is necessary to move a large amount of data, and its efficiency is as bad as the bubbling sorting method and the selection sorting method.
It is hoped that this article is helpful to everyone's Java program design.