常见的排序算法

importjava.util.Arrays;publicclassSortingAlgorithms{// 冒泡排序publicstaticvoidbubbleSort(int[]arr){intnarr.length;// 外层循环控制排序轮数for(inti0;in-1;i){booleanswappedfalse;// 内层循环进行相邻元素比较for(intj0;jn-i-1;j){// 如果前一个元素大于后一个元素则交换if(arr[j]arr[j1]){inttemparr[j];arr[j]arr[j1];arr[j1]temp;swappedtrue;}}// 如果某一轮没有发生交换说明数组已经有序if(!swapped)break;}}// 选择排序publicstaticvoidselectionSort(int[]arr){intnarr.length;// 外层循环控制排序位置for(inti0;in-1;i){intminIndexi;// 内层循环寻找最小元素的索引for(intji1;jn;j){if(arr[j]arr[minIndex]){minIndexj;}}// 将找到的最小元素与当前位置交换inttemparr[i];arr[i]arr[minIndex];arr[minIndex]temp;}}// 插入排序publicstaticvoidinsertionSort(int[]arr){intnarr.length;// 从第二个元素开始遍历for(inti1;in;i){intkeyarr[i];// 当前要插入的元素intji-1;// 已排序部分的最后一个元素索引// 将大于key的元素向后移动while(j0arr[j]key){arr[j1]arr[j];j--;}// 插入key到正确位置arr[j1]key;}}// 希尔排序publicstaticvoidshellSort(int[]arr){intnarr.length;// 初始间隔为数组长度的一半for(intgapn/2;gap0;gap/2){// 对每个间隔进行插入排序for(intigap;in;i){intkeyarr[i];intji;// 在间隔为gap的子数组中进行插入排序while(jgaparr[j-gap]key){arr[j]arr[j-gap];j-gap;}arr[j]key;}}}// 快速排序publicstaticvoidquickSort(int[]arr,intlow,inthigh){if(lowhigh){// 获取分区点intpipartition(arr,low,high);// 递归排序分区点左边的子数组quickSort(arr,low,pi-1);// 递归排序分区点右边的子数组quickSort(arr,pi1,high);}}// 分区函数privatestaticintpartition(int[]arr,intlow,inthigh){intpivotarr[high];// 选择最后一个元素作为基准inti(low-1);// 较小元素的索引for(intjlow;jhigh;j){// 如果当前元素小于等于基准if(arr[j]pivot){i;// 交换元素inttemparr[i];arr[i]arr[j];arr[j]temp;}}// 将基准放到正确位置inttemparr[i1];arr[i1]arr[high];arr[high]temp;return(i1);}// 归并排序publicstaticvoidmergeSort(int[]arr,intleft,intright){if(leftright){intmid(leftright)/2;// 递归排序左半部分mergeSort(arr,left,mid);// 递归排序右半部分mergeSort(arr,mid1,right);// 合并两个已排序的部分merge(arr,left,mid,right);}}// 合并函数privatestaticvoidmerge(int[]arr,intleft,intmid,intright){intn1mid-left1;intn2right-mid;// 创建临时数组int[]leftArrnewint[n1];int[]rightArrnewint[n2];// 复制数据到临时数组for(inti0;in1;i)leftArr[i]arr[lefti];for(intj0;jn2;j)rightArr[j]arr[mid1j];// 合并临时数组inti0,j0,kleft;while(in1jn2){if(leftArr[i]rightArr[j]){arr[k]leftArr[i];i;}else{arr[k]rightArr[j];j;}k;}// 复制剩余元素while(in1){arr[k]leftArr[i];i;k;}while(jn2){arr[k]rightArr[j];j;k;}}// 堆排序publicstaticvoidheapSort(int[]arr){intnarr.length;// 构建最大堆for(intin/2-1;i0;i--)heapify(arr,n,i);// 逐个提取元素for(intin-1;i0;i--){// 将当前最大元素移到末尾inttemparr;arrarr[i];arr[i]temp;// 重新调整堆heapify(arr,i,0);}}// 调整堆privatestaticvoidheapify(int[]arr,intn,inti){intlargesti;intl2*i1;intr2*i2;// 如果左子节点大于根节点if(lnarr[l]arr[largest])largestl;// 如果右子节点大于根节点if(rnarr[r]arr[largest])largestr;// 如果最大值不是根节点if(largest!i){intswaparr[i];arr[i]arr[largest];arr[largest]swap;// 递归调整受影响的子树heapify(arr,n,largest);}}publicstaticvoidmain(String[]args){int[]arr1{64,34,25,12,22,11,90};int[]arr2{64,34,25,12,22,11,90};int[]arr3{64,34,25,12,22,11,90};int[]arr4{64,34,25,12,22,11,90};int[]arr5{64,34,25,12,22,11,90};int[]arr6{64,34,25,12,22,11,90};int[]arr7{64,34,25,12,22,11,90};System.out.println(原始数组: Arrays.toString(arr1));bubbleSort(arr1);System.out.println(冒泡排序结果: Arrays.toString(arr1));selectionSort(arr2);System.out.println(选择排序结果: Arrays.toString(arr2));insertionSort(arr3);System.out.println(插入排序结果: Arrays.toString(arr3));shellSort(arr4);System.out.println(希尔排序结果: Arrays.toString(arr4));quickSort(arr5,0,arr5.length-1);System.out.println(快速排序结果: Arrays.toString(arr5));mergeSort(arr6,0,arr6.length-1);System.out.println(归并排序结果: Arrays.toString(arr6));heapSort(arr7);System.out.println(堆排序结果: Arrays.toString(arr7));}}