<> one ,Comparable Interface introduction

Java Provides an interface comparable Used to define collation , Sort objects .

demand :

* Define a student class Student, Have age age And name name Two properties , And pass Comparable Interface provides comparison rules .
* Define test class , Define test methods in test classes Comparable getMax(Comparable c1,Comparable c2) Complete the test . class
Student implements Comparable<Student>{ private int age; private String name;
// ellipsis set,get,toString, constructor // rewrite compareTo method , Used to compare the age of students @Override public int
compareTo(Student o) { int result=this.age-o.age; return result; } public static
void main(String[] args) { Student s1=new Student(18," Zhang San "); Student s2=new
Student(20, " Li Si "); int result=s1.compareTo(s2); if (result>0) { System.out.
println(s1.toString()); }else { System.out.println(s2.toString()); } }
Writing tool classes Utils, Used to compare data size and make data replacement
public class Utils { // Compare values public static boolean greater(Comparable v,
Comparable w) { return v.compareTo(w)>0; } // Numerical substitution public static void exch(
Comparable[] a,int i,int j) { Comparable temp; temp=a[i]; a[i]=a[j]; a[j]=temp;
} }
<> two , Bubble sorting

<>1. Sorting principle

*
Compare adjacent elements , If the previous element is larger than the latter element , Just swap the positions of the two elements .

*
Do the same for each pair of adjacent elements , From the first element at the beginning to the last element at the end , The element in the final position is the maximum value .

( From the last element to the first element , Finally, the first element is the minimum value ).

<>2. code implementation

The time complexity of bubble sorting is O(N^2).

code implementation 1:
public class BubbleSort2 { public static void main(String[] args) { int[] s= {4
,8,2,6,7,5,1}; bubbleSort(s); for (int i = 0; i < s.length; i++) { System.out.
println(s[i]); } } private static void bubbleSort(int[] s) { int temp; for (int
i= 0; i < s.length; i++) { for (int j = s.length-1; j >i; j--) { if (s[j]<s[j-1]
) { temp=s[j]; s[j]=s[j-1]; s[j-1]=temp; } } } } } public class BubbleSort {
public static void bubbleSort(Comparable[] s) { for (int i = 0; i < s.length; i
++) { for (int j = s.length-1; j >i; j--) { if (Utils.greater(s[j], s[j-1])) {
Utils.exch(s, j, j-1); } } } } public static void main(String[] args) { Integer[
] s= {9,7,4,8,2,5,3,1,6}; bubbleSort(s); // Output sorted sequence System.out.print(Arrays.
toString(s)); } }
<>3. Algorithm optimization
public class OptimizeBubbleSorting { private static void bubbleSort(Comparable[
] s) { for (int i = 0; i < s.length-1; i++) { boolean flag=true;
// use flag To indicate whether data exchange occurs in a round of comparison for (int j = s.length-1; j>i; j--) { if (Utils.greater
(s[j], s[j-1])) { Utils.exch(s, j, j-1); flag=false; // If data exchange occurs, set to false } } if (
flag) { // judge flag Value of , If still true It indicates that there is no data exchange in a round of comparison , immediate withdrawal return; } } } public static void
main(String[] args) { Integer[] s= {9,7,4,8,2,5,3,1,6}; bubbleSort(s); //
Output sorted sequence System.out.print(Arrays.toString(s)); } }
<> three , Select sort

<>1. Sorting principle

*
The process of each traversal , It is assumed that the element at the first index is the minimum value , Compare with the values at other indexes in turn , If the value at the current index is greater than the value at an index , The value at some other index is assumed to be the minimum , Finally, you can find the index where the minimum value is located .
* Swap the values at the first index and at the index where the minimum value is located .

<>2. code implementation

Time complexity :O(n^2)

code implementation 1:
public class SelectionSort { public static void main(String[] args) { int[] s=
{9,8,6,3,7,2,4,1,5}; selectionSort(s); for (int i = 0; i < s.length; i++) {
System.out.println(s[i]); } } private static void selectionSort(int[] s) { for (
int i = 0; i < s.length-1; i++) { int min=i;
// Define a variable , Record the index of the smallest element , The default is the location of the first element participating in the selection sorting for (int j = i+1; j < s.length; j++) {
// Minimum index to compare min Value at and j Value at index if (s[min]>s[j]) { min=j; } } // Exchange the index of the smallest element min Value and index at i Value at
int temp=s[min]; s[min]=s[i]; s[i]=temp; } } }
code implementation 2:
public class SelectionSort2 { public static void main(String[] args) { Integer[
] s= {9,7,4,8,2,5,3,1,6}; selectionSort(s); // Output sorted sequence System.out.print(Arrays.
toString(s)); } private static void selectionSort(Comparable[] s) { for (int i =
0; i < s.length-1; i++) { // Define a variable , Record the index of the smallest element , The default is the location of the first element participating in the selection sorting int min=i;
for (int j = i+1; j < s.length; j++) { // Minimum index to compare min Value at and j Value at index if (Utils.greater
(s[min], s[j])) { min=j; } } // Exchange the index of the smallest element min Value and index at i Value at Utils.exch(s, min, i); }
} }
<> four , Insert sort

<>1. Sorting principle

* Divide all elements into two groups , Sorted and unordered .
* The first element in an unordered group was found , Insert into a group that has already been inserted .
* Flashback traverses the sorted elements , Compare with the elements to be inserted in turn , Until an element smaller than the element with insertion is found , Then put the element to be inserted in this position , Other elements move back one bit .

<>2. code implementation

Time complexity :O(n^2)

code implementation 1:
public class InsertionSort { public static void main(String[] args) { int[] s=
{4,3,2,10,12,1,5,6}; insertionSort(s); for (int i = 0; i < s.length; i++) {
System.out.println(s[i]); } } private static void insertionSort(int[] s) { int
temp;// Intermediate variable for substitution // Sorted array for (int i = 0; i < s.length-1; i++) { // Find the first element that is not sorted
for (int j = i+1; j>0; j--) { // The first element that is not sorted is compared with a sorted array if (s[j]<s[j-1]) { temp=s[j
]; s[j]=s[j-1]; s[j-1]=temp; } } } } }
code implementation 2:
public class InsertionSort2 { public static void main(String[] args) { Integer[
] s= {1,7,4,6,3,5,2,8,9}; insertionSort2(s); System.out.println(Arrays.toString(
s)); } private static void insertionSort2(Comparable[] s) { for (int i = 0; i <
s.length-1; i++) { for (int j = i+1; j > 0; j--) { if (Utils.greater(s[j],s[j-1]
)) { Utils.exch(s,j,j-1); } } } } }
<> five , Shell Sort

<>1. Sorting principle

* Select an increase h, According to the growth h As the basis for data grouping , Group arrays
* Insert and sort each group of data divided into groups
* Reduce growth , The minimum is reduced to one , Repeat the second operation

<>2. code implementation

code implementation 1:
public class ShellSort { public static void main(String[] args) { Integer[] s=
{1,7,4,6,3,5,2,8,9}; shellSort(s); System.out.println(Arrays.toString(s)); }
private static void shellSort(Comparable[] s) { // According to array a Length of , Determine growth h Initial value of int h=1;
while (h<s.length/2) { h=2*h+1; } // Shell Sort while (h>=1) { // sort // Find the element to insert for (int
i= h; i < s.length; i++) { // Insert the elements to be inserted into an ordered sequence for (int j = i; j >= h; j-=h) {
// The element to be inserted is a[j], compare a[j],a[j-h] if (Utils.greater(s[j-h], s[j])) { Utils.exch(s, j,
j-h); }else { break; } } } // reduce h Value of h=h/2; System.out.println(Arrays.toString(s))
; } } }
code implementation 2:
public class ShellSort2 { public static void main(String[] args) { int[] s= {6,
3,8,7,9,5,1,2}; shellSort(s); for (int i = 0; i < s.length; i++) { System.out.
println(s[i]); } } private static void shellSort(int[] s) { int temp; int h=1;
while (h<s.length/2) { h=2*h+1; } while (h>=1) { for (int i = h; i < s.length; i
++) { for (int j = i; j >=h; j=j-h) { if (s[j]<s[j-h]) { temp=s[j]; s[j]=s[j-h];
s[j-h]=temp; } } } h=h/2; } } }
<> six , recursion

<>1. definition

When defining a method , Call the method itself inside the method , Called recursion .

During recursion , You can't call yourself unlimited , There must be boundary conditions , Can end recursion , Because every recursive call will open up a new space in the stack memory and re execute the method , If the level of recursion is too deep , It is easy to cause stack overflow .

<>2. demand

Define a method , Use recursion to complete the search n factorial .
public static long factional(int n) { // seek n factorial if (n==1) { return 1; } return n*
factional(n-1); }
<> seven , Merge sort

<>1. Sorting principle

* As far as possible, a set of data is divided into subgroups with equal two elements , And continue to split each sub group , Until the number of elements in each subgroup after splitting is 1 until .
* Merge two adjacent subgroups into an ordered large group
* Repeat the steps continuously 2, Until there is only one group in the end

<> eight , Quick sort

<>1. Sorting principle

*
First, set a boundary value , The array is divided into left and right parts by this boundary value

*
Put the data greater than or equal to the boundary value to the right of the array , Data less than the boundary value is placed to the left of the array , At this time, all elements in the left part are less than or equal to the boundary value , The elements in each part on the right are greater than or equal to the boundary value .

*

Then the data on the left and right can be sorted independently , For data on the left , Another boundary value can be taken , Divide this part of data into left and right parts , Also place smaller values on the left , Place a larger value on the right , The array data on the right can be processed similarly .

*
Repeat the above process , It can be seen that , This is a recursive definition , The left part is sorted by recursion , Then take the sequence of the right part recursively , When the data of the left and right parts are sequenced , The sorting of the whole array is completed .

Technology
©2019-2020 Toolsou All rights reserved,
evo Tool usage problems ——Degenerate covariance rank, Umeyama alignment is not possible Experiment 4 Automated test tools - software test mysql Export data sql sentence _mysql according to sql Query statement export data Create a thread ——— Javaweb (3) Data structure experiment ( three )—— Stacks and queues TS stay vue2 Writing in the project web Front end signature plug-in _signature_pad Plug in implements electronic signature function docker Where is the image stored Qt Getting Started tutorial 【 Basic controls 】QCalendarWidget calendar control springboot How to get reality in ip address