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

Technology
Daily Recommendation
views 5
views 2