catalogue
Brief introduction to selecting sorting
Implementation of selective sorting
Select sort
Brief introduction to selecting sorting
Take out the smallest one first
Take out the smallest one for the rest
Take out the smallest one for the rest
......
Select the smallest element among the unprocessed elements every time
Every time we find the smallest element among the remaining elements, we just need to put the smallest element directly at the beginning of the array, that is, we can directly use the space of the current array to achieve in-situ sorting.
j starts from i, scans all the following elements, finds the smallest element, names it minIndex, and exchanges its position with the ith element.
Implementation of selective sorting
1. First select the smallest data from the original array and exchange it with the data at the first position.
2. Then select the next smallest element from the remaining n-1 data and exchange it with the data at the second position.
3. Then, repeat until the last two data are exchanged. At this point, the sorting of the original array from small to large is completed.
Continuously select the smallest element from the unordered elements and store it at the beginning of the sorted sequence, and then find the smallest element from the remaining unordered elements and store it at the end of the sorted sequence. And so on until all the elements are in order.
public class SelectionSort {
public SelectionSort() {
}
public static void sort(int[] arr){
//arr[0...i) is ordered; arr[i...n) is disordered s
for (int i = 0; i < arr.length; i++) {
//Select the index of the smallest value in arr[i...n)
int minIndex = i;
for (int j = i;j < arr.length;j++){
//Find the smallest of the remaining elements (compare search)
if (arr[j]<arr[minIndex]){
minIndex = j;
}
}
//Exchange arr[i] with arr[minIndex]
swap(arr,i,minIndex);
}
}
private static void swap(int[] arr, int i, int j) {
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int[] arr = {1,4,2,3,6,5};
SelectionSort.sort(arr);
for (int item:arr){
System.out.print(item+" ");
}
}
}Currently, you can only sort arrays of type int, so you need to use generics.
Use constrained generics
Just add < E > after static, which means that this method is a generic method. It handles a type like E. this type is specified by the user when calling, and the corresponding array can be specified as type E.
public static <E> void sort(E[] arr)
However, E-type may not necessarily be calculated with <, so we need to constrain the generic e to make it Comparable (there is a generic t in the Comparable interface, and the selection of T is the type of the object that can be compared with it. Generally, it is the class that implements the interface itself. Of course, it is the Person itself that can be compared with the Person class). Introduction to Comparable interface
public class SelectionSort {
public SelectionSort() {
}
//
public static <E extends Comparable<E>> void sort(E[] arr){
//arr[0...i) is ordered; arr[i...n) is disordered s
for (int i = 0; i < arr.length; i++) {
//Select the index of the smallest value in arr[i...n)
int minIndex = i;
for (int j = i;j < arr.length;j++){
//Find the smallest of the remaining elements (compare search)
if (arr[j].compareTo(arr[minIndex]) < 0){
minIndex = j;
}
}
//Exchange arr[i] with arr[minIndex]
swap(arr,i,minIndex);
}
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
Integer[] arr = {1,4,2,3,6,5};
SelectionSort.sort(arr);
for (int item:arr){
System.out.print(item+" ");
}
}
}
At this time, the method has been modified into a generic method. There is also a constraint on this type, which must be comparable. When it is presented in the JAVA language, it implements the comparable interface. Many sorting algorithms must ensure comparability.
Use Comparable interface
In order to reflect the advantages of modifying it into a generic method, we use a custom Student class to implement the sorting algorithm.
import java.util.Objects;
public class Student implements Comparable<Student>{
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student another) {
/*
Compare the current class with the passed class other, and return a negative number 0 and a positive number according to the situation
*/
if (this.score<another.score)
return -1;
else if (this.score>another.score)
return 1;
return 0;
//return this.score - another.score
}
@Override
public boolean equals(Object student) {
/*
Exceptions may occur during cast, so judgment is required
*/
if (this == student)//Compare whether the current class object is consistent with the passed in parameters. If it is consistent, no forced type conversion is required. It is directly true
return true;
if (student == null)//If the incoming object is empty, it can be directly false
return false;
/*
If the current class object does not belong to the same class as the class object of the passed in parameter, it is directly false, and there is no need for forced conversion
(The reason why overriding the equals method requires cast is that its parameters must be of type Object, so as to cover all possible parameter types passed in,
And if the specific parameter type transmitted is different from. If the earning objects are different, the two objects must be different)
*/
if (this.getClass() != student.getClass())
return false;
Student another = (Student) student;
return this.name.equals(another.name);//Write comparison logic
}
@Override
public String toString() {
return "Student{" +
"name='" + name + '\'' +
", score=" + score +
'}';
}
}
Main method implementation class:
public class SelectionSort {
public SelectionSort() {
}
//
public static <E extends Comparable<E>> void sort(E[] arr){
//arr[0...i) is ordered; arr[i...n) is disordered s
for (int i = 0; i < arr.length; i++) {
//Select the index of the smallest value in arr[i...n)
int minIndex = i;
for (int j = i;j < arr.length;j++){
//Find the smallest of the remaining elements (compare search)
if (arr[j].compareTo(arr[minIndex]) < 0){
minIndex = j;
}
}
//Exchange arr[i] with arr[minIndex]
swap(arr,i,minIndex);
}
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
Integer[] arr = {1,4,2,3,6,5};
SelectionSort.sort(arr);
for (int item:arr){
System.out.print(item+" ");
}
System.out.println();
Student[] students = {new Student("Alice",98),
new Student("Bobo",100),
new Student("xiaoming",66)};
SelectionSort.sort(students);
for (Student student:students){
System.out.println(student+" ");
}
}
}
Complexity analysis
Except for the two-layer loop, the other operations are constant level operations. In the second layer loop, if i is 0, n operations are required; if i=1, n-1 operations are required; and so on, a total of 1+2+3+...+n operations are required.
First, generate a random array in the ArrayGenerator class
/*
Because it is a sorting algorithm, it must ensure that the order is out of order, and generate a random array with a length of n. the range of each number is [0, bound]
*/
public static Integer[] generateRandomArray(int n,int bound){
Integer[] arr = new Integer[n];
Random rnd = new Random( );
for(int i = 0; i< n;i++)
arr[i] = rnd.nextInt(bound);
return arr;
}Judge whether such a large array is really sorted successfully:
public class SortingHelper {
public SortingHelper() {
}
public static <E extends Comparable<E>> boolean isSorted(E[] arr){
//Determine whether the previous element of the array is smaller than the next element
for (int i = 1;i<arr.length;i++){
if (arr[i-1].compareTo(arr[i])>0)
return false;
}
return true;
}
}
Encapsulate a test method in SortingHelper to test any sort method:
//Encapsulates a test method to test any sort method
public static <E extends Comparable<E>> void sortTest(String sortname, E[] arr){
long startTime = System.nanoTime();
if(sortname.equals("SelectionSort"))
SelectionSort.sort(arr);
long endTime = System.nanoTime();
double time = (endTime - startTime) / 1000000000.0;
if(!SortingHelper.isSorted(arr))
throw new RuntimeException(sortname + "failed");
System.out.println(sortname+","+"n = "+arr.length+","+time +"s");
}Test time:
public class SelectionSort {
public SelectionSort() {
}
//
public static <E extends Comparable<E>> void sort(E[] arr){
//arr[0...i) is ordered; arr[i...n) is disordered s
for (int i = 0; i < arr.length; i++) {
//Select the index of the smallest value in arr[i...n)
int minIndex = i;
for (int j = i;j < arr.length;j++){
//Find the smallest of the remaining elements (compare search)
if (arr[j].compareTo(arr[minIndex]) < 0){
minIndex = j;
}
}
//Exchange arr[i] with arr[minIndex]
swap(arr,i,minIndex);
}
}
private static <E> void swap(E[] arr, int i, int j) {
E t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int n = 10000;
Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
SortingHelper.sortTest("SelectionSort", arr);
}
}
If you want to test two groups of arrays:
public static void main(String[] args) {
int[] dataSize = {10000,100000};
for (int n:dataSize){
Integer[] arr = ArrayGenerator.generateRandomArray(n,n);
SortingHelper.sortTest("SelectionSort", arr);
}
}
It can be seen that due to the 10 times difference in N and the time complexity of O(n^2), the final time difference is nearly 100 times.