<> Exchange sort

<> Bubble sorting

principle : In disorder interval , By comparison of adjacent numbers , Bubble the largest number to the end of the unordered interval , Continue the process , Until the array is ordered as a whole .

realization :
public static void bubbleSort(int[] array){ for(int i=0;i<array.length-1;i++){
boolean isSorted=true; for(int j=0;j<array.length-i-1;j++){ // Equality and non exchange , Ensure stability if(
array[i]>array[j+1]){ swap(array,j,j+1); isSorted=fasle; } } if(isSorted){ break
; } } }
performance analysis

stability : stable

<> Quick sort ( important )

principle :

* Select a number from the range to be sorted , As reference value (pivot);
* Partition: Traversing the whole range to be sorted , Will be smaller than the reference value ( Can contain equal ) To the left of the reference value , Will be larger than the reference value ( Can contain equal ) To the right of the reference value ;
* Adopting the idea of divide and rule , Treat the left and right cells in the same way , Up to inter cell length == 1, Representatives are in order , Or the length between cells == 0, No data for .
realization :
public static void quickSort(int[] array) { quickSortInternal(array, 0, array.
length- 1); } //[left,right] Is the interval to be sorted private static void quickSortInternal(int[]
array, int left,int right){ if(left==right) { return; } if(left>right){ return;
} // The simplest way to select a reference value , choice array【left】 As reference value //pivoIndex Subscript representing the final stay of the reference value int pivoIndex=
partition(array,left,right); //[left,pivoIndex-1] Are less than or equal to the reference value
//[piovIndex+1,right] Are greater than or equal to the reference value quickSortInternal(array, left,pivoIndex-1);
quickSortInternal(array,pivoIndex+1,right); }
principle -partition

realization :
private static int partition(int[] array,int left,int right){ int i=left; int j
=right; int pivot=array[left]; while(i<j){ while(i<j&&array[j]>=pivot){ j--; }
while(i<j&&array[i]<=pivot){ i++; } swap(array,i,j); } swap(array,i,left);
return 1; }
Excavation method :
Basic ideas and Hoare Consistency of law , Just no more exchanges , It's assignment ( Pit filling + Dig a hole )

realization :
private static int partition(int[] array,int left,int right){ int i=left; int j
=right; int pivot=array[left]; while(i<j){ while(i<j&&array[j]>=pivot){ j--; }
array[i]=array[j]; while(i<j&&array[i]<=pivot){ i++; } array[j]=array[i]; }
array[i]=pivot; return 1; }
Forward backward traversal :
private static int partition(int[] array,int left,int right){ int d=left+1; int
pivot=array[left]; for(int i=left+1;i<=right;i++){ if(array[i]<pivot){ swap(
array,i,d); d++; } } swap(array,d-1,left); return d-1; }
performance analysis :

There is an optimal situation : If the reference value obtained each time can divide the interval into left and right parts → graphic : Binary tree equilibrium number →O(NlogN)
Worst case : After each division , Data is on one side of the reference ( The benchmark value obtained each time is just the extreme value in the interval )→ graphic : Single branch tree →O(N^2)

stability : instable

Selection of reference value :
1. Select edge ( Left or right )
2. Random selection
3. How to get the middle ( For example, taking three numbers ):array[left],array[mid],array[right] The size is based on the middle

Optimization summary :
1, It's important to choose a baseline , How many numbers are usually used
2.partition In the process, select the number equal to the reference value
3. When the interval to be sorted is less than a threshold , Use direct insert sort

<> Merge sort

principle :

Merge sort is an effective sort algorithm based on merge operation , This algorithm is a typical application of divide and conquer method . Merge ordered subsequences , To get a completely ordered sequence ; That is, to make each subsequence orderly first , To make the subsequence orderly . If two ordered tables are combined into one ordered table , It's called two-way merge .

principle - Merge two ordered arrays
private static int merge(int[] array,int left,int right){ int i=low; int j=mid;
int length=high-low; int[] extra=new int[length]; int k=0; // Select small to put extra while(i
<mid&&j<high){ // Add equal to , Guaranteed stability if(array[i]<=array[j]){ extra[k++]=array[i++]; }else
{ extra[k++]=array[j++]; } } // Put the belonging element into extra while(i<mid){ extra[k++]=array[i++];
} while(j<high){ extra[k++]=array[j++]; } // from extra Move back array for(int t=0;t<length;
t++){ // Need to move back to the original location , from low start array[low+t]=extra[t]; } }
public static void mergeSort(int[] array) { mergeSortInternal(array, 0, array.
length); } // The interval to be sorted is [low,high) private static void mergeSortInternal(int[] array,
int low,int high){ if(low>=high-1){ return; } int mid=(low+high)/2;
mergeSortInternal(array,low,mid); mergeSortInternal(array,mid,high); merge(array
,low,mid,high); }
performance analysis :
There is no so-called worst and best case in merging and sorting
Time complexity :O(n*log(n))
Spatial complexity :O(n)
stability : stable

Find the top K Words -----TOP-K
output : Output from large to small according to times , Times if the same , Output in alphabetical order

Mode 1 :
1. Count the number of occurrences of each word ;
2. Results of Statistics < word , Number of words > Key value pair , Sort ----- Comparison criteria must be provided ---- You need to write your own comparator
3. Take the first in the sorting result K Words

Method 2 :
1. Count the number of occurrences of each word ;
2. Use priority queue to < word , Number of words > Comparison of times , Created a bunch of ;
3. Before direct extraction K Elements
just so so

Front K Largest elements — Small pile
Front K Smallest elements — A lot

1. Before use K Build a heap of elements — Front K Maximum elements ( Small pile )
The small heap can ensure that the top element is always the smallest element currently encountered , Every replacement , It's all about taking the smallest out of the heap
2. Compare with the heap top element in sequence with the subsequent element ,
If it's smaller than the top element — Abandon
If it's larger than the top element —* Replace the top element directly — Heap needs to be adjusted down
*:1. Delete the top of heap element ;2. Insert the element

©2019-2020 Toolsou All rights reserved,
It's unexpected Python Cherry tree (turtle The gorgeous style of Library ) Some East 14 Pay change 16 salary , Sincerity or routine ? Browser kernel ( understand )java Four functional interfaces ( a key , simple )HashMap Explain in detail html Writing about cherry trees , Writing about cherry trees os Simple use of module