JAVA simple selection sorting algorithm principle and implementation

Simple selection sort :(select the minimum value, put it in the first place, then the first place moves backward, and so on) the first place is compared with each other one by one, and the first place is minimized, and the first place is pushed backward (i.e. the first place just selected is the minimum value, no longer participates in the comparison, the number of comparison is reduced by 1).

Complexity: the number of operations required for record movement is less than 0-3 (n-1). Regardless of the initial arrangement of records, the number of keyword comparisons required is the same, which is n(n-1)/2, and the total time complexity is O(n2).
Space complexity O(1)

Algorithm improvement: each comparison is to put the minimum value in the first place, so it can be a ratio to the end, find the minimum value, directly put in the first place, the elimination of meaningless switching operation. You can also move in a different direction and compare the last bit with each of the previous ones, sinking the maximum and pushing the last bit forward.

JAVA source code:

 public static void selectSort(Date[] days) {
  int min;
  Date temp;
  for (int i = 0; i < days.length; i++) {
   min = i;
   for (int j = min + 1; j < days.length; j++) {
    if (days[min].compare(days[j]) > 0) {
     min = j;
    }
   }
   if (min != i) {
    temp = days[i];
    days[i] = days[min];
    days[min] = temp;
   }
  }
 }
class Date {
 int year, month, day;
 Date(int y, int m, int d) {
  year = y;
  month = m;
  day = d;
 }
 public int compare(Date date) {
  return year > date.year ? 1 : year < date.year ? -1
    : month > date.month ? 1 : month < date.month ? -1
      : day > date.day ? 1 : day < date.day ? -1 : 0;
 }
 public void print() {
  System.out.println(year + " " + month + " " + day);
 }
}

Simple Selection Sort:

A simple selection Sort is similar to a Bubble Sort, in that each time a maximum value is selected from the remaining set of elements to fill the current position. The only difference is that bubble sort exchanges the position of the element each time it finds a value less than (or greater than) the current value, whereas simple selection sort selects the most and the current position of the remaining elements to exchange data.

For example, for the set of elements R={37, 40, 38, 42, 461, 5,  7, 9, 12}

In the first sequence: 37 is directly exchanged with 5 to form the new sequence R1={5,40,38,42,461,37,7,9,12}
In the second sequence: 40 is directly exchanged with 7 to form a new sequence R2={5,7,38,42,46,37,40,9,12}

And so on, down to the last element (note: in the second sort, 38 is less than 42, but they don't exchange data).

Here is a Java implementation version of simple selection sort:

　　public static void selectionSort ( int[] data )  {
　　if  ( data == null || data.length <= 1 ) 
　　return;
　　int i, j, value, minPos, len = data.length;
　　int outer = len - 1, tmp;
　　for  ( i = 0; i < outer; i++ )  {
　　value = data[i];
　　minPos = -1;
　　for  ( j = i + 1; j < len; j++ )  {
　　if  ( data[j] < value )  {
　　minPos = j;
　　value = data[j];
　　}
　　}
　　if  ( minPos != -1 )  {
　　tmp = data[i];
　　data[i] = value;
　　data[minPos] = tmp;
　　}
　　//            for  ( int k = 0; k < len; k++ )  {
　　//                System.out.print ( data[k] + " , " ); 
　　//            }
　　//            System.out.println (a); 
　　}
　　}
　　public static void main ( String[] args )  {
　　int[] coll = {
　　37, 40, 38, 42, 461, 5,  7, 9, 12
　　};
　　selectionSort ( coll ); 
　　for  ( int i = 0; i < coll.length; i++ )  {
　　System.out.print ( coll[i] + " , " ); 
　　}
　　}

Tree Selection Sort
Compared with simple selection sort, tree selection sort is a typical algorithm of space for time. The idea is to construct a relatively small (N +1) /2 number of N elements in a sort, and then a relatively small (N +1) /4 number until there is only one element. Construct a complete binary tree.
When you sort, that element is the minimum, you take that minimum element, you replace it with the maximum, and you adjust the full binary tree.
Here is a Java implementation of tree selection sort:

　　public static void treeSelectionSort ( int[] data )  {
　　if  ( data == null || data.length <= 1 ) 
　　return;
　　int len = data.length , low = 0 , i , j;
　　// add Auxiliary Space
　　int[] tmp = new int[2*len -1];
　　int tSize = tmp.length;
　　//construct a tree
　　for ( i =len-1 , j=tmp.length-1;i >=0 ;i--,j-- ) {
　　tmp[j]=data[i];
　　}
　　for ( i = tSize -1 ; i > 0 ; i-=2 ) {
　　tmp[ ( i-1 ) /2] = tmp[i] > tmp[i-1]? tmp[i-1]:tmp[i];
　　}
　　//end
　　//remove the minimum node.
　　while ( low < len ) {
　　data[low++] = tmp[0];
　　for ( j=tSize-1;tmp[j]!=tmp[0];j-- ); 
　　tmp[j] = Integer.MAX_VALUE;
　　while ( j > 0 ) {
　　if ( j%2 == 0 ) {  //If it's the right node
　　tmp[ ( j-1 ) /2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j =  ( j-1 ) /2;
　　}else{  //If it's the left node
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}
　　}
　　}

When we construct a complete binary tree, we need 2 times N minus 1 auxiliary Spaces for a set of N elements.
Code:

　　while ( j > 0 ) {
　　if ( j%2 == 0 ) {  //If it's the right node
　　tmp[ ( j-1 ) /2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
　　j =  ( j-1 ) /2;
　　}else{  //If it's the left node
　　tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
　　j = j/2;
　　}
　　}

Implements a recursive minimum in constructing a new set.