Simple selection sorting: (select the minimum value, put it first, and then the first bit moves backward, so loop) The first bit compares with each one after the next, each time the smallest bit is topped, and the first bit is backward Promote (that is, the first digit just selected is the minimum value, no longer participate in the comparison, the number of comparisons is reduced by 1)
Complexity: The number of operations required to perform record movement is 0--3(n-1). Regardless of the initial arrangement of the record, the number of comparisons between keywords required is the same, and is n(n-1)/ 2. The total time complexity is O(n2);
Space complexity O(1)
Algorithm improvement: Every time you compare, it is to put the smallest value in the first place, so you can compare it to the end, find the minimum value, and put it directly in the first place, eliminating meaningless switching and moving operations. You can also change the direction, compare the last bit with each previous one, and make the maximum value bottom each time, and push the last bit forward.
JAVA source code:
The code copy is as follows:
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:
Simple selection sort is similar to bubble sorting (Bubble Sort). Each time, a most value will be selected from the remaining element collection to fill it to the current position. The only difference is that bubble sorting swaps the location of the element every time it finds that it is smaller (or greater than) than the current value, while simple selection sorting is to select the most value in the remaining elements and exchange data at the current position.
For example, for element set R={37, 40, 38, 42, 461, 5, 7, 9, 12}
In the first order: 37 is directly exchanged with 5, forming a new sequence R1={5,40,38,42,461,37,7,9,12}
In the second order: 40 is directly exchanged with 7, forming a new sequence R2={5,7,38,42,461,37,40,9,12}
And so on until the last element (note: in the second order, 38 is smaller than 42, but they do not exchange data).
Here is a Java implementation version that simply selects sorting:
The code copy is as follows:
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();
}
}
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
The tree selection sorting algorithm is a typical algorithm that trades space for time compared to simple selection sorting. The idea is to treat the N elements sorted, construct relatively small (n+1)/2 numbers, and then construct relatively small [n+1]/4 numbers until there is only one element. Constructed into a completely binary tree.
When sorting, the element is the smallest. Take out the smallest element, replace the element with "maximum value", and then adjust the complete binary tree.
Here is a Java implementation version of tree selection sorting:
The code copy is as follows:
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 is a right node
tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = (j-1)/2;
}else{ //If it is the left node
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
}
}
When constructing a complete binary tree, 2*N -1 auxiliary space is required for a collection of N elements.
Code:
The code copy is as follows:
while(j > 0){
if (j%2 == 0) { //If it is a right node
tmp[(j-1)/2] = tmp[j] > tmp[j-1]?tmp[j-1]:tmp[j];
j = (j-1)/2;
}else{ //If it is the left node
tmp[j/2]=tmp[j] > tmp[j+1]? tmp[j+1]:tmp[j];
j = j/2;
}
}
Then implement recursive construction of the minimum value in the new set.