大厂面试：六大排序

前言

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

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

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);}}