7 sorting algorithms that are often tested in interviews

给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果.

题目很简单,最近在准备秋招,By the way, a few commonly used sorting algorithms are summarized

import java.util.*;


public class Solution {
    
    public int[] MySort (int[] arr) {
    
        // write code here
        bubbleSort(arr);//57ms
        insertSort(arr);//52ms
        choiceSort(arr);//46ms
        quickSort(arr,0,arr.length-1);//46ms
        mergeSort(arr,0,arr.length-1);//39ms
        shellSort(arr);//49ms
        heapSort(arr);//42ms
        return arr;
    }
    //选择
    private void choiceSort(int[] arr){
    
        
        for(int i=0;i<arr.length;i++){
    
            int min=i;
            for(int j=i+1;j<arr.length;j++){
    
                if(arr[j]<arr[min]){
    
                    min=j;
                }
            }
            swap(arr,i,min);
        }
    }
    //插排
    private void insertSort(int[] arr){
    
        for(int i=1;i<arr.length;i++){
    
            int tmp=arr[i];
            for(int j=i-1;j>=0;j--){
    
                if(tmp<arr[j]){
    
                    swap(arr,j,j+1);
                }
            }
        }
    }
    //冒泡
    private void bubbleSort(int[] arr){
    
        for(int i=0;i<arr.length;i++){
    
            for(int j=0;j<arr.length-1;j++){
    
                if(arr[j]>arr[j+1]){
    
                    swap(arr,j,j+1);
                }
            }
        }
    }
    //快排:The key is to find a way to separate the points each time,Select the left endpoint of the interval as the standard point,Start by looking for the swap position smaller than it from the right end,Then find a larger swap position from the left,Finally, the position of the standard point can be obtained
    private void quickSort(int[] arr,int start,int end){
    
        if(start>=end) return;
        int tmp=quickHelper(arr,start,end);
// System.out.println("start:"+start+"end:"+end);
        quickSort(arr,start,tmp-1);
        quickSort(arr,tmp+1,end);
    }
    private int quickHelper(int[] arr,int start,int end){
    
        int l=start,r=end;
        int normal=arr[start];
        while(l<r){
    
            while(l<r&&arr[r]>=normal){
    
                r--;
            }
            swap(arr,l,r);
            while(l<r&&arr[l]<=normal){
    
                l++;
            }
            swap(arr,l,r);
        }
// System.out.println(l);
        return l;
    }
    //希尔:is a variant of plug-in,Just don't start from scratch every round,And there is also one decrement each timegap在
    private void shellSort(int[] arr){
    
        for(int gap=arr.length/2;gap>0;gap/=2){
    
            for(int j=gap;j<arr.length;j++){
    
                int tmp=arr[j];
                for(int i=j;i>=gap;i-=gap){
    
                    if(arr[i-gap]>tmp){
    
                        swap(arr,i-gap,i);
                    }
                }
            }
        }
    }
    //归并
    private void mergeSort(int[] arr,int start,int end){
    
        if(start>=end) return;
        int mid=start+(end-start)/2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        mergeHelper(arr,start,mid,mid+1,end);
    }
    private void mergeHelper(int[] arr,int ls,int le,int rs,int re){
    
        int i=ls,j=le,p=rs,q=re,k=0;
        int[] tmp=new int[q-i+1];
        while(i<=j&&p<=q){
    
            if(arr[i]<=arr[p]){
    
                tmp[k++]=arr[i++];
            }else{
    
                tmp[k++]=arr[p++];
            }
        }
        while(i<=le){
    
             tmp[k++]=arr[i++];
        }
        while(p<=re){
    
             tmp[k++]=arr[p++];
        }
        k=0;
        for(int s=ls;s<=re;s++){
    
            arr[s]=tmp[k++];
        }
    }
    //堆排:First construct the array as a large top heap,Then replace the top and bottom elements of the heap.Constructing a large top heap requires knowing some formulas
    private void heapSort(int[] arr){
    
        if(arr==null||arr.length==0) return;
        int len=arr.length;
        //构建大顶堆
        heapHelper1(arr,len);
        //Permutes the position of the top and last element of the heap,Then rebuild the big top heap.The build here is top-down rather than bottom-up,所以直接使用heapHelper2构建即可
        for(int i=len-1;i>=0;i--){
    
            swap(arr,0,i);
            //每次交换完,The last element of the array is in order
            len--;
            heapHelper2(arr,len,0);
        }
    }
    //构造大顶堆,arr[arr.length/2]-1is the element of the first non-leaf node
    private void heapHelper1(int[] arr,int len){
    
        for(int i=(int)Math.floor(len/2)-1;i>=0;i--){
    
            heapHelper2(arr,len,i);
        }
    }
    //
    private void heapHelper2(int[] arr,int len,int i){
    
        int l=2*i+1,r=2*i+2;
        int maxIndex=i;
        if(l<len&&arr[l]>arr[maxIndex]){
    
            maxIndex=l;
        }
        if(r<len&&arr[r]>arr[maxIndex]){
    
            maxIndex=r;
        }
        if(maxIndex!=i){
    
            swap(arr,maxIndex,i);
            heapHelper2(arr,len,maxIndex);
        }
    }
    private void swap(int[] arr,int i,int j){
    
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
}