排序是 408 数据结构的必考内容每年选择题 2-3 道大题可能出现。这篇把八大排序的核心代码、复杂度、稳定性一次性理清。一、插入排序类1. 直接插入排序publicvoidinsertSort(int[]arr){for(inti1;iarr.length;i){intkeyarr[i];intji-1;while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;}}2. 希尔排序publicvoidshellSort(int[]arr){for(intgaparr.length/2;gap0;gap/2){for(intigap;iarr.length;i){intji;inttemparr[j];while(j-gap0arr[j-gap]temp){arr[j]arr[j-gap];j-gap;}arr[j]temp;}}}二、交换排序类3. 冒泡排序publicvoidbubbleSort(int[]arr){for(inti0;iarr.length-1;i){booleanswappedfalse;for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){swap(arr,j,j1);swappedtrue;}}if(!swapped)break;// 提前结束}}4. 快速排序publicvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh)return;intpivotpartition(arr,low,high);quickSort(arr,low,pivot-1);quickSort(arr,pivot1,high);}privateintpartition(int[]arr,intlow,inthigh){intpivotarr[low];while(lowhigh){while(lowhigharr[high]pivot)high--;arr[low]arr[high];while(lowhigharr[low]pivot)low;arr[high]arr[low];}arr[low]pivot;returnlow;}三、选择排序类5. 简单选择排序publicvoidselectSort(int[]arr){for(inti0;iarr.length-1;i){intminIdxi;for(intji1;jarr.length;j){if(arr[j]arr[minIdx])minIdxj;}if(minIdx!i)swap(arr,i,minIdx);}}6. 堆排序publicvoidheapSort(int[]arr){for(intiarr.length/2-1;i0;i--)heapify(arr,i,arr.length);for(intiarr.length-1;i0;i--){swap(arr,0,i);heapify(arr,0,i);}}privatevoidheapify(int[]arr,inti,intn){intlargesti;intleft2*i1;intright2*i2;if(leftnarr[left]arr[largest])largestleft;if(rightnarr[right]arr[largest])largestright;if(largest!i){swap(arr,i,largest);heapify(arr,largest,n);}}四、其他排序7. 归并排序publicvoidmergeSort(int[]arr,intleft,intright){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);merge(arr,left,mid,right);}privatevoidmerge(int[]arr,intleft,intmid,intright){int[]tempnewint[right-left1];intileft,jmid1,k0;while(imidjright)temp[k]arr[i]arr[j]?arr[i]:arr[j];while(imid)temp[k]arr[i];while(jright)temp[k]arr[j];System.arraycopy(temp,0,arr,left,temp.length);}8. 基数排序publicvoidradixSort(int[]arr){intmaxArrays.stream(arr).max().getAsInt();for(intexp1;max/exp0;exp*10){countingSortByDigit(arr,exp);}}privatevoidcountingSortByDigit(int[]arr,intexp){int[]countnewint[10];int[]outputnewint[arr.length];for(intnum:arr)count[(num/exp)%10];for(inti1;i10;i)count[i]count[i-1];for(intiarr.length-1;i0;i--){intdigit(arr[i]/exp)%10;output[count[digit]-1]arr[i];count[digit]--;}System.arraycopy(output,0,arr,0,arr.length);}五、对比总结排序算法平均最好最坏空间稳定直接插入O(n²)O(n)O(n²)O(1)✅希尔排序O(n^1.3)O(n)O(n²)O(1)❌冒泡排序O(n²)O(n)O(n²)O(1)✅快速排序O(n log n)O(n log n)O(n²)O(log n)❌简单选择O(n²)O(n²)O(n²)O(1)❌堆排序O(n log n)O(n log n)O(n log n)O(1)❌归并排序O(n log n)O(n log n)O(n log n)O(n)✅基数排序O(d(nr))O(d(nr))O(d(nr))O®✅几个常考结论稳定的排序插入、冒泡、归并、基数不稳定的排序希尔、快速、选择、堆堆排序的最坏情况也是 O(n log n)快排最坏 O(n²)有序或逆序时 觉得有用的话点赞 关注【张老师技术栈】吧
数据结构——排序算法全总结：八大排序代码模板 + 408 真题
发布时间：2026/7/16 1:17:37
排序是 408 数据结构的必考内容每年选择题 2-3 道大题可能出现。这篇把八大排序的核心代码、复杂度、稳定性一次性理清。一、插入排序类1. 直接插入排序publicvoidinsertSort(int[]arr){for(inti1;iarr.length;i){intkeyarr[i];intji-1;while(j0arr[j]key){arr[j1]arr[j];j--;}arr[j1]key;}}2. 希尔排序publicvoidshellSort(int[]arr){for(intgaparr.length/2;gap0;gap/2){for(intigap;iarr.length;i){intji;inttemparr[j];while(j-gap0arr[j-gap]temp){arr[j]arr[j-gap];j-gap;}arr[j]temp;}}}二、交换排序类3. 冒泡排序publicvoidbubbleSort(int[]arr){for(inti0;iarr.length-1;i){booleanswappedfalse;for(intj0;jarr.length-1-i;j){if(arr[j]arr[j1]){swap(arr,j,j1);swappedtrue;}}if(!swapped)break;// 提前结束}}4. 快速排序publicvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh)return;intpivotpartition(arr,low,high);quickSort(arr,low,pivot-1);quickSort(arr,pivot1,high);}privateintpartition(int[]arr,intlow,inthigh){intpivotarr[low];while(lowhigh){while(lowhigharr[high]pivot)high--;arr[low]arr[high];while(lowhigharr[low]pivot)low;arr[high]arr[low];}arr[low]pivot;returnlow;}三、选择排序类5. 简单选择排序publicvoidselectSort(int[]arr){for(inti0;iarr.length-1;i){intminIdxi;for(intji1;jarr.length;j){if(arr[j]arr[minIdx])minIdxj;}if(minIdx!i)swap(arr,i,minIdx);}}6. 堆排序publicvoidheapSort(int[]arr){for(intiarr.length/2-1;i0;i--)heapify(arr,i,arr.length);for(intiarr.length-1;i0;i--){swap(arr,0,i);heapify(arr,0,i);}}privatevoidheapify(int[]arr,inti,intn){intlargesti;intleft2*i1;intright2*i2;if(leftnarr[left]arr[largest])largestleft;if(rightnarr[right]arr[largest])largestright;if(largest!i){swap(arr,i,largest);heapify(arr,largest,n);}}四、其他排序7. 归并排序publicvoidmergeSort(int[]arr,intleft,intright){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid);mergeSort(arr,mid1,right);merge(arr,left,mid,right);}privatevoidmerge(int[]arr,intleft,intmid,intright){int[]tempnewint[right-left1];intileft,jmid1,k0;while(imidjright)temp[k]arr[i]arr[j]?arr[i]:arr[j];while(imid)temp[k]arr[i];while(jright)temp[k]arr[j];System.arraycopy(temp,0,arr,left,temp.length);}8. 基数排序publicvoidradixSort(int[]arr){intmaxArrays.stream(arr).max().getAsInt();for(intexp1;max/exp0;exp*10){countingSortByDigit(arr,exp);}}privatevoidcountingSortByDigit(int[]arr,intexp){int[]countnewint[10];int[]outputnewint[arr.length];for(intnum:arr)count[(num/exp)%10];for(inti1;i10;i)count[i]count[i-1];for(intiarr.length-1;i0;i--){intdigit(arr[i]/exp)%10;output[count[digit]-1]arr[i];count[digit]--;}System.arraycopy(output,0,arr,0,arr.length);}五、对比总结排序算法平均最好最坏空间稳定直接插入O(n²)O(n)O(n²)O(1)✅希尔排序O(n^1.3)O(n)O(n²)O(1)❌冒泡排序O(n²)O(n)O(n²)O(1)✅快速排序O(n log n)O(n log n)O(n²)O(log n)❌简单选择O(n²)O(n²)O(n²)O(1)❌堆排序O(n log n)O(n log n)O(n log n)O(1)❌归并排序O(n log n)O(n log n)O(n log n)O(n)✅基数排序O(d(nr))O(d(nr))O(d(nr))O®✅几个常考结论稳定的排序插入、冒泡、归并、基数不稳定的排序希尔、快速、选择、堆堆排序的最坏情况也是 O(n log n)快排最坏 O(n²)有序或逆序时 觉得有用的话点赞 关注【张老师技术栈】吧
