排序算法核心思想平均时间最坏时间空间稳定性冒泡排序相邻元素两两比较大的往后冒O(n²)O(n²)O(1)稳定选择排序每轮选择最小值放到前面O(n²)O(n²)O(1)不稳定插入排序将当前元素插入前面有序区O(n²)O(n²)O(1)稳定希尔排序分组插入排序逐渐缩小 gapO(n log n)~O(n²)O(n²)O(1)不稳定归并排序分治拆分再合并有序数组O(n log n)O(n log n)O(n)稳定快速排序选基准小的放左大的放右O(n log n)O(n²)O(log n)不稳定堆排序建大顶堆反复取堆顶O(n log n)O(n log n)O(1)不稳定计数排序统计每个值出现次数再回填O(nk)O(nk)O(k)稳定/可稳定桶排序数据分到多个桶桶内排序再合并O(nk)O(n²)O(nk)取决于桶内排序基数排序按个位、十位、百位逐位排序O(d(nk))O(d(nk))O(nk)稳定importjava.util.*;publicclassTenSorts{// 1. 冒泡排序publicstaticvoidbubbleSort(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;}}// 2. 选择排序publicstaticvoidselectionSort(int[]arr){for(inti0;iarr.length-1;i){intmini;for(intji1;jarr.length;j){if(arr[j]arr[min])minj;}swap(arr,i,min);}}// 3. 插入排序publicstaticvoidinsertionSort(int[]arr){for(inti1;iarr.length;i){intcurarr[i];intji-1;while(j0arr[j]cur){arr[j1]arr[j];j--;}arr[j1]cur;}}// 4. 希尔排序publicstaticvoidshellSort(int[]arr){for(intgaparr.length/2;gap0;gap/2){for(intigap;iarr.length;i){intcurarr[i];intji;while(jgaparr[j-gap]cur){arr[j]arr[j-gap];j-gap;}arr[j]cur;}}}// 5. 归并排序publicstaticvoidmergeSort(int[]arr){int[]tempnewint[arr.length];mergeSort(arr,0,arr.length-1,temp);}privatestaticvoidmergeSort(int[]arr,intleft,intright,int[]temp){if(leftright)return;intmidleft(right-left)/2;mergeSort(arr,left,mid,temp);mergeSort(arr,mid1,right,temp);merge(arr,left,mid,right,temp);}privatestaticvoidmerge(int[]arr,intleft,intmid,intright,int[]temp){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];for(intp0;pk;p)arr[leftp]temp[p];}// 6. 快速排序publicstaticvoidquickSort(int[]arr){quickSort(arr,0,arr.length-1);}privatestaticvoidquickSort(int[]arr,intleft,intright){if(leftright)return;intpivotpartition(arr,left,right);quickSort(arr,left,pivot-1);quickSort(arr,pivot1,right);}privatestaticintpartition(int[]arr,intleft,intright){intpivotarr[right];intileft;for(intjleft;jright;j){if(arr[j]pivot){swap(arr,i,j);i;}}swap(arr,i,right);returni;}// 7. 堆排序publicstaticvoidheapSort(int[]arr){intnarr.length;for(intin/2-1;i0;i--){heapify(arr,n,i);}for(intin-1;i0;i--){swap(arr,0,i);heapify(arr,i,0);}}privatestaticvoidheapify(int[]arr,intheapSize,introot){intlargestroot;intleftroot*21;intrightroot*22;if(leftheapSizearr[left]arr[largest])largestleft;if(rightheapSizearr[right]arr[largest])largestright;if(largest!root){swap(arr,root,largest);heapify(arr,heapSize,largest);}}// 8. 计数排序适合非负整数publicstaticvoidcountingSort(int[]arr){if(arr.length0)return;intmaxarr[0];for(intnum:arr)maxMath.max(max,num);int[]countnewint[max1];for(intnum:arr)count[num];intindex0;for(inti0;icount.length;i){while(count[i]--0){arr[index]i;}}}// 9. 桶排序适合分布较均匀的数据publicstaticvoidbucketSort(int[]arr){if(arr.length0)return;intminarr[0],maxarr[0];for(intnum:arr){minMath.min(min,num);maxMath.max(max,num);}intbucketCountarr.length;ListListIntegerbucketsnewArrayList();for(inti0;ibucketCount;i){buckets.add(newArrayList());}for(intnum:arr){intindex(num-min)*(bucketCount-1)/(max-min1);buckets.get(index).add(num);}intk0;for(ListIntegerbucket:buckets){Collections.sort(bucket);for(intnum:bucket){arr[k]num;}}}// 10. 基数排序适合非负整数publicstaticvoidradixSort(int[]arr){if(arr.length0)return;intmaxarr[0];for(intnum:arr)maxMath.max(max,num);for(intexp1;max/exp0;exp*10){countingByDigit(arr,exp);}}privatestaticvoidcountingByDigit(int[]arr,intexp){int[]outputnewint[arr.length];int[]countnewint[10];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);}privatestaticvoidswap(int[]arr,inti,intj){inttarr[i];arr[i]arr[j];arr[j]t;}publicstaticvoidmain(String[]args){int[]arr{5,3,8,4,2,7,1,6};quickSort(arr);System.out.println(Arrays.toString(arr));}}