算法面试——排序算法手撕：快排、归并、堆排模板

面试手撕排序算法是必考环节。快排、归并、堆排这三种手写频率最高。

一、快速排序

publicvoidquickSort(int[]arr,intlow,inthigh){if(low>=high)return;intpivot=partition(arr,low,high);quickSort(arr,low,pivot-1);quickSort(arr,pivot+1,high);}privateintpartition(int[]arr,intlow,inthigh){intpivot=arr[low];while(low<high){while(low<high&&arr[high]>=pivot)high--;arr[low]=arr[high];while(low<high&&arr[low]<=pivot)low++;arr[high]=arr[low];}arr[low]=pivot;returnlow;}

二、归并排序

publicvoidmergeSort(int[]arr,intleft,intright){if(left>=right)return;intmid=left+(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid+1,right);merge(arr,left,mid,right);}privatevoidmerge(int[]arr,intleft,intmid,intright){int[]temp=newint[right-left+1];inti=left,j=mid+1,k=0;while(i<=mid&&j<=right)temp[k++]=arr[i]<=arr[j]?arr[i++]:arr[j++];while(i<=mid)temp[k++]=arr[i++];while(j<=right)temp[k++]=arr[j++];System.arraycopy(temp,0,arr,left,temp.length);}

三、堆排序

publicvoidheapSort(int[]arr){for(inti=arr.length/2-1;i>=0;i--)heapify(arr,i,arr.length);for(inti=arr.length-1;i>0;i--){swap(arr,0,i);heapify(arr,0,i);}}privatevoidheapify(int[]arr,inti,intn){intlargest=i;intleft=2*i+1,right=2*i+2;if(left<n&&arr[left]>arr[largest])largest=left;if(right<n&&arr[right]>arr[largest])largest=right;if(largest!=i){swap(arr,i,largest);heapify(arr,largest,n);}}

---

💡 觉得有用的话，点赞 + 关注【张老师技术栈】吧！