Java十大排序算法

(资料图片)

1.1选择排序

选择排序算法的运作如下：

(1)从待排序序列中，找到关键字最小的元素；

(2)如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；

(3)从余下的N-1个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

/***选择排序**@paramarray*@return*/publicstaticint[]selectSort(int[]array){for(inti=0;i

1.2快速排序

快速排序算法的运作如下：

(1)从数列中挑出一个元素，称为"基准"（pivot）。

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

(3)递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

/***快速排序（递归）**@paramarr待排序数组*@paramlow左边界*@paramhigh右边界*/publicstaticint[]quickSort(int[]arr,intlow,inthigh){if(arr.length<=0){returnarr;}if(low>=high){returnarr;}intleft=low;intright=high;//挖坑1：保存基准的值inttemp=arr[left];while(left=temp){right--;}arr[left]=arr[right];//坑3：从前往后找到比基准大的元素，放到刚才挖的坑2中while(left

1.3冒泡排序

冒泡排序算法的运作如下：

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

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

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

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

/***冒泡排序**@paramarray将要被排序的数组*@return排序完成的数组*/publicstaticint[]bubbleSort(int[]array){for(inti=0;iarray[j+1]){inttemp=array[j];array[j]=array[j+1];array[j+1]=temp;flag=false;}}if(flag){break;}}returnarray;}复制代码

1.4归并排序

归并排序算法的运作如下：

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

归并排序可通过两种方式实现：

自上而下的递归

自下而上的迭代

一、递归法（假设序列共有n个元素）：

(1).将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素；

(2).将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素；

(3).重复步骤(2)，直到所有元素排序完毕。

二、迭代法

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

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

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

(4).重复步骤(3)直到某一指针到达序列尾

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

代码

/***归并排序（递归）**(1).将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素；*(2).将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素；*(3).重复步骤(2)，直到所有元素排序完毕。*@paramarr待排序数组*/publicstaticint[]mergingSort(int[]arr){if(arr.length<=1)returnarr;intnum=arr.length>>1;int[]leftArr=Arrays.copyOfRange(arr,0,num);int[]rightArr=Arrays.copyOfRange(arr,num,arr.length);System.out.println("splittwoarray:"+Arrays.toString(leftArr)+"And"+Arrays.toString(rightArr));returnmergeTwoArray(mergingSort(leftArr),mergingSort(rightArr));//不断拆分为最小单元，再排序合并}privatestaticint[]mergeTwoArray(int[]arr1,int[]arr2){inti=0,j=0,k=0;int[]result=newint[arr1.length+arr2.length];//申请额外的空间存储合并之后的数组while(i

1.5基数排序

基数排序算法的运作如下：

(1).取得数组中的最大数，并取得位数；

(2).arr为原始数组，从最低位开始取每个位组成radix数组；

(3).对radix进行计数排序（利用计数排序适用于小范围数的特点）

/***基数排序（LSD从低位开始）**基数排序适用于：*(1)数据范围较小，建议在小于1000*(2)每个数值都要大于等于0**(1).取得数组中的最大数，并取得位数；*(2).arr为原始数组，从最低位开始取每个位组成radix数组；*(3).对radix进行计数排序（利用计数排序适用于小范围数的特点）；*@paramarr待排序数组*/publicstaticvoidradixSort(int[]arr){if(arr.length<=1)return;//取得数组中的最大数，并取得位数intmax=0;for(inti=0;i0){maxDigit++;max=max/10;}System.out.println("maxDigit:"+maxDigit);//申请一个桶空间int[][]buckets=newint[10][arr.length-1];intbase=10;//从低位到高位，对每一位遍历，将所有元素分配到桶中for(inti=0;i

1.6堆排序

此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。

堆排序算法的运作如下：

(1).先将初始序列K[1…n]K[1…n]建成一个大顶堆,那么此时第一个元素K1K1最大,此堆为初始的无序区.

(2).再将关键字最大的记录K1K1(即堆顶,第一个元素)和无序区的最后一个记录KnKn交换,由此得到新的无序区K[1…n−1]K[1…n−1]和有序区K[n]K[n],且满足K[1…n−1].keys⩽K[n].keyK[1…n−1].keys⩽K[n].key

(3).交换K1K1和KnKn后,堆顶可能违反堆性质,因此需将K[1…n−1]K[1…n−1]调整为堆.然后重复步骤(2),直到无序区只有一个元素时停止.

代码

/***堆排序**1.先将初始序列K[1..n]建成一个大顶堆,那么此时第一个元素K1最大,此堆为初始的无序区.*2.再将关键字最大的记录K1(即堆顶,第一个元素)和无序区的最后一个记录Kn交换,由此得到新的无序区K[1..n−1]和有序区K[n],且满足K[1..n−1].keys⩽K[n].key*3.交换K1和Kn后,堆顶可能违反堆性质,因此需将K[1..n−1]调整为堆.然后重复步骤(2),直到无序区只有一个元素时停止.*@paramarr待排序数组*/publicstaticvoidheapSort(int[]arr){for(inti=arr.length;i>0;i--){max_heapify(arr,i);inttemp=arr[0];//堆顶元素(第一个元素)与Kn交换arr[0]=arr[i-1];arr[i-1]=temp;}}privatestaticvoidmax_heapify(int[]arr,intlimit){if(arr.length<=0||arr.length

=0;parentIdx--){if(parentIdx*2>=limit){continue;}intleft=parentIdx*2;//左子节点位置intright=(left+1)>=limit?left:(left+1);//右子节点位置，如果没有右节点，默认为左节点位置intmaxChildId=arr[left]>=arr[right]?left:right;if(arr[maxChildId]>arr[parentIdx]){//交换父节点与左右子节点中的最大值inttemp=arr[parentIdx];arr[parentIdx]=arr[maxChildId];arr[maxChildId]=temp;}}System.out.println("Max_Heapify:"+Arrays.toString(arr));}复制代码

1.7桶排序

桶排序的基本思想是：把数组arr划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。

计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。

桶排序算法的运作如下：

1.找出待排序数组中的最大值max、最小值min

2.我们使用动态数组ArrayList作为桶，桶里放的元素也用ArrayList存储。桶的数量为(max-min)/arr.length+1

3.遍历数组arr，计算每个元素arr[i]放的桶

4.每个桶各自排序

5.遍历桶数组，把排序好的元素放进输出数组

代码：

publicstaticvoidbucketSort(int[]arr){intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;for(inti=0;i>bucketArr=newArrayList<>(bucketNum);for(inti=0;i);}//将每个元素放入桶for(inti=0;i

1.8希尔排序

希尔排序算法的运作如下：

(1)选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）

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

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

/***希尔排序**@paramarray*@return*/publicstaticint[]shellSort(int[]array){for(intgap=array.length/2;gap>0;gap=gap/2){//将整个数组分为若干个子数组for(inti=gap;i=0;j=j-gap){//交换元素if(array[j]>array[j+gap]){inttemp=array[j];array[j]=array[j+gap];array[j+gap]=temp;}}}}returnarray;}复制代码

1.9插入排序

插入排序算法的运作如下：

(1)从第一个元素开始，该元素可以认为已经被排序

(2)取出下一个元素，在已经排序的元素序列中从后向前扫描

(3)如果该元素（已排序）大于新元素，将该元素移到下一位置

(4)重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

(5)将新元素插入到该位置后

(6)重复步骤(2)~(5)

/***插入排序**@paramarray*@return*/publicstaticint[]insertSort(int[]array){//长度不减1，是因为要留多一个位置方便插入数for(inti=0;i=0&&insertValue

1.10计数排序

需要三个数组:

待排序数组int[]arr=newint[]{4,3,6,3,5,1};

辅助计数数组int[]help=newint[max-min+1];//该数组大小为待排序数组中的最大值减最小值+1

输出数组int[]res=newint[arr.length];

计数排序算法的运作如下：

1.求出待排序数组的最大值max=6，最小值min=1

2.实例化辅助计数数组help，help用来记录每个元素之前出现的元素个数

3.计算arr每个数字应该在排序后数组中应该处于的位置，此时help=[1,1,4,5,6,7];

4.根据help数组求得排序后的数组，此时res=[1,3,3,4,5,6]

代码

publicstaticint[]countSort(int[]arr){intmax=Integer.MIN_VALUE;intmin=Integer.MAX_VALUE;//找出数组中的最大最小值for(inti=0;i

总结

排序算法的稳定性定义：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

口诀：

冒泡、插入、希尔、桶拍最好都是n

选择最好n方

堆、归并、快速都是nlog2n

基数n*k计数n+k

冒泡、插入、归并、桶、计数、基数稳，其他都不稳

关键词： 一篇文章