六 歸并排序
算法思想是每次把待排序列分成兩部分，分別對(duì)這兩部分遞歸地用歸并排序，完成后把這兩個(gè)子部分合并成一個(gè)
序列。
歸并排序借助一個(gè)全局性臨時(shí)數(shù)組來方便對(duì)子序列的歸并，該算法核心在于歸并。
package algorithms;
import java.lang.reflect.Array;
/**
* @author yovn
*
*/
public class MergeSorter<E extends Comparable<E>> extends Sorter<E> {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@SuppressWarnings("unchecked")
@Override
public void sort(E[] array, int from, int len) {
if(len<=1)return;
E[] temporary=(E[])Array.newInstance(array[0].getClass(),len);
merge_sort(array,from,from+len-1,temporary);
}
private final void merge_sort(E[] array, int from, int to, E[] temporary) {
if(to<=from)
{
return;
}
int middle=(from+to)/2;
merge_sort(array,from,middle,temporary);
merge_sort(array,middle+1,to,temporary);
merge(array,from,to,middle,temporary);
}
private final void merge(E[] array, int from, int to, int middle, E[] temporary) {
int k=0,leftIndex=0,rightIndex=to-from;
System.arraycopy(array, from, temporary, 0, middle-from+1);
for(int i=0;i<to-middle;i++)
{
temporary[to-from-i]=array[middle+i+1];
}
while(k<to-from+1)
{
if(temporary[leftIndex].compareTo(temporary[rightIndex])<0)
{
array[k+from]=temporary[leftIndex++];
}
else
{
array[k+from]=temporary[rightIndex--];
}
k++;
}
}
}
七 堆排序
堆是一種完全二叉樹，一般使用數(shù)組來實(shí)現(xiàn)。
堆主要有兩種核心操作，
1）從指定節(jié)點(diǎn)向上調(diào)整(shiftUp)
2）從指定節(jié)點(diǎn)向下調(diào)整(shiftDown)
建堆，以及刪除堆定節(jié)點(diǎn)使用shiftDwon,而在插入節(jié)點(diǎn)時(shí)一般結(jié)合兩種操作一起使用。
堆排序借助最大值堆來實(shí)現(xiàn)，第i次從堆頂移除最大值放到數(shù)組的倒數(shù)第i個(gè)位置，然后shiftDown到倒數(shù)第i+1個(gè)位置,一共執(zhí)行N此調(diào)整，即完成排序。
顯然，堆排序也是一種選擇性的排序，每次選擇第i大的元素。
package algorithms;
/**
* @author yovn
*
*/
public class HeapSorter<E extends Comparable<E>> extends Sorter<E> {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
build_heap(array,from,len);
for(int i=0;i<len;i++)
{
//swap max value to the (len-i)-th position
swap(array,from,from+len-1-i);
shift_down(array,from,len-1-i,0);//always shiftDown from 0
}
}
private final void build_heap(E[] array, int from, int len) {
int pos=(len-1)/2;//we start from (len-1)/2, because branch's node +1=leaf's node, and all leaf node is already a heap
for(int i=pos;i>=0;i--)
{
shift_down(array,from,len,i);
}
}
private final void shift_down(E[] array,int from, int len, int pos)
{
E tmp=array[from+pos];
int index=pos*2+1;//use left child
while(index<len)//until no child
{
if(index+1<len&&array[from+index].compareTo(array[from+index+1])<0)//right child is bigger
{
index+=1;//switch to right child
}
if(tmp.compareTo(array[from+index])<0)
{
array[from+pos]=array[from+index];
pos=index;
index=pos*2+1;
}
else
{
break;
}
}
array[from+pos]=tmp;
}
}
八 桶式排序
桶式排序不再是基于比較的了，它和基數(shù)排序同屬于分配類的排序，這類排序的特點(diǎn)是事先要知道待排序列的一些特征。
桶式排序事先要知道待排序列在一個(gè)范圍內(nèi)，而且這個(gè)范圍應(yīng)該不是很大的。
比如知道待排序列在[0,M）內(nèi)，那么可以分配M個(gè)桶，第I個(gè)桶記錄I的出現(xiàn)情況，最后根據(jù)每個(gè)桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。
這里我們用兩個(gè)臨時(shí)性數(shù)組，一個(gè)用于記錄位置信息，一個(gè)用于方便輸出數(shù)據(jù)成有序方式，另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開始，你可以把每個(gè)數(shù)減去最小的數(shù)。
package algorithms;
/**
* @author yovn
*
*/
public class BucketSorter {
public void sort(int[] keys,int from,int len,int max)
{
int[] temp=new int[len];
int[] count=new int[max];
for(int i=0;i<len;i++)
{
count[keys[from+i]]++;
}
//calculate position info
for(int i=1;i<max;i++)
{
count[i]=count[i]+count[i-1];//this means how many number which is less or equals than i,thus it is also position + 1
}
System.arraycopy(keys, from, temp, 0, len);
for(int k=len-1;k>=0;k--)//from the ending to beginning can keep the stability
{
keys[--count[temp[k]]]=temp[k];// position +1 =count
}
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16};
BucketSorter sorter=new BucketSorter();
sorter.sort(a,0,a.length,20);//actually is 18, but 20 will also work
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}
}
}
九 基數(shù)排序
基數(shù)排序可以說是擴(kuò)展了的桶式排序，比如當(dāng)待排序列在一個(gè)很大的范圍內(nèi)，比如0到999999內(nèi)，那么用桶式排序是很浪費(fèi)空間的。而基數(shù)排序把每個(gè)排序碼拆成由d個(gè)排序碼，比如任何一個(gè)6位數(shù)（不滿六位前面補(bǔ)0）拆成6個(gè)排序碼，分別是個(gè)位的，十位的，百位的。。。。
排序時(shí)，分6次完成，每次按第i個(gè)排序碼來排。
一般有兩種方式:
1) 高位優(yōu)先(MSD)： 從高位到低位依次對(duì)序列排序
2）低位優(yōu)先(LSD)： 從低位到高位依次對(duì)序列排序
計(jì)算機(jī)一般采用低位優(yōu)先法（人類一般使用高位優(yōu)先），但是采用低位優(yōu)先時(shí)要確保排序算法的穩(wěn)定性。
基數(shù)排序借助桶式排序，每次按第N位排序時(shí)，采用桶式排序。對(duì)于如何安排每次落入同一個(gè)桶中的數(shù)據(jù)有兩種安排方法：
1）順序存儲(chǔ)：每次使用桶式排序，放入r個(gè)桶中，，相同時(shí)增加計(jì)數(shù)。
2）鏈?zhǔn)酱鎯?chǔ)：每個(gè)桶通過一個(gè)靜態(tài)隊(duì)列來跟蹤。
package algorithms;
import java.util.Arrays;
/**
* @author yovn
*
*/
public class RadixSorter {
public static boolean USE_LINK=true;
/**
*
* @param keys
* @param from
* @param len
* @param radix key's radix
* @param d how many sub keys should one key divide to
*/
public void sort(int[] keys,int from ,int len,int radix, int d)
{
if(USE_LINK)
{
link_radix_sort(keys,from,len,radix,d);
}
else
{
array_radix_sort(keys,from,len,radix,d);
}
}
private final void array_radix_sort(int[] keys, int from, int len, int radix,
int d)
{
int[] temporary=new int[len];
int[] count=new int[radix];
int R=1;
for(int i=0;i<d;i++)
{
System.arraycopy(keys, from, temporary, 0, len);
Arrays.fill(count, 0);
for(int k=0;k<len;k++)
{
int subkey=(temporary[k]/R)%radix;
count[subkey]++;
}
for(int j=1;j<radix;j++)
{
count[j]=count[j]+count[j-1];
}
for(int m=len-1;m>=0;m--)
{
int subkey=(temporary[m]/R)%radix;
--count[subkey];
keys[from+count[subkey]]=temporary[m];
}
R*=radix;
}
}
private static class LinkQueue
{
int head=-1;
int tail=-1;
}
private final void link_radix_sort(int[] keys, int from, int len, int radix, int d) {
int[] nexts=new int[len];
LinkQueue[] queues=new LinkQueue[radix];
for(int i=0;i<radix;i++)
{
queues[i]=new LinkQueue();
}
for(int i=0;i<len-1;i++)
{
nexts[i]=i+1;
}
nexts[len-1]=-1;
int first=0;
for(int i=0;i<d;i++)
{
link_radix_sort_distribute(keys,from,len,radix,i,nexts,queues,first);
first=link_radix_sort_collect(keys,from,len,radix,i,nexts,queues);
}
int[] tmps=new int[len];
int k=0;
while(first!=-1)
{
tmps[k++]=keys[from+first];
first=nexts[first];
}
System.arraycopy(tmps, 0, keys, from, len);
}
private final void link_radix_sort_distribute(int[] keys, int from, int len,
int radix, int d, int[] nexts, LinkQueue[] queues,int first) {
for(int i=0;i<radix;i++)queues[i].head=queues[i].tail=-1;
while(first!=-1)
{
int val=keys[from+first];
for(int j=0;j<d;j++)val/=radix;
val=val%radix;
if(queues[val].head==-1)
{
queues[val].head=first;
}
else
{
nexts[queues[val].tail]=first;
}
queues[val].tail=first;
first=nexts[first];
}
}
private int link_radix_sort_collect(int[] keys, int from, int len,
int radix, int d, int[] nexts, LinkQueue[] queues) {
int first=0;
int last=0;
int fromQueue=0;
for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);
first=queues[fromQueue].head;
last=queues[fromQueue].tail;
while(fromQueue<radix-1&&queues[fromQueue].head!=-1)
{
fromQueue+=1;
for(;(fromQueue<radix-1)&&(queues[fromQueue].head==-1);fromQueue++);
nexts[last]=queues[fromQueue].head;
last=queues[fromQueue].tail;
}
if(last!=-1)nexts[last]=-1;
return first;
}
/**
* @param args
*/
public static void main(String[] args) {
int[] a={1,4,8,3,2,9,5,0,7,6,9,10,9,135,14,15,11,222222222,1111111111,12,17,45,16};
USE_LINK=true;
RadixSorter sorter=new RadixSorter();
sorter.sort(a,0,a.length,10,10);
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+",");
}
}
}