Algorithm in hand , I have the world .

One , Algorithm classification

The time complexity and space complexity of the algorithm are reduced :

Two , Seven sorting algorithms

( One ) Bubble sort

1, basic thought

Compare two adjacent numbers in turn , Put smaller numbers in front , The larger number is put at the back .

2, Dynamic rendering

3, code implementation
// Bubble sort private static void bubbleSort(int[] arr){ // Identifying variables , Indicates whether an exchange has been made boolean
flag = false; int temp = 0; for (int i = 0; i < arr.length-1; i++) { for (int j
= 0; j < arr.length-1-i; j++) { // If the number before is larger than the number after , Then exchange if(arr[j]>arr[j+1]){ flag =
true; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } //
In a sort , Not a single exchange happened if(!flag){ break; } } }
4, Speed test

Bubble sort :120000 data ,23 second

( Two ) Select sort

1, basic thought

(1) Find the smallest element in the sequence , Put it in the first place ;

(2) Continue to find the smallest element from the remaining unordered elements , Put it in the second position ;

and so on , Until sorting is complete .

2, Dynamic rendering

3, code implementation
// Select sort public static void selectSort(int[] arr) { for (int i = 0; i <
arr.length - 1; i++) { int minIndex = i; int min = arr[minIndex]; for(int j = 1
+ i;j<arr.length;j++){ if(min > arr[j]){ min = arr[j]; minIndex = j; } }
arr[minIndex] = arr[i]; arr[i] = min; } }
4, Speed test

Select sort :120000 data ,4 second

( Three ) Insert sort

1, basic thought

hold n The first element to be sorted is regarded as an ordered table , Others are considered unordered tables , During sorting , Take one number from the unordered table at a time , Compare with the numbers in the ordered table in turn , Insert in place .

2, Dynamic rendering

3, code implementation
// Insert sort public static void insertSort(int[] arr ){ int insertVal = 0; int
insertIndex = 0; for (int i = 1; i < arr.length; i++) { // Defines the number to be inserted insertVal =
arr[i]; // Namely arr[i] The subscript of the number in front of insertIndex = i - 1; // to insertVal Find where to insert // explain //
1. insertIndex >= 0 Promise to give insertVal Find the insertion position , Don't cross the line // 2. insertVal < arr[insertIndex]
Number to insert , The insertion position has not been found // 3. You need to arr[insertIndex] Move back while(insertIndex >= 0 &&
insertVal < arr[insertIndex]){ arr[insertIndex+1] = arr[insertIndex];
insertIndex--; } // When exiting while Cycle time , Description insert location found , insertIndex + 1 if(insertIndex + 1
!= i){ arr[insertIndex+1] = insertVal; } } }
4, Speed test

Insert sort :120000 data ,1 second

( Four ) Shell Sort

1, basic thought

Hill sort is also an insertion sort , It is a more efficient version of the simple insert sort , Also known as reduced incremental sort , At the same time, the algorithm is also a breakthrough O(n²) One of the first algorithms of . It differs from insert sort in that , It takes precedence over the farther elements .

2, design sketch

3, Code instance

  There are two ways to sort .

① Shell Sort ( Bubble sort )
// Shell Sort // Use step-by-step derivation to write the Hill sort // Hill sort , The exchange method is used to insert the ordered sequence , // thinking ( algorithm ) ===> code public
static void shellSort(int[] arr){ // According to the previous step-by-step analysis , Use cycle processing for(int step =
arr.length/2;step>0;step /= 2 ){ for (int i = step; i < arr.length; i++) { //
Traverse all the elements in each group ( common step group , Each group has one element ), step step for (int j = i - step; j >= 0; j -= step) {
// If the current element is larger than the element after adding the step , Explanation exchange if (arr[j] > arr[j + step]) { int temp = arr[j];
arr[j] = arr[j + step]; arr[j + step] = temp; } } } } }
Speed test :

Bubble fahir sorting :120000 data ,11 second

