Hope the epidemic is over
Today, I will share with you new and simple cases of learning data structures and algorithms, which are the internal skills of programming. So it's very important to learn it well. I hope I can continue to learn with you and insist on sharing the blog.
Today, I am learning the O(n^2) level sorting algorithm -- selection sorting and direct insertion sorting
(ascending sort by default)
Selection sort
In a pile of data to be arranged, select the smallest element and put it in the front arranged position, which may be a little unclear. For example:
For example, we have an array
[5,3,6,2,9]
In the first round, we find the smallest element, 2, and exchange it with the first element
[2,3,6,5,9]
Then we start with the second element and find the smallest element, 3. Exchange
Start with the third element and find the smallest element 5 to exchange
It can be seen that the selection sorting is to select the smallest element of the elements to be arranged every time, and then put it behind the elements in the order in front
If you still don't understand the process, baidu chooses the dynamic graph of sorting, which can be seen more intuitively
The implementation code is as follows:
(of course, in order to be more powerful, generic programming and object types that can be compared and customized are used here.)
package com.yxc.sort;
import com.yxc.domain.User;
import java.util.ArrayList;
/**
* @Auther: Little new
* @Date: 2020/2/7 09:06
* @Description:Select sorting to achieve efficiency O(n^2)
* Idea: select the smallest (largest) element in a pile of elements waiting to be arranged, exchange it with the first element, and then find the second smallest (second largest)
* Element, and then let it exchange with the second element, and so on, you can code as follows
* Using generic programming, note that if the a data in the main function is an Integer, it must be defined as Integer, and int cannot be used, otherwise it will appear
*/
public class SelectedSort {
public static void main(String[] args) {
Integer a[]={2,5,4,3,1,6,0,21,56,4};
Double b[]={2.0,5.2,6.8,8.5,6.88889,6.88888};
selectSort(a);
selectSort(b);
//Sorting test of custom type
//Create an array of several objects if there are several objects. Otherwise, a null pointer exception will appear
User[] user=new User[5];
user[0]=new User(1,"yxc",26);
user[1]=new User(1,"yxc1",25);
user[2]=new User(2,"yxc2",23);
user[3]=new User(9,"yxc3",23);
user[4]=new User(4,"yxc4",23);
selectSort(user);
for(int i=0;i<user.length;i++){
System.out.println(user[i]);
}
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
System.out.println();
for(int i=0;i<b.length;i++){
System.out.print(b[i]+" ");
}
}
/***
* Select sort ascending
* @param a
*/
public static void selectSort(Comparable a[]){
int n=a.length;
//Find the smallest element of [i,n], where n is the number length
for(int i=0;i<n;i++){
//Record the subscript of the smallest element
int index=i;
for(int j=i+1;j<n;j++){
if(a[j].compareTo(a[index])<0){
index=j;
}
}
swap(a,i,index);
}
}
//Exchange two elements
public static void swap(Object a[],int i,int j){
Object temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
User.java
package com.yxc.domain;
/**
* @Auther: Little new
* @Date: 2020/2/7 10:06
* @Description: Sort custom object types
*/
public class User implements Comparable<User>{
private Integer id;
private String usernmae;
private Integer age;
//Provide construction method
public User(){}
public User(Integer id, String usernmae, Integer age) {
this.id = id;
this.usernmae = usernmae;
this.age = age;
}
/***
* Sort users in ascending order of ID by default
* @param user
* @return
*/
@Override
public int compareTo(User user) {
if(this.id<user.id){
return -1;
}else if(this.id>user.id){
return 1;
}else{
//Sort by age if id is the same
return this.age.compareTo(user.age);
}
}
public Integer getId() {
return id;
}
public void setId(Integer id) {
this.id = id;
}
public String getUsernmae() {
return usernmae;
}
public void setUsernmae(String usernmae) {
this.usernmae = usernmae;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"id=" + id +
", usernmae='" + usernmae + '\'' +
", age=" + age +
'}';
}
}
Introduce our second sort algorithm insert sort directly
In fact, we all use this sort in our life, that is, when we play cards, we will habitually arrange the cards in order. This sort is the type and direct insertion sort
Sorting principle:
We cycle each element, and then put it in the appropriate position in front of us. In this way, we can divide all data into two heaps, the ordered and the unordered. Each time, we take an element from the unordered, insert it into the ordered position, and ensure that it is in the correct order
The same example illustrates the problem:
[8,1,6,5,9]
The first element 8 is ordered by default. So let's start with the second element
Take out 1, it's smaller than 8, so we're going to swap positions
[1,8,6,5,9]
Take out 6. It's smaller than 8. Swap positions. Keep comparing. It's bigger than 1. No exchange
[1,6,8,5,9]
Take out 5 to 8, exchange, continue to compare, exchange to 6, continue to compare to 1, end the comparison
And so on:
In addition, there is a simple optimization method, that is, every time we need to exchange, we can take this value, compare it all the time, and directly put it in the right place, so that when the data is large, the efficiency will be higher. Next, we can implement the algorithm through code and compare the efficiency
package com.yxc.sort;
import com.yxc.utils.CommonUtils;
/**
* @Auther: Little new
* @Date: 2020/2/7 15:02
* @Description:Insert sort O directly (n^2)
* Idea: loop through the array, putting each element in the right place in front of it
*/
public class InsertionSort {
public static void main(String[] args) {
/*Integer[] arry={1,8,6,5,2,3};
insertion2(arry);
CommonUtils.printArray(arry);*/
//It can be seen from the test results that the second method is more efficient when the data volume is large
Integer[] arry = CommonUtils.createRandom(10000);
//Testing the efficiency of two kinds of sorting
insertion(arry);
insertion2(arry);
//Test result: the use time of direct insertion sorting is 210ms
// The optimized time of direct insertion sorting is 3ms
}
/***
* Direct insert sort
* @param arry
*/
public static void insertion(Comparable[] arry){
long start = System.currentTimeMillis();
int length=arry.length;
//Starting with the second element, the first element is ordered
for(int i=1;i<length;i++){
//If the current element is smaller than the previous one, exchange the elements and start to compare further
//If the current element is larger than the previous one, you can end this cycle
for(int j=i;j>0&&(arry[j].compareTo(arry[j-1])<0);j--){
if(arry[j].compareTo(arry[j-1])<0){
CommonUtils.swap(arry,j,j-1);
}else{
break;
}
}
}
long end=System.currentTimeMillis();
System.out.println("Insert sort usage time directly"+(end-start)+"ms");
}
/***
* Simple optimization of direct insertion
* @param arry
*/
public static void insertion2(Comparable[] arry){
long start=System.currentTimeMillis();
int length=arry.length;
for(int i=1;i<length;i++){
//Do not exchange elements
Comparable temp=arry[i];
for(int j=i;j>0&&(arry[j].compareTo(arry[j-1])<0);j--){
if(temp.compareTo(arry[j-1])<0){
arry[j]=arry[j-1];
}else{
arry[j]= temp;
break;
}
}
}
long end=System.currentTimeMillis();
System.out.println("The optimized time of direct insertion sorting is"+(end-start)+"ms");
}
}
CommonUtils.java
package com.yxc.utils;
import java.util.Random;
/**
* @Auther: Little new
* @Date: 2020/2/7 10:37
* @Description:Some common and simple tool classes
*/
public class CommonUtils {
/***
* Exchange the values of two elements in an array
* @param arry
* @param i
* @param j
*/
public static void swap(Object arry[],int i,int j){
Object temp=arry[i];
arry[i]=arry[j];
arry[j]=temp;
}
/***
* Print array
* @param arry
*/
public static void printArray(Object[] arry){
for(int i=0;i<arry.length;i++){
System.out.print(arry[i]+" ");
}
}
/***
* Generate an array of random numbers
* @param n
*/
public static Integer[] createRandom(int n){
Integer[] arry=new Integer[n];
Random ran=new Random();
//If this is the case, the random number generated is the same every time
//Random ran=new Random(1);
for(int i=0;i<n;i++){
arry[i]=ran.nextInt(1000);
}
return arry;
}
}
Some specific code has detailed comments. Today's two algorithms are O (n^2) level algorithms, of course, there is a more classic algorithm of this level is bubble sorting. I believe that the first sorting algorithm in every book will take it as an example, and you can learn by yourself. If an array is basically ordered, we can basically achieve O (n) level efficiency by using direct insertion sorting. Note that we have (arry [J]. CompareTo (arry [J-1]) < 0) in the condition. If the array is basically ordered, we can directly jump out of the inner loop. This is the end of today's learning. During the epidemic, I urge myself to keep learning. I hope the epidemic will end soon. Cheer for yourself, cheer for the motherland!!!
