大厂面试：六大排序

前言

本篇博客集中了冒泡，选择，二分插入，快排，归并，堆排，六大排序算法

如果觉得对你有帮助，可以点点关注，点点赞，谢谢你！

1.冒泡排序

//冒泡排序：依次比较相邻的两个数，如果前一个数比后一个数大，则交换位置，将最大的数放到最后面
    public void bubbling(int[] arr){
        for(int i=0;i<arr.length;i++){
            //为什么要j<arr.length-i-1：每次循环将最大的数排到了最后，下次不用管它
            for(int j=0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]){
                    int temp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=temp;
                }
            }
        }
    }

2.选择排序

//选择排序：每次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
    public void selection(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;
                }
            }
            int temp=arr[i];
            arr[i]=arr[min];
            arr[min]=temp;
        }
    }

3.插入排序

//插入排序：将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表
    public void insertion(int[] arr){
        for(int i=1;i<arr.length;i++){
            int temp=arr[i];
            if(temp>=arr[i-1])
                continue;
            //二分法找到插入位置
            int l=0,r=i-1;
            while(l<=r){
                int mid=(l+r)/2;
                if(arr[mid]>temp){
                    r=mid-1;
                }else{
                    l=mid+1;
                }
            }
            //将插入位置之后的元素后移一位
            for(int j=i-1;j>=l;j--){
                arr[j+1]=arr[j];
            }
            arr[l]=temp;
        }
    }

4.快速排序

核心思路就是将数组的第一个值作为基准值

双指针指向左边界和右边界

每次循环，将右边界扫过的比基准值小的放到左指针位置

将左边界扫过的比基准值大的放到右指针位置

最后找到两个指针相等的地方，填入基准值，分成左右两个数组进行递归

//快速排序：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
    public void quickSort(int[] arr,int left,int right){
        if(left>=right)
            return;
        int l=left,r=right;
        //选取基准值,第一个数
        int temp=arr[left];
        while (l < r) {
            //从右向左找比基准值小的数,放到左边
            while (l < r && arr[r] >= temp) {
                r--;
            }
            arr[l] = arr[r];
            //从左向右找比基准值大的数,放到右边
            while (l < r && arr[l] <= temp) {
                l++;
            }
            arr[r]=arr[l];
        }
        //将基准值放到中间,分界线，左右两边分别递归
        arr[l]=temp;
        quickSort(arr,left,l-1);
        quickSort(arr,l+1,right);
    }

5.归并排序

先分，左右两个子组递归，再合

合的时候就是两个有序组合成一个更大的有序组的过程

//归并排序：将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列
    public void mergeSort(int[] arr,int left,int right){
       //先分
        if(left>=right)
            return;
        int mid=(left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        //再合
        int[] temp=new int[right-left+1];
        int i=left,j=mid+1,k=0;
        while(i<=mid&&j<=right){
            if(arr[i]<=arr[j]){
                temp[k++]=arr[i++];
            }else{
                temp[k++]=arr[j++];
            }
        }
        while(i<=mid){
            temp[k++]=arr[i++];
        }
        while(j<=right){
            temp[k++]=arr[j++];
        }
        for(int m=0;m<temp.length;m++){
            arr[left+m]=temp[m];
        }
    }

6.堆排序

最大堆：根节点大于左右节点

最小堆：根节点小于左右节点

我的另一篇博客：

 数组中的第K个最大元素：堆排序-CSDN博客

//堆排序：堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点
    public void heapSort(int[] arr){
        int len=arr.length;
        //建堆
        for(int i=len/2-1;i>=0;i--){
            adjustHeap(arr,i,len);
        }
    }
    private void adjustHeap(int[] arr,int i,int len) {
        int index=i;
        int l=i*2+1,r=i*2+2;
        if(l<len&&arr[l]>arr[index])
            index=l;
        if(r<len&&arr[r]>arr[index])
            index=r;
        if(index!=i){
            int temp=arr[i];
            arr[i]=arr[index];
            arr[index]=temp;
            adjustHeap(arr,index,len);
        }
    }