② Shell Sort ( Insert sort )
// Optimize the commutative Hill sort -> Insertion method public static void shellSort2(int[] arr) { // increment step,
And gradually reduce the increment for (int step = arr.length / 2; step > 0; step /= 2) { //
From the first step Elements , Directly insert and sort the groups one by one for (int i = step; i < arr.length; i++) { int j = i;
int temp = arr[j]; if(arr[j]<arr[j-step]){ while (j - step >=
0&&temp<arr[j-step]){ arr[j] = arr[j-step]; j -= step; } arr[j] = temp; } } }
Speed test :

Insert fahir sort :12000000 data ,4 second , as the acme of perfection

( Five ) Quick sort

1, basic thought

The records to be arranged are divided into two independent parts by one pass sorting , The keywords of some records are smaller than those of others , You can sort these two parts of records separately , To achieve the whole sorting process .

2, design sketch

3, Algorithm description

* Quicksort uses divide and conquer to divide a string into two substrings ;
* Find a benchmark , Temporarily select the middle point as the datum point ;
* Reorder sequence , Those smaller than the reference value are placed in front of the reference point , The big ones are in the back ;
* Recursively sort the subsequence less than the base value and the subsequence greater than the base value ;
4, Code instance
// Quick sort public static void quickSort(int[] arr,int left, int right) { int l =
left; // Left subscript int r = right; // Right subscript //pivot Central axis value int pivot = arr[(left + right) /
2]; int temp = 0; // Temporary variable , Used in exchange //while The purpose of the cycle is to make it easier for us pivot Lower the value to the left // than pivot Put the value to the right
while( l < r) { // stay pivot Keep looking on your left , Found greater than or equal to pivot value , Just quit while( arr[l] < pivot) { l +=
1; } // stay pivot Keep looking on your right , Less than or equal to found pivot value , Just quit while(arr[r] > pivot) { r -= 1; } // If l >=
r explain pivot The left and right values of , It's all on the left // Less than or equal to pivot value , All on the right are greater than or equal to pivot value if( l >= r) { break; }
// exchange temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // If after the exchange , Find this arr[l] ==
pivot value equal r--, Move forward if(arr[l] == pivot) { r -= 1; } // If after the exchange , Find this arr[r] == pivot value
equal l++, Move back if(arr[r] == pivot) { l += 1; } } // If l == r, must l++, r--, Otherwise, it is stack overflow
if (l == r) { l += 1; r -= 1; } // Recursion to the left if(left < r) { quickSort(arr, left, r);
} // Recursion to the right if(right > l) { quickSort(arr, l, right); } }
5, Speed test

Quick sort :12000000 data ,1 second , rebel against the god

( Six ) Merge sort

1, basic thought

The classical divide and conquer strategy is used in merging and sorting , Divide and conquer divides the problem into small problems and then recursively solves them , Then the stage of governance is to patch up the answers obtained in different stages , That is, divide and rule .

2, design sketch

 3, code implementation
// Merge sort public static void mergerSort(int[] arr,int left,int right,int[] temp){
if(left<right){ // Intermediate index int middle = (left + right)/2; // Decompose recursively to the left
mergerSort(arr,left,middle,temp); // Decompose recursively to the right mergerSort(arr,middle +
1,right,temp); // merge merger(arr, left, middle, right, temp); } } // merge public
static void merger(int[] arr,int left,int middle,int right,int[] temp){ int i =
left; // initialization i, Initial index of left ordered sequence int j = middle + 1; // initialization j, The initial index of the right ordered sequence int t = 0;
// point temp The current index of the array // Let's start with the left and right ( Order ) The data is filled into the temp array // Up to the ordered sequence on the left and right , One side is finished while (i
<= middle && j <= right) {// continue // If the current element of the ordered sequence on the left , Less than or equal to the current element of the ordered sequence on the right // The current element on the left , Fill in to
temp array // then t++, i++ if(arr[i] <= arr[j]){ temp[t] = arr[i]; t++; i++; }else {
// conversely , Sets the current element of the ordered sequence on the right , Fill in to temp array temp[t] = arr[j]; t++; j++; } }
// Fill in all the data on the side with the remaining data in turn temp // The ordered sequence on the left has the remaining elements , Just fill it all in temp while (i <= middle){
temp[t] = arr[i]; t++; i++; } // The ordered sequence on the right has the remaining elements , Just fill it all in temp while (j <= right){
temp[t] = arr[j]; t++; j++; } // take temp The elements of the array are copied to the arr // be careful , You don't copy everything every time t = 0; int
tempLeft = left; // while (tempLeft <= right){ arr[tempLeft] = temp[t]; t++;
tempLeft++; } }
4, Speed test

Merge sort :12000000 data ,1 second , Amazing

( Seven ) Cardinal sort

1, basic thought

Unifies all band comparison values to the same digit length , The number with shorter data is complemented by the number with shorter data 0, And then sort from the lowest position , So sort from the lowest order to the highest order , The sequence becomes an ordered sequence .

2, Dynamic rendering

3, Code instance
// Cardinal sort public static void radixSort(int arr[]){
System.out.println(" Cardinal sort ,arr length :"+arr.length); //1. Gets the number of digits of the largest number in the array int max =
arr[0]; // Suppose the first number is the maximum number for(int i = 1; i < arr.length; i++) { if (arr[i] > max) {
max = arr[i]; } } // How many digits is the maximum number int maxLength = (max + "").length();
// Define a two-dimensional array , express 10 A bucket , Each bucket is a one-dimensional array // explain //1. Two dimensional array contains 10 One dimensional array //2.
In order to prevent the number in the time , data overflow , Then each one-dimensional array ( bucket ), Size to arr.length //3. The name is clear , Cardinality sorting is a classical algorithm that uses space for time int[][]
bucket = new int[10][arr.length];
// In order to record the information in each bucket , How many data are actually stored , We define a one-dimensional array to record the number of data in each bucket // It's understandable here
// such as :bucketElementCounts[0] , It's recorded bucket[0] The number of data in the bucket int[]
bucketElementCounts = new int[10]; // Here we use loops to process the code for(int i = 0 , n = 1; i <
maxLength; i++, n *= 10) { //( Sort the corresponding bits of each element ), The first time was a bit , The second time was ten , The third time was 100 .. for(int
j = 0; j < arr.length; j++) { // Take out the value of the corresponding bit of each element int digitOfElement = arr[j] / n %
10; // Put it into the corresponding bucket bucket[digitOfElement][bucketElementCounts[digitOfElement]] =
arr[j]; bucketElementCounts[digitOfElement]++; }
// In the order of this bucket ( The subscripts of one-dimensional array take out the data in turn , Put in the original array ) int index = 0; // Traverse every bucket , And put the data in the bucket , Put into the original array for(int
k = 0; k < bucketElementCounts.length; k++) { // If it's in the bucket , There is data , We just put it in the original array
if(bucketElementCounts[k] != 0) { // Circulating the bucket is the first step k A bucket ( That is the first k One dimensional array ), Put in for(int l = 0; l <
bucketElementCounts[k]; l++) { // Take out the element and put it in the arr arr[index++] = bucket[k][l]; } }
// The first i+1 After the wheel treatment , Need to put each bucketElementCounts[k] = 0 !!!! bucketElementCounts[k] = 0; }
} }
4, Speed test

Cardinal sort :12000000 data ,1 second , The speed is moving

Technology
©2019-2020 Toolsou All rights reserved,
Bitcoin in ten years ,VDS Opportunity or fraud Don't annoy the panda with any cat !「 Kung Fu Panda 」20 It's the year of man 4 blood sort ( one ) bubble sort Random forest R Language implementation java Realize the function of grabbing red packets Python Basic knowledge and notes python To solve the problem of dictionary writing list in CSS architecture design Vue Common features ( one )2021 year 2 Monthly programmer salary statistics , average 15144 element