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
Daily Recommendation