十大经典排序算法动画与解析，看我就够了！（配代码完全版）五分钟学算法

排序算法是《数据结构与算法》中最基本的算法之一。

排序算法可以分为内部排序和外部排序。

内部排序是数据记录在内存中进行排序。

而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。

常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。

用一张图概括：

image

1//Java代码实现2publicclassBubbleSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6//对arr进行拷贝，不改变参数内容7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);89for(inti=1;iarr[j+1]){15inttmp=arr[j];16arr[j]=arr[j+1];17arr[j+1]=tmp;1819flag=false;20}21}2223if(flag){24break;25}26}27returnarr;28}29}2.选择排序2.1算法步骤2.2动画演示image

1//Java代码实现2publicclassSelectionSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);78//总共要经过N-1轮比较9for(inti=0;i

1//Java代码实现2publicclassInsertSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6//对arr进行拷贝，不改变参数内容7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);89//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的10for(inti=1;i0&&tmp

1//Java代码实现2publicclassShellSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6//对arr进行拷贝，不改变参数内容7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);89intgap=1;10while(gap0){15for(inti=gap;i=0&&arr[j]>tmp){19arr[j+gap]=arr[j];20j-=gap;21}22arr[j+gap]=tmp;23}24gap=(int)Math.floor(gap/3);25}2627returnarr;28}29}5.归并排序5.1算法步骤5.2动画演示image

1publicclassMergeSortimplementsIArraySort{23@Override4publicint[]sort(int[]sourceArray)throwsException{5//对arr进行拷贝，不改变参数内容6int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);78if(arr.length<2){9returnarr;10}11intmiddle=(int)Math.floor(arr.length/2);1213int[]left=Arrays.copyOfRange(arr,0,middle);14int[]right=Arrays.copyOfRange(arr,middle,arr.length);1516returnmerge(sort(left),sort(right));17}1819protectedint[]merge(int[]left,int[]right){20int[]result=newint[left.length+right.length];21inti=0;22while(left.length>0&&right.length>0){23if(left[0]<=right[0]){24result[i++]=left[0];25left=Arrays.copyOfRange(left,1,left.length);26}else{27result[i++]=right[0];28right=Arrays.copyOfRange(right,1,right.length);29}30}3132while(left.length>0){33result[i++]=left[0];34left=Arrays.copyOfRange(left,1,left.length);35}3637while(right.length>0){38result[i++]=right[0];39right=Arrays.copyOfRange(right,1,right.length);40}4142returnresult;43}4445}6.快速排序6.1算法步骤6.2动画演示image

1//Java代码实现2publicclassQuickSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6//对arr进行拷贝，不改变参数内容7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);89returnquickSort(arr,0,arr.length-1);10}1112privateint[]quickSort(int[]arr,intleft,intright){13if(left

1//Java代码实现2publicclassHeapSortimplementsIArraySort{34@Override5publicint[]sort(int[]sourceArray)throwsException{6//对arr进行拷贝，不改变参数内容7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);89intlen=arr.length;1011buildMaxHeap(arr,len);1213for(inti=len-1;i>0;i--){14swap(arr,0,i);15len--;16heapify(arr,0,len);17}18returnarr;19}2021privatevoidbuildMaxHeap(int[]arr,intlen){22for(inti=(int)Math.floor(len/2);i>=0;i--){23heapify(arr,i,len);24}25}2627privatevoidheapify(int[]arr,inti,intlen){28intleft=2*i+1;29intright=2*i+2;30intlargest=i;3132if(leftarr[largest]){33largest=left;34}3536if(rightarr[largest]){37largest=right;38}3940if(largest!=i){41swap(arr,i,largest);42heapify(arr,largest,len);43}44}4546privatevoidswap(int[]arr,inti,intj){47inttemp=arr[i];48arr[i]=arr[j];49arr[j]=temp;50}5152}