动画图解：十大经典排序算法动画与解析

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 本文链接：/kexuanxiu1163/article/details/103051357

<!--一个博主专栏付费入口结束--><link rel="stylesheet" href="/release/phoenix/template/css/ck_htmledit_views-d284373521.css"><link rel="stylesheet" href="/release/phoenix/template/css/ck_htmledit_views-d284373521.css"><div class="htmledit_views" id="content_views"><p><strong>&nbsp;</strong></p>

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

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

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

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

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

用一张图概括：

时间复杂度与空间复杂度

关于时间复杂度：

平方阶 (O(n2)) 排序 各类简单排序：直接插入、直接选择和冒泡排序。

线性对数阶 (O(nlog2n)) 排序 快速排序、堆排序和归并排序；

O(n1+§)) 排序，§ 是介于 0 和 1 之间的常数。 希尔排序

线性阶 (O(n)) 排序 基数排序，此外还有桶、箱排序。

关于稳定性：

稳定的排序算法：冒泡排序、插入排序、归并排序和基数排序。

不是稳定的排序算法：选择排序、快速排序、希尔排序、堆排序。

1. 冒泡排序

1.1 算法步骤

比较相邻的元素。如果第一个比第二个大，就交换他们两个。

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

针对所有的元素重复以上的步骤，除了最后一个。

持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

1.2 动画演示

冒泡排序动画演示

1.3 参考代码

1//Java代码实现 2publicclassBubbleSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9for(inti=1;i<arr.length;i++){10//设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。11booleanflag=true;1213for(intj=0;j<arr.length-i;j++){14if(arr[j]>arr[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 动画演示

选择排序动画演示

2.3 参考代码

1//Java代码实现 2publicclassSelectionSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 7 8//总共要经过N-1轮比较 9for(inti=0;i<arr.length-1;i++){10intmin=i;1112//每轮需要比较的次数N-i13for(intj=i+1;j<arr.length;j++){14if(arr[j]<arr[min]){15//记录目前能找到的最小值元素的下标16min=j;17}18}1920//将找到的最小值和i位置所在的值进行交换21if(i!=min){22inttmp=arr[i];23arr[i]=arr[min];24arr[min]=tmp;25}2627}28returnarr;29}30}

3. 插入排序

3.1 算法步骤

将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

3.2 动画演示

插入排序动画演示

3.3 参考代码

1//Java代码实现 2publicclassInsertSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9//从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的10for(inti=1;i<arr.length;i++){1112//记录要插入的数据13inttmp=arr[i];1415//从已经排序的序列最右边的开始比较，找到比其小的数16intj=i;17while(j>0&&tmp<arr[j-1]){18arr[j]=arr[j-1];19j--;20}2122//存在比其小的数，插入23if(j!=i){24arr[j]=tmp;25}2627}28returnarr;29}30}

4. 希尔排序

4.1 算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动画演示

希尔排序动画演示

4.3 参考代码

1//Java代码实现 2publicclassShellSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9intgap=1;10while(gap<arr.length){11gap=gap*3+1;12}1314while(gap>0){15for(inti=gap;i<arr.length;i++){16inttmp=arr[i];17intj=i-gap;18while(j>=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 算法步骤

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

5.2 动画演示

归并排序动画演示

5.3 参考代码

1//Java代码实现publicclassMergeSortimplementsIArraySort{ 2 3@Override 4publicint[]sort(int[]sourceArray)throwsException{ 5//对arr进行拷贝，不改变参数内容 6int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 7 8if(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 算法步骤

从数列中挑出一个元素，称为 “基准”（pivot）;

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

6.2 动画演示

快速排序动画演示

6.3 参考代码

1//Java代码实现 2publicclassQuickSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9returnquickSort(arr,0,arr.length-1);10}1112privateint[]quickSort(int[]arr,intleft,intright){13if(left<right){14intpartitionIndex=partition(arr,left,right);15quickSort(arr,left,partitionIndex-1);16quickSort(arr,partitionIndex+1,right);17}18returnarr;19}privateintpartition(int[]arr,intleft,intright){22//设定基准值（pivot）23intpivot=left;24intindex=pivot+1;25for(inti=index;i<=right;i++){26if(arr[i]<arr[pivot]){27swap(arr,i,index);28index++;29}30}31swap(arr,pivot,index-1);32returnindex-1;33}3435privatevoidswap(int[]arr,inti,intj){36inttemp=arr[i];37arr[i]=arr[j];38arr[j]=temp;39}4041}

7. 堆排序

7.1 算法步骤

创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

7.2 动画演示

堆排序动画演示

7.3 参考代码

1//Java代码实现 2publicclassHeapSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9intlen=arr.length;1011buildMaxHeap(arr,len);1213for(inti=len-1;i>0;i--){14swap(arr,0,i);15len--;16heapify(arr,0,len);17}18returnarr;19}privatevoidbuildMaxHeap(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(left<len&&arr[left]>arr[largest]){33largest=left;34}3536if(right<len&&arr[right]>arr[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}

8. 计数排序

8.1 算法步骤

花O(n)的时间扫描一下整个序列 A，获取最小值 min 和最大值 max

开辟一块新的空间创建新的数组 B，长度为 ( max - min + 1)

数组 B 中 index 的元素记录的值是 A 中某元素出现的次数

最后输出目标整数序列，具体的逻辑是遍历数组 B，输出相应元素以及对应的个数

8.2 动画演示

计数排序动画演示

8.3 参考代码

1//Java代码实现 2publicclassCountingSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9intmaxValue=getMaxValue(arr);1011returncountingSort(arr,maxValue);12}1314privateint[]countingSort(int[]arr,intmaxValue){15intbucketLen=maxValue+1;16int[]bucket=newint[bucketLen];1718for(intvalue:arr){19bucket[value]++;20}2122intsortedIndex=0;23for(intj=0;j<bucketLen;j++){24while(bucket[j]>0){25arr[sortedIndex++]=j;26bucket[j]--;27}28}29returnarr;30}3132privateintgetMaxValue(int[]arr){33intmaxValue=arr[0];34for(intvalue:arr){35if(maxValue<value){36maxValue=value;37}38}39returnmaxValue;40}4142}

9. 桶排序

9.1 算法步骤

设置固定数量的空桶。

把数据放到对应的桶中。

对每个不为空的桶中数据进行排序。

拼接不为空的桶中数据，得到结果

9.2 动画演示

桶排序动画演示

9.3 参考代码

1//Java代码实现 2publicclassBucketSortimplementsIArraySort{ 3 4privatestaticfinalInsertSortinsertSort=newInsertSort(); 5 6@Override 7publicint[]sort(int[]sourceArray)throwsException{ 8//对arr进行拷贝，不改变参数内容 9int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);1011returnbucketSort(arr,5);12}1314privateint[]bucketSort(int[]arr,intbucketSize)throwsException{15if(arr.length==0){16returnarr;17}1819intminValue=arr[0];20intmaxValue=arr[0];21for(intvalue:arr){22if(value<minValue){23minValue=value;24}elseif(value>maxValue){25maxValue=value;26}27}2829intbucketCount=(int)Math.floor((maxValue-minValue)/bucketSize)+1;30int[][]buckets=newint[bucketCount][0];3132//利用映射函数将数据分配到各个桶中33for(inti=0;i<arr.length;i++){34intindex=(int)Math.floor((arr[i]-minValue)/bucketSize);35buckets[index]=arrAppend(buckets[index],arr[i]);36}3738intarrIndex=0;39for(int[]bucket:buckets){40if(bucket.length<=0){41continue;42}43//对每个桶进行排序，这里使用了插入排序44bucket=insertSort.sort(bucket);45for(intvalue:bucket){46arr[arrIndex++]=value;47}48}4950returnarr;51}5253/**54*自动扩容，并保存数据55*56*@paramarr57*@paramvalue58*/59privateint[]arrAppend(int[]arr,intvalue){60arr=Arrays.copyOf(arr,arr.length+1);61arr[arr.length-1]=value;62returnarr;63}6465}

10. 基数排序

10.1 算法步骤

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零

从最低位开始，依次进行一次排序

从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

10.2 动画演示

基数排序动画演示

10.3 参考代码

1//Java代码实现 2publicclassRadixSortimplementsIArraySort{ 3 4@Override 5publicint[]sort(int[]sourceArray)throwsException{ 6//对arr进行拷贝，不改变参数内容 7int[]arr=Arrays.copyOf(sourceArray,sourceArray.length); 8 9intmaxDigit=getMaxDigit(arr);10returnradixSort(arr,maxDigit);11}1213/**14*获取最高位数15*/16privateintgetMaxDigit(int[]arr){17intmaxValue=getMaxValue(arr);18returngetNumLenght(maxValue);19}privateintgetMaxValue(int[]arr){22intmaxValue=arr[0];23for(intvalue:arr){24if(maxValue<value){25maxValue=value;26}27}28returnmaxValue;29}3031protectedintgetNumLenght(longnum){32if(num==0){33return1;34}35intlenght=0;36for(longtemp=num;temp!=0;temp/=10){37lenght++;38}39returnlenght;40}4142privateint[]radixSort(int[]arr,intmaxDigit){43intmod=10;44intdev=1;4546for(inti=0;i<maxDigit;i++,dev*=10,mod*=10){47//考虑负数的情况，这里扩展一倍队列数，其中[0-9]对应负数，[10-19]对应正数(bucket+10)48int[][]counter=newint[mod*2][0];4950for(intj=0;j<arr.length;j++){51intbucket=((arr[j]%mod)/dev)+mod;52counter[bucket]=arrayAppend(counter[bucket],arr[j]);53}5455intpos=0;56for(int[]bucket:counter){57for(intvalue:bucket){58arr[pos++]=value;59}60}61}6263returnarr;64}65privateint[]arrayAppend(int[]arr,intvalue){66arr=Arrays.copyOf(arr,arr.length+1);67arr[arr.length-1]=value;68returnarr;69}70}

</div></div>

如果觉得《动画图解：十大经典排序算法动画与解析》对你有帮助，请点赞、收藏，并留下你的观点哦！