private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;
while (lindex<=mid&&rindex<=r) {//先左右比较兼并
if(array[lindex]<=array[rindex])
{
team[teamindex++]=array[lindex++];
}
else {
team[teamindex++]=array[rindex++];
}
}
while(lindex<=mid)//当一个越界后剩余按序列添加即可
{
team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{
team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{
array[l+i]=team[i];
}
}
桶类排序桶排序是一种用空间换取时间的排序，桶排序重要的是它的思想，而不是详细完成，时间复杂度最好能够是线性O(n)，桶排序不是基于比较的排序而是一种分配式的。桶排序从字面的意思上看：
桶：若干个桶，阐明此类排序将数据放入若干个桶中。
桶：每个桶有容量，桶是有一定容积的容器，所以每个桶中能够有多个元素。
桶：从全体来看，整个排序更希望桶可以更匀称，即既不溢出(太多)又不太少。
桶排序的思想为： 「将待排序的序列分到若干个桶中，每个桶内的元素再停止一般排序。」 当然桶排序选择的方案跟详细的数据有关系，桶排序是一个比较普遍的概念，并且计数排序是一种特殊的桶排序，基数排序也是树立在桶排序的基础上。在数据散布平均且每个桶元素趋近一个时间复杂度能到达O(n),但是假设数据范围较大且相对集中就不太适宜运用桶排序。
完成一个复杂桶排序：
import java.util.ArrayList;
import java.util.List;
//微信群众号：bigsai
public class bucketSort {
public static void main(String[] args) {
int a[]= {1,8,7,44,42,46,38,34,33,17,15,16,27,28,24};
List[] buckets=new ArrayList[5];
for(int i=0;i<buckets.length;i++)//初始化
{
buckets[i]=new ArrayList<Integer>();
}
for(int i=0;i<a.length;i++)//将待排序序列放入对应桶中
{
int index=a[i]/10;//对应的桶号
buckets[index].add(a[i]);
}
for(int i=0;i<buckets.length;i++)//每个桶内停止排序(运用系统自带快排)
{
buckets[i].sort(null);
for(int j=0;j<buckets[i].size();j++)//特地打印输入
{
System.out.print(buckets[i].get(j)+" ");
}
}
}
}
计数排序计数排序是一种特殊的桶排序，每个桶的大小为1，每个桶不在用List表示，而通常用一个值用来计数。
在 「设计详细算法的时分」 ，先找到最小值min，再找最大值max。然后创立这个区间大小的数组,从min的位置末尾计数，这样就可以最大水平的紧缩空间，提空中间的运用效率。
public static void countSort(int a[])
{
int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;
for(int i=0;i<a.length;i++)//找到max和min
{
if(a[i]<min)
min=a[i];
if(a[i]>max)
max=a[i];
}
int count[]=new int[max-min+1];//对元素停止计数
for(int i=0;i<a.length;i++)
{
count[a[i]-min]++;
}
//排序取值
int index=0;
for(int i=0;i<count.length;i++)
{
while (count[i]-->0) {
a[index++]=i+min;//有min才是真正值
}
}
}
基数排序 (责任编辑：admin)