面试必备排序算法java版（冒泡、快排、归并、堆排）

以下四个排序是面试时的高频考点，直接背住，快速手撕。

冒泡排序（注意使用flag提升效率）

public class bubble_sort {
    public void bubblesort(int[] nums){
        if(nums.length<=1) return;
        boolean flag=true;//标记位，如果已经有序，立即结束
        for(int i=0;i<nums.length-1;i++){
            for(int j=0;j<nums.length-1-i;j++){
                if(nums[j]>nums[j+1]){
                    int tmp=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=tmp;
                    flag=false;
                }
            }
            if(flag) break;
            else flag=true;
        }
    }
}

快排（必背）

public class quick_sort {
    public void quicksort(int[] nums){
        if(nums.length<=1) return;
        quicksort(nums,0,nums.length-1);
    }
    public void quicksort(int[] nums,int low,int high){
        if(low<high){
            int pivot = partition(nums, low, high);
            quicksort(nums,low,pivot-1);
            quicksort(nums,pivot+1,high);
        }
    }
    public int partition(int[] nums,int low,int high){
        if(low==high) return low;
        int i=low,j=high+1;
        int pivot=nums[low];//以pivot为中心，左边的都比pivot小，右边的都比pivot大
        while(true){
            while(nums[++i]<pivot){
                if(i>=high) break;
            }
            while(nums[--j]>pivot){
                if(j<=low) break;
            }
            if(i>=j) break;
            swap(nums,i,j);
        }
        swap(nums,low,j);
        return j;
    }
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

归并（必背）

public class merge_sort {
    public void mergesort(int[] nums){
        if(nums.length<=1) return;
        int[] tmp=new int[nums.length];
        mergesort(nums,tmp,0,nums.length-1);
    }
    public void mergesort(int[] nums,int[] tmp,int low,int high){
        if(low<high){
            int mid=low+(high-low)/2;
            mergesort(nums,tmp,low,mid);
            mergesort(nums,tmp,mid+1,high);
            merge(nums,tmp,low,mid,high);
        }
    }
    public void merge(int[] nums,int[] tmp,int low,int mid,int high){
        int i=low,j=mid+1;
        int index=low;
        while(i<=mid&&j<=high) {
            if (nums[i] < nums[j]) tmp[index++] = nums[i++];
            else tmp[index++] = nums[j++];
        }
        while(i<=mid) tmp[index++]=nums[i++];
        while(j<=high) tmp[index++]=nums[j++];
        for(int k=low;k<=high;k++){
            nums[k]=tmp[k];
        }
    }
}

堆排序（主要是建堆）

//以大根堆为例
public class heap_sort {
    public void heapsort(int[] nums){
        int len=nums.length;
        build_heap(nums,len);
        for(int i=len-1;i>=0;i--){
            swap(nums,0,i);
            heapify(nums,0,i);
        }
    }
    public void build_heap(int[] nums,int len){
        for(int i=len/2-1;i>=0;i--){//从最后一个非叶子节点开始倒序建堆
            heapify(nums,i,len);
        }
    }
    public void heapify(int[] nums,int i,int len){
        int left=2*i+1,right=2*i+2;
        int index=i;//比较当前节点左右子节点确定调换位置
        if(left<len&&nums[left]>nums[index]) index=left;
        if(right<len&&nums[right]>nums[index]) index=right;
        if(index!=i){
            swap(nums,index,i);
            heapify(nums,index,len);
        }
    }
    public void swap(int[] nums,int i,int j){
        int tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

主函数调用

public class Main {
    public static void main(String[] args) {
	  //以归并排序为例
        merge_sort sort=new merge_sort();
        int[] nums={0,1,2,3,4,-4,-6,-1};
        sort.mergesort(nums);
        for (int num : nums) {
            System.out.print(num+" ");
        }
    }
}