How to implement Common sorting by Java

This article will explain in detail how Java implements common sorting, Xiaobian feels quite practical, so share it with you as a reference, I hope you can gain something after reading this article.

1. selection sort

The basic idea of selective sorting is that in the process of traversing the array, if i represents the sequence number currently to be sorted, then it is necessary to find the minimum value among the remaining [i…n-1], and then exchange the minimum value found with the value pointed to by i. Because each element determination process has a subprocess that selects the maximum value, people call it selection sorting.

Take an example:

Initial: [38,17,16,16,7,31,39,32,2,11] i=0:[2,17,16,16,7,31,39,32,38,11](0th[38]8th[2]) i=1:[2,7,16,16,17,31,39,32,38,11](1st[38]4th[17]) i=2:[2,7,11,16,17,31,39,32,38,16](2nd[11]9th[16]) i=3:[2,7,11,16,17,31,39,32,38,16](no exchange required) i=4:[2,7,11,16,16,31,39,32,38,17](4th[17]9th[16]) i=5:[2,7,11,16,16,17,39,32,38,31](5th[31]9th[17]) i=6:[2,7,11,16,16,17,31,32,38,39](6th[39]9th[31]) i=7:[2,7,11,16,16,17,31,32,38,39](no exchange required) i=8:[2,7,11,16,16,17,31,32,38,39](no exchange required) i=9:[2,7,11,16,16,17,31,32,38,39](no exchange required)

As can be seen from the example, the number of comparisons will decrease as the selection sort proceeds (i gradually increases), but regardless of whether the array is initially ordered, the selection sort will perform a selection comparison from i to the end of the array, so the number of comparisons for a given length array is fixed: 1+2+3+….+ n=n*(n+1)/2, and the number of exchanges depends on the order of the initial array. If the initial array order is random, then in the worst case, the array elements will be exchanged n times, and in the best case, it may be 0 times (the array itself is ordered).

It follows from this that the time complexity and space complexity of selection sorting are O(n2) and O(1), respectively (selection sorting requires only one extra space for swapping array elements).

Implementation code:

/** *SelectionSorting */ SELECTION(newSortable(){ publicvoidsort(T[]array,booleanascend){ intlen=array.length; for(inti=0;i