# Java select sort

### 1. principle

``` Select the smallest element from the records to be sorted each time, and place the sequence at the end of the sorted sequence until all records are sorted.
That is to say: every time i n n-i+1(i=1, 2,...) I n n-1) records, the record with the smallest key is selected as the ith record in the ordered sequence.
```

### 2. way of thinking

``` Given array: int[] arr = {n data}; in the first sorting, select the smallest data from the data to be sorted, arr[1]~arr[n],
In the second step, select the smallest data from the data to be sorted, and exchange it with r[2];
And so on, the i-th pass selects the smallest data i n the data to be sorted, arr[i]~arr[n], exchanges it with r[i], until all sorting is completed.
```

### 3. Code implementation

```/**
* Algorithm 1
*/
public int[] chooseSort(int[] arr){

//Comparison trips
for (int i = 0; i < arr.length - 1; i++) {
System.out.println("The first"+(i+1)+"Secondary ranking");
for (int j = i+1; j < arr.length; j++) {
System.out.println(arr[i] +" and "+arr[j]+" compare");
if(arr[i] > arr[j]){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
System.out.println("The first"+(i+1)+"After sorting:");
printArr(arr);
System.out.println();
}
return arr;
}

/**
*  Selection sort
*  optimization
*  Record the position of each minimum value
*  And then exchange the data
*/
public int[] chooseSort1(int[] arr){

int index;
//Comparison trips
for (int i = 0; i < arr.length - 1; i++) {
index = i;
System.out.println("The first"+(i+1)+"Secondary ranking");
//Select the decimal place
for (int j = i+1; j < arr.length; j++) {
System.out.println(arr[index] +" and "+arr[j]+" compare");
if(arr[index] > arr[j]){
//Note the location of the currently found minimum
index = j;
}
}
//At the end of the inner loop, that is, find the decimal place of the current loop, and then exchange
if(index != i){
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp;
}
System.out.println("The first"+(i+1)+"After sorting:");
printArr(arr);
System.out.println();
}
return arr;
}```

### 4. test

```@Test
public void test(){
//  int arr[] = {0,1,1,2,3,3,4,8,7,6,12,22,65};
int arr[] = {6,3,8,2,9,1};
System.out.println("Before sorting");
printArr(arr);

int[] data = chooseSort1(arr);

System.out.println("After ordering");
printArr(data);
}

public void printArr(int[] arr){
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
System.out.println();
}```

### 5. summary

```In terms of time complexity:
The comparison times of simple selection sorting are independent of the initial sorting of the sequence. If the sequence to be sorted has N elements, the number of comparisons will always be N (N - 1) / 2.
The number of moves is related to the initial sequence. When the sequence is in positive order, the minimum number of moves is 0. When the sequence is reversed, the number of moves is the most, 3N (N - 1) / 2.

So, to sum up, the time complexity of simple sorting is O(N2).
```

Added by lzylzlz on Thu, 02 Apr 2020 22:33:19 +0300