One , Insert sort

1.1 Direct insert sort

        Spatial complexity :.

        Time complexity :. In the best case , Elements in the table are ordered , At this time, every element is inserted , You only need to compare them once without moving the elements , So the time complexity is .

        stability : Every time you insert an element, always compare and move from the back to the front , So the relative position of the same element will not change . That is to say, direct insertion sort is a stable sort method .
public class InsertSort { public static void insertSort(int[] array,int n) {
int i=0; int j=0; for(i=1;i<n;i++) {// Unordered area to be sorted int t=array[i];
for(j=i-1;j>=0&&t<array[j];j--) {// Ordered area array[j+1]=array[j]; }
array[j+1]=t; } } public static void main(String[] args) { int[] a=
{4,0,2,3,1}; insertSort(a, 5); for(int n:a) { System.out.print(n+" "); } } }
 

1.2 Shell Sort

    Spatial complexity :.

    Time complexity : When n When in a certain range , The time complexity of hill sorting is about . In the worst case, the time complexity of Hill sort is .

    stability : When records with the same key are divided into different sub tables , May change the relative order between them , So Hill sort is an unstable sort method .
public static void shell(int value[],int n,int start,int step)     {       
 int i = 0;         for(i = start + step;i < n;i += step)         {           
 int temp = value[i];             int j = 0;             for(j = i - step;j >=
start && value[j] > temp;j -= step)             {                 value[j +
step] = value[j];             }             value[j + step] = temp;         }
    }     public static void shellSort(int value[],int n)     {         int
step = n / 2;         while(step > 0)         {             int i = 0;         
   for(i = 0;i < step;i++)             {                 shell(value,n,i,step);
            }             step /= 2;         }     }     public static void
main(String[] args){         int value[] = {8,3,6,2,4,5,7,1,9,0};       
 shellSort(value,10);         System.out.println(" The sorted result is :");         int i =
0;         for(;i < 10;i++) {             System.out.print(value[i]);         }
       }
Two , Exchange sort

2.1 Bubble sorting

Spatial complexity :.

Time complexity : Worst case , Best case ( The elements in the table are basically in order ). The average time complexity is .

stability : stable .
public class BubbleSort { public static void bubbleSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { boolean flag=false; for(int j=n-1;j>i;j--) {
if(array[j-1]>array[j]) { int t=array[j-1]; array[j-1]=array[j]; array[j]=t;
flag=true; } } if(flag==false) { return; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; bubbleSort(a, 8); for(int n:a) {
System.out.print(n+" "); } } }
2.2 Quick sort

        Spatial complexity : Because quicksort is recursive , It is necessary to save the necessary information of each layer of recursive call with the help of a recursive work stack , Its capacity should be consistent with the maximum depth of recursive calls . Best case
. Worst case , Because it's going to be n-1 Recursion calls , So the depth of the stack is . On average , Depth of stack .

        Time complexity : The worst case scenario for quick sorting occurs in two areas n-1 Elements and 0 When elements , This maximum asymmetry occurs at every level of recursion , That is, when the initial sorting table is basically in order or basically in reverse order , We get the worst-case time complexity . At its best ( Balance Division ), Time complexity is
. Fast sorting is the best sorting algorithm with the best average performance among all internal sorting algorithms .

       stability : instable .
      
public class QuickSort { public static void quickSort(int[] array,int low,int
high) { if(low<high) { int index=partition(array,low,high); quickSort(array,
low, index-1); quickSort(array, index+1, high); } } public static int
partition(int[] array,int low,int high) { int pivot=array[low]; while(low<high)
{ while(low<high&&array[high]>=pivot) { --high; } array[low]=array[high];
while(low<high&&array[low]<=pivot) { low++; } array[high]=array[low]; }
array[low]=pivot; return low; } public static void main(String[] args) { int[]
a= {3,8,7,1,2,5,6,4}; quickSort(a, 0,7); for(int n:a) { System.out.print(n+"
"); } } }
Three , Select sort

3.1 Simple selection sorting

        Spatial complexity :.

        Time complexity : As can be seen from the following code , Simple selection sorting process , Very few element moves , Not more than times
( once swap need 3 Subelement movement ), The best case is mobile 0 second , At this time, the corresponding table is in order . But the number of element comparisons is independent of the initial state of the sequence , Always next . So time complexity is .

        stability : instable .
      
public class SelectSort { public static void selectSort(int[] array,int n) {
for(int i=0;i<n-1;i++) { int min=i; for(int j=i+1;j<n;j++) {
if(array[j]<array[min]) { min=j; } } if(min!=i) { int temp=array[min];
array[min]=array[i]; array[i]=temp; } } } public static void main(String[]
args) { int[] a= {3,8,7,1,2,5,6,4}; selectSort(a,8); for(int n:a) {
System.out.print(n+" "); } } }
 3.2 Heap sort

    Spatial complexity : Use only constant auxiliary units , So the space complexity is .

    Time complexity : At the best , Worst case and average case , The time complexity of heap sorting is .

    stability : instable .

Four , Merge sort

4.1 merge sort

       Spatial complexity :Merge() In operation , Because the auxiliary space is just about to be occupied n Units , But every time they merge, these spaces are released , So the spatial complexity of merging and sorting is .

       Time complexity : The time complexity of each merging is , It is necessary to merge , So the time complexity of the algorithm is .

       stability : stable .  
public class MergeSort { public static void mergeSort(int[] array,int low,int
high) { if(low<high) { int mid=(low+high)/2; mergeSort(array, low, mid);
mergeSort(array, mid+1, high); merge(array,low,mid,high); } } public static
void merge(int[] array,int low,int mid,int high) { int[] num=new
int[array.length]; for(int k=low;k<=high;k++) { num[k]=array[k]; } int i=low;
int j=mid+1; int k=i; for(;i<=mid&&j<=high;k++) { if(num[i]<num[j]) {
array[k]=num[i++]; }else { array[k]=num[j++]; } } while(i<=mid) {
array[k++]=num[i++]; } while(j<=high) { array[k++]=num[j++]; } } public static
void main(String[] args) { int[] a= {3,8,7,1,2,5,6,4}; mergeSort(a, 0,7);
for(int n:a) { System.out.print(n+" "); } } }
 

Technology
©2019-2020 Toolsou All rights reserved,
be based on STM32 Design of infrared obstacle avoidance car ( There is a code )415 Status code to background error That's what you should know Mybatis-Plus Skills Summary of artificial intelligence algorithm Keras Summary of training data loading ajax get Request Chinese parameter garbled solution experiment 11-1-6 Output string at specified position (20 branch )C Language confession practice small program ( Suitable for beginners )SSM Project's excel File upload and add to database about Navicat for mysql Of 2003 error