<>1. Sorting concept :

sort , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged in ascending or descending order .

Stability of sequencing :
Two equal data , If after sorting , The sorting algorithm can ensure that its relative position does not change , The algorithm is called a stable sorting algorithm .

Sorting algorithm : Implementation principle , code implementation , Analysis algorithm stability , time & Spatial complexity , Application scenario

<> Insert sort : Insert sort and Hill Sort directly

<> Direct insert sort :

principle : The whole interval is divided into ordered intervals , Disorder interval . Select the first element of the unordered interval each time , Select the right position to insert in the ordered interval .
Time complexity :O(N^2)
Spatial complexity :O(1)
When sorting , No auxiliary space used

Spatial complexity : An algorithm needs space and problem size during operation N Mathematical expression of
Does an algorithm use : If the auxiliary space is constant (10,100,1000000) Space →O1
If the auxiliary space is a variable →newT[N]→O(N)
stability : stable
Insert sorting scenario :
Time consuming operations : To move elements , If the number of moving elements is relatively small , It's more suitable for insertion sorting The sequence is close to order or the number of data is relatively small
Most likely :O(N)→ Data order
Worst case :O(N^2)→ Data reverse order
realization :
public static void insertSort(int[] array){ for(int i=1;i<array.length;i++){
// Ordered interval :[0,i] // Disorder interval :[i,array.lenght] int v=array[i]; // The first number of unordered interval int j=i-1;
// Don't write array[j]==v Is to ensure the stability of sorting for(j>=0&&array[j]>v;j--){ array[j+1]=array[j]; } array
[j+1]=v; } }
<> Shell Sort

Hill sort is to group records by a certain increment of subscript , Use direct insertion sorting algorithm to sort each group ; As the increment decreases , Each group contains more and more keywords , When the increment is reduced to 1 Time , The whole document is just a group , The algorithm will terminate .

performance analysis :

stability : instable
realization :
public static void shellSort(int[] array){ int gap=array.length; while(gap>1){
insertSortGap(array,gap); gap=(gap/3)+1; } insertSortGap(array,1); } private
static void insertSortGap(int[] array,int gap){ for(int i=1;i<array.length;i++){
int v=array[i]; int j=i-gap; for(;j>=0&&array[j]>v;j-=gap){ array[j+gap]=array[j
]; } array[j+gap]=v; } }
<> Select sort

<> Select sort

concept : Select the maximum value from the unordered range every time ( Or minimum ) An element of , Stored at the end of an unordered interval ( Or first ), Until all data elements to be sorted are finished

realization :
public static void selectSort(int[] array){ for(int i=0;i<array.length-1;i++){
int max=0; for(int j=1;j<array.length-i;j++){ if(array[j]>array[max]){ max=j; }
} int t=array[max]; array[max]=array[array.length-i-1]; array[array.length-i-1]=
t; } }
performance analysis :

<> Heap sort

principle : The basic principle is also selective sorting , Just stop using traversal to find the maximum number of unordered intervals , Instead, it selects the largest number of unordered intervals by heap . be careful : A lot of things need to be done in ascending order ; Select small heap in descending order .
realization :
public static void heapSort(int[] array){ createHeap(array); for(int i=0;i<
array.length-1;i++){ swap(array,0,array.length-1); shiftDown(array,array.length-
i-1,0); } } private void swap(int[] array,int i,int j){ int t=array[i]; array[i]
=array[j]; array[j]=t; } private void createHeap(int[] array){ for(int i=(array.
length-1)/2;i>=0;i--){ shiftDown(array,array.length,i); } } public static void
shiftDown(int[] array,int size,int index){ int left=2*index+1; while(left<size){
int max=left; int right=2*index+2; if(right<size){ if(array[right]>array[left]){
max=right; } } if(array[index]>=array[max]){ break; } int t=array[index]; array
[index]=array[max]; array[max]=t; index=max; left=2*index+1; } }
performance analysis :

Stability : instable

©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