1. Insert sort
1.1, introduced
First, we divide the data in the array into two intervals, sorted and unsorted. The initial sorted interval has only one element, the first element of the array. The core idea of Insertion Sort algorithm is to take elements in the unsorted interval, find a suitable Insertion position in the sorted interval, and ensure that the sorted interval is always in order. This process is repeated until the unsorted interval element is empty and the algorithm ends.
1.2, analysis,
- Want to make
arr[0~0]Upper ordered, there’s only one number in this range, and of course it’s ordered.- Want to make
arr[0~1]Theta is ordered, so theta goes from thetaarr[1]Let’s start looking ahead, ifarr[1] < arr[0], just swap. Otherwise, do nothing.…
- Want to make
arr[0~i]Theta is ordered, so theta goes from thetaarr[i]Start looking forward,arr[i]This number keeps moving to the left, until the number to the left is no longer larger than it is, and it stops moving.- And the last step, I want you to
arr[0~N-1]The orderly,arr[N-1]This number keeps moving to the left, until the number to the left is no bigger than itself, and it stops moving.
The complexity of the algorithmic flow can vary depending on the state of the data.
Did you find it?
If the complexity of an algorithmic flow can vary depending on the state of the data, then you must use worst-case estimates.
Obviously, in the worst case, if arR is length N, the number of constant operations per step of insertion sort is the same as an arithmetic sequence, so
Where, a, b, and c are constants, so the time complexity of insertion sort is O(N^2).
1.3, implementation,
/ * * *@description: Insert sort *@author: erlang
* @since: 2020-08-29 * /
public class InsertionSort {
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
// [0, i-1] is ordered
for (int j = i - 1; j >= 0 && arr[j + 1] < arr[j]; j--) {
swap(arr, j, j + 1); }}}private static void swap(int[] arr, int j, int i) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
ArraySortUtils.testSort(InsertionSort::insertionSort, 100.100); }}Copy the code2. Bubble sort
2.1, introduced
The Bubble Sort algorithm only operates on two adjacent pieces of data. Each bubble operation compares the two adjacent elements to see if they meet the size relationship, and if not, swaps them. One bubble moves at least one element to its proper position, n times, and n numbers are sorted.
2.2, analysis,
In arR [0 ~ n-1] range:
arr[0]andarr[1]He who is the greatest comes1Position;arr[1]andarr[2]Whoever is older comes to position 2…arr[N-2]andarr[N-1]He who is the greatest comesN-1location- in
Arr [0 ~ N - 2)On the scale, repeat the above process, but the last step isarr[N-3]andarr[N-2]He who is the greatest comesN-2location- in
Arr [0 ~ N - 3]On the scale, repeat the above process, but the last step isarr[N-4]andarr[N-3]He who is the greatest comesN-3location…
- Finally, in
Arr (0 ~ 1] scope, repeat the process above, but the last step isarr[0]andarr[1]So whoever is bigger goes to position 1
Obviously, if the length of ARR is N, the number of constant operations at each step is still the same as an arithmetic sequence, so the total number of constant operations = A ∗(N2)+b∗N+c Total number of constant operations = A *(N^2) +b *N + C Total number of constant operations = A ∗(N2)+b∗N+c Where, A, b, and c are all constants, so the time complexity of bubble sort is O(N2)O(N^2)O(N2).
2.3, implementation,
/ * * *@description: Bubble sort *@author: erlang
* @since: the 2020-08-29 19:06 * /
public class BubbleSort {
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = arr.length - 1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1); }}}}private static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
public static void main(String[] args) {
ArraySortUtils.testSort(BubbleSort::bubbleSort, 10.100); }}Copy the code3. Selection sort
3.1, introduced
The idea of Selection Sort algorithm is similar to insertion Sort, and it can also be divided into sorted interval and unsorted interval. But selecting sort will find the smallest element in the unsorted interval every time and place it at the end of the sorted interval. And so on until all the elements are sorted.
Selection sort is an unstable in situ sort algorithm.
3.2, analysis,
In the range arR [0 to n-1], find the location of the minimum value, and then swap the minimum value to 0.
In the range arR [1 to n-1], find the location of the minimum value, and then swap the minimum value to 1.
In the range arR [2 to n-1], find the location of the minimum value, and then swap the minimum value to 2.
…
In the range arR [n-1 to n-1], find the minimum position, and then swap the minimum to the n-1 position.
Obviously, if the length of arR is N, the number of constant operations per step is like an arithmetic sequence. Therefore, total number of constant operations = A ∗(N2)+b∗N+c Total number of constant operations = A *(N^2) + B *N + C Total number of constant operations = A ∗(N2)+b∗N+ C Where A, b, and c are constants, the time complexity of selection sort is O(N2)O(N^2)O(N2).
3.3, implementation,
/ * * *@description: Select sort *@author: erlang
* @since: the 2020-08-29 10:09 * /
public class SelectionSort {
/ * * *@paramArr Array to be sorted */
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
// Record the minimum index
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
// Find the smallest index from I + 1 to length-1 less than arr[I]
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
// Swap I and minIndexswap(arr, i, minIndex); }}private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int maxSize = 10;
int maxValue = 10; ArraySortUtils.testSort(SelectionSort::selectionSort, maxSize, maxValue); }}Copy the code4. Test tool classes
import java.util.Arrays;
import java.util.function.Consumer;
/ * * *@description: Array sort tool *@author: erlang
* @since: the 2020-08-29 and * /
public class ArraySortUtils {
/** * Randomly generates the array to be tested **@paramMaxSize Maximum array length *@paramMaxValue The largest value * in the array@returnReturns the generated array */
public static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
}
return arr;
}
/** * outputs the element ** of the array@paramArray arr * /
public static void printArray(int[] arr) {
System.out.println("");
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++START");
for (int value : arr) {
System.out.print(value + "");
}
System.out.println("");
System.out.println("+++++++++++++++++++++++++++++++++++++++++++++++++++END");
}
public static void comparator(int[] arr) {
Arrays.sort(arr);
}
/** * re-copy a new array **@paramArr Array to copy *@returnReturns the copied new array */
public static int[] copyArray(int[] arr) {
if (arr == null) {
return null;
}
int[] res = new int[arr.length];
System.arraycopy(arr, 0, res, 0, arr.length);
return res;
}
/** * compares whether the elements of two arrays are equal **@paramArr1 Array 1 * to be compared@paramArr2 The array to compare 2 star@returnReturns the verification result true/false */
public static boolean isEqual(int[] arr1, int[] arr2) {
if (arr1 == null && arr2 == null) {
return true;
}
if (arr1 == null || arr2 == null) {
return false;
}
if(arr1.length ! = arr2.length) {return false;
}
for (int i = 0; i < arr1.length; i++) {
if(arr1[i] ! = arr2[i]) {return false; }}return true;
}
/** * Test whether the sorting result of the sorting method is correct **@paramThe consumer calls back the user - defined sorting method *@paramMaxSize Maximum array length *@paramMaxValue Specifies the largest number in the array, i.e. 0-maxValue */
public static void testSort(Consumer<int[]> consumer, int maxSize, int maxValue) {
int testTime = 5000;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
// Generate a new array
int[] arr1 = ArraySortUtils.generateRandomArray(maxSize, maxValue);
// Copy the new array
int[] arr2 = copyArray(arr1);
// Call back the user-defined sort method to sort arri1
consumer.accept(arr1);
// Use the system's own sorting method to sort arr2
comparator(arr2);
// Compare the results of the two treatments
if(! isEqual(arr1, arr2)) { succeed =false;
printArray(arr1);
printArray(arr2);
break; }}// Outputs test results
System.out.println(succeed ? "Nice!" : "Error!"); }}Copy the code5, summary
This section mainly introduces three kinds of common sort: insert sort, bubble sort, select sort
