排序算法之线性排序(计数排序和桶排序)--Java语言
程序员文章站
2022-05-12 16:34:57
...
之前的文章讲到的都是比较算法，以下链接是之前文章提到过的一些基本排序方法，其时间复杂度的下界是O(nlogn)。今天提到的两个主角分别是计数排序和桶排序，其时间复杂度好的情况下能够达到O(n)，它们不属于比较排序。
首先，计数排序相当于是值与下标以及原序列中小于等于当前值的数目之间的一个相互映射关系，所以是一个线性关系。计数排序需要引入一个值K，K的值至少为原序列中的最大值加1。引入一个数组C[K]，序列初始值都为0，开始遍历一遍原序列A[],当遍历到A[j],C[A[j]]+=1。然后对C作进一步处理：从第二个元素开始逐个加上前一个数，并保存。此时C[i]用于存储小于等于i的个数。因此i越大个数越多，i在原序列的位置越靠后，则用一个B[n]，存储排序结果，此时B序列中C[A[j]]位置应当存储A[j]。排序完成，时间复杂度为O(2n+2K)，即O(n+k),当K=O(n)，时间复杂度是线性的。所以计数排序在序列最大值与序列个数相近或者序列最大值不是特别大的情况下效果尤佳。
代码：
import java.util.Arrays;
public class CountingSort {
public static int[] countingSort(int[] A,int n,int[] B,int k)
{
//下标以及值的映射关系，通过计数法来确定当前数在有序数列中的位置
int[] C=new int[k];
for(int i=0;i<k;i++)
C[i]=0;
for(int j=0;j<n;j++)
C[A[j]]+=1;
for(int h=1;h<k;h++)
C[h]=C[h]+C[h-1];//C[h]表示所有小于等于h的元素个数
for(int w=n-1;w>=0;w--)
{
C[A[w]]-=1;//通过C[h]的值即小于等于h的个数来确定该元素A[w]在B数组的位置，
B[C[A[w]]]=A[w];//C[h]越小则说明小于等于A[w]的数越少，即A[w]越小，在B中的位置越靠前，实现排序目的。
}
return B;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A= {10,6,5,4,12,8,7};
int[] Q= {0,1,0,1,0,2,2,1,0};
int[] B=new int[A.length];
int n=A.length;
int k=13;
System.out.println("计数排序后的结果：");
System.out.println(Arrays.toString(countingSort(A,n,B,k)));
}
}
测试结果：
计数排序后的结果：
[4, 5, 6, 7, 8, 10, 12]接下来讲述的是桶排序，其实桶排序的与计数排序类似，需要引入一个变量K，K的值大于序列的最大值。此处K表示有K个桶，引入一个表示桶的数组buckets[K]，初始时各元素都为0,遍历一遍待排序序列A，序列值即为其对应的桶的序号，直接扔进对应的桶：buckets[A[i]]+=1。遍历完之后，开始按桶序号从小到大遍历桶，检查相应的元素，然后逐个存入A中，遍历结束则排序完成，获得的A为有序序列。
由上可知，元素只需遍历一次原序列，然后需要遍历两次桶，所以时间复杂度为O(n+2K)，属于线性排序。
代码：
import java.util.Arrays;
public class BucketSort {
public static int[] bucketSort(int[] A,int n,int k)
{
//将值作为桶的序号，将每个元素丢进相应的桶中，然后进行遍历桶，当桶的数字为多少时，则输出多少个桶的序号即元素值。
int w,h,u;
int[] buckets=new int[k];
for(int j=0;j<k;j++)
buckets[j]=0;
for(int i=0;i<n;i++)
buckets[A[i]]+=1;
for(w=0,h=0;h<k;h++)
{
for(u=buckets[h];u>0;--u)
A[w++]=h;
}
return A;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] A= {10,6,5,4,12,8,7};
int n=A.length;
int k=13;
System.out.println("桶排序后的有序序列为：");
System.out.println(Arrays.toString(bucketSort(A,n,k)));
}
}
测试结果：
桶排序后的有序序列为：
[4, 5, 6, 7, 8, 10, 12]由上可知，无论是计数排序还是桶排序，都需要引进一个K，而K跟序列的最值相关，所以这两个线性排序方法适用于固定序列以及K=O(n)的序列。
转发请注明：转自http://blog.csdn.net/carson0408/article/details/78654904