ソートアルゴリズム復習(Java実装)
管理を容易にするために、まず基礎クラスを導入します.
挿入ソートこのアルゴリズムは、データ規模が小さいときに非常に効率的であり、K+1番目から前のK個の秩序配列の適切な位置に挿入されるたびに、Kが0からN−1まで挿入され、ソートが完了する.
バブルソートこれは最も簡単なソートアルゴリズムかもしれませんが、アルゴリズムの考え方は、配列の末端から隣接する2つの要素を比較するたびに、i番目の小さなバブルを配列のi番目の位置に置くことです.i 0からN−1まで並べ替えを完了する.(もちろん、配列の先頭から隣接する2つの要素を比較し、i番目の大きな泡を配列のN-i番目の位置に置くこともできます.iは0からN-1まで並べ替えが完了します.)
選択ソート選択ソートは、バブルに対して、逆シーケンスが発見されるたびに交換されるのではなく、グローバルiが小さいときに要素の位置をメモし、最後にi番目の要素と交換し、配列の最終的な秩序を保証します.
挿入ソートと比較して、選択ソートは毎回グローバルi番目に小さく、前のi要素は調整されません.
ShellソートShellソートは、挿入ソートの2つの特徴を十分に利用している挿入ソートの変種として理解できます.
1)データ規模が小さい場合、非常に効率的
2)与えられたデータが秩序化されている場合の時間的コストはO(N)である.
したがって、Shellソートは、データを小さなブロックに分割するたびに挿入ソートを使用し、その後、小さなブロックがソートされた場合に大きなブロックを合成し、挿入ソートを使用し続け、小さなブロックを結合し続け、最後にブロックになることを知り、挿入ソートを使用します.
ここで、各分割数の小さなブロックは「増分」によって制御され、開始時に増分が大きくなり、N/2に近づくことで、分割数がN/2に近い小さなブロックに近づき、徐々に「増分」が減少し、最終的には1に減少する.
常に良好な増分シーケンスは2^k−1,2^(k−1)−1,......7,3,1であり,これによりShell並べ替え時間の複雑さをO(N^1.5)に達させることができる.
だから私はShellソートを実現する際にこのインクリメンタルシーケンスを採用しました
クイックソートクイックソートは、現在最も広く使用されているソートアルゴリズムです.
一般的には、次の手順に従います.
1)ピボット要素を選択する(選択方法がよく、私の実現では中間要素を除去する簡単な方法を採用している)
2)このピボット要素を使用して配列を分割し、その要素より小さい要素がその左側にあり、それより大きいものが右側にあるようにします.ピボット要素を適切な位置に配置します.
3)ピボット要素の最後に決定された位置に基づいて,配列を3つの部分に分け,左,右,ピボット要素自身,左,右のそれぞれに対して高速ソートアルゴリズムを再帰的に呼び出せばよい.
高速ソートの核心は分割アルゴリズムにあり,最もテクニックのある部分ともいえる.
集計ソートアルゴリズムの考え方は,並べ替えられるシーケンスを2つの部分に分割するたびに,この2つの部分をそれぞれ再帰的に集計ソートし,完了後にこの2つのサブ部分を1つに統合することである.
シーケンス.
集計ソートは、集計を容易にするためにグローバル一時配列を用い、このアルゴリズムのコアは集計にある.
スタックソートスタックは完全な二叉木であり、一般的に配列を使用して実現される.
スタックには主に2つのコア操作があります.
1)指定されたノードから上方への調整(shiftUp)
2)指定ノードから下方調整(shiftDown)
ヒープの作成、およびヒープノードの削除にはshiftDwonが使用されますが、ノードを挿入するときは一般的に2つの操作を組み合わせて使用されます.
スタックソートは最大値スタックによって実現され、i回目にスタックトップから最大値を除去して配列の最後からi番目の位置に配置し、shiftDownから最後からi+1番目の位置に配置し、Nの調整を行い、ソートを完了する.
スタックソートも、i番目に大きい要素を選択するたびに選択的なソートであることは明らかである.
バケツソートバケツソートは、比較に基づいているわけではありません.基数ソートと同じ割当クラスのソートに属します.このソートの特徴は、事前にソートされるシーケンスのいくつかの特徴を知っておくことです.
バケツソートは、並べ替えられるシーケンスが1つの範囲内であり、この範囲は大きくないことを事前に知っておく必要があります.
例えば、配列待ちシーケンスが[0,M)内であることが分かると、M個のバケツが割り当てられ、I番目のバケツはIの出現状況を記録し、最後に各バケツが受信した位置情報に基づいてデータを秩序ある形式に出力することができる.
ここでは,位置情報を記録するための2つの一時配列と,データの出力を容易にするための秩序化方式を用い,また,データが0からMAXに落ちると仮定し,与えられたデータが0からでなければ,各数から最小の数を減算することができる.
基数ソート基数ソートは、拡張されたバケツソートと言える.例えば、0から999999のようなソート対象が広い範囲にある場合、バケツソートはスペースの無駄である.基数ソートは、各ソートコードをd個のソートコード、例えば6桁未満(6桁前補0未満)に分解する6つのソートコードに分解して、それぞれビット、10ビット、100ビットです...
ソートは、6回に分けて完了し、毎回i番目のソートコードで並べます.
一般的には2つの方法があります.
1)上位優先(MSD):上位から下位へ順にシーケンスを並べ替える
2)下位優先(LSD):下位から上位へ順にシーケンスを並べ替える
コンピュータは一般的に低位優先法(人間は一般的に高位優先を用いる)を採用するが,低位優先を採用する場合はソートアルゴリズムの安定性を確保しなければならない.
基数ソートはバケツソートにより、N番目のビットでソートされるたびにバケツソートされます.同じバケツに落ちるデータをどのように配置するかには、次の2つの方法があります.
1)逐次格納:バケツ式ソートを使用するたびに、r個のバケツに入れ、同時にカウントを増やす.
2)チェーンストレージ:各バケツは静的キューによって追跡される.
package algorithms;
public abstract class Sorter<E extends Comparable<E>> {
public abstract void sort(E[] array,int from ,int len);
public final void sort(E[] array)
{
sort(array,0,array.length);
}
protected final void swap(E[] array,int from ,int to)
{
E tmp=array[from];
array[from]=array[to];
array[to]=tmp;
}
}挿入ソートこのアルゴリズムは、データ規模が小さいときに非常に効率的であり、K+1番目から前のK個の秩序配列の適切な位置に挿入されるたびに、Kが0からN−1まで挿入され、ソートが完了する.
package algorithms;
public class InsertSorter<E extends Comparable<E>> extends Sorter<E> {
/* (non-Javadoc)
* @see algorithms.Sorter#sort(E[], int, int)
*/
public void sort(E[] array, int from, int len) {
E tmp=null;
for(int i=from+1;i<from+len;i++)
{
tmp=array[i];
int j=i;
for(;j>from;j--)
{
if(tmp.compareTo(array[j-1])<0)
{
array[j]=array[j-1];
}
else break;
}
array[j]=tmp;
}
}
}バブルソートこれは最も簡単なソートアルゴリズムかもしれませんが、アルゴリズムの考え方は、配列の末端から隣接する2つの要素を比較するたびに、i番目の小さなバブルを配列のi番目の位置に置くことです.i 0からN−1まで並べ替えを完了する.(もちろん、配列の先頭から隣接する2つの要素を比較し、i番目の大きな泡を配列のN-i番目の位置に置くこともできます.iは0からN-1まで並べ替えが完了します.)
package algorithms;
public class BubbleSorter<E extends Comparable<E>> extends Sorter<E> {
private static boolean DWON=true;
public final void bubble_down(E[] array, int from, int len)
{
for(int i=from;i<from+len;i++)
{
for(int j=from+len-1;j>i;j--)
{
if(array[j].compareTo(array[j-1])<0)
{
swap(array,j-1,j);
}
}
}
}
public final void bubble_up(E[] array, int from, int len)
{
for(int i=from+len-1;i>=from;i--)
{
for(int j=from;j<i;j++)
{
if(array[j].compareTo(array[j+1])>0)
{
swap(array,j,j+1);
}
}
}
}
@Override
public void sort(E[] array, int from, int len) {
if(DWON)
{
bubble_down(array,from,len);
}
else
{
bubble_up(array,from,len);
}
}
}選択ソート選択ソートは、バブルに対して、逆シーケンスが発見されるたびに交換されるのではなく、グローバルiが小さいときに要素の位置をメモし、最後にi番目の要素と交換し、配列の最終的な秩序を保証します.
挿入ソートと比較して、選択ソートは毎回グローバルi番目に小さく、前のi要素は調整されません.
package algorithms;
public class SelectSorter<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) {
for(int i=0;i<len;i++)
{
int smallest=i;
int j=i+from;
for(;j<from+len;j++)
{
if(array[j].compareTo(array[smallest])<0)
{
smallest=j;
}
}
swap(array,i,smallest);
}
}
}
ShellソートShellソートは、挿入ソートの2つの特徴を十分に利用している挿入ソートの変種として理解できます.
1)データ規模が小さい場合、非常に効率的
2)与えられたデータが秩序化されている場合の時間的コストはO(N)である.
したがって、Shellソートは、データを小さなブロックに分割するたびに挿入ソートを使用し、その後、小さなブロックがソートされた場合に大きなブロックを合成し、挿入ソートを使用し続け、小さなブロックを結合し続け、最後にブロックになることを知り、挿入ソートを使用します.
ここで、各分割数の小さなブロックは「増分」によって制御され、開始時に増分が大きくなり、N/2に近づくことで、分割数がN/2に近い小さなブロックに近づき、徐々に「増分」が減少し、最終的には1に減少する.
常に良好な増分シーケンスは2^k−1,2^(k−1)−1,......7,3,1であり,これによりShell並べ替え時間の複雑さをO(N^1.5)に達させることができる.
だから私はShellソートを実現する際にこのインクリメンタルシーケンスを採用しました
package algorithms;
public class ShellSorter<E extends Comparable<E>> extends Sorter<E> {
/* (non-Javadoc)
* Our delta value choose 2^k-1,2^(k-1)-1,.7,3,1.
* complexity is O(n^1.5)
* @see algorithms.Sorter#sort(E[], int, int)
*/
@Override
public void sort(E[] array, int from, int len) {
//1.calculate the first delta value;
int value=1;
while((value+1)*2<len)
{
value=(value+1)*2-1;
}
for(int delta=value;delta>=1;delta=(delta+1)/2-1)
{
for(int i=0;i<delta;i++)
{
modify_insert_sort(array,from+i,len-i,delta);
}
}
}
private final void modify_insert_sort(E[] array, int from, int len,int delta) {
if(len<=1)return;
E tmp=null;
for(int i=from+delta;i<from+len;i+=delta)
{
tmp=array[i];
int j=i;
for(;j>from;j-=delta)
{
if(tmp.compareTo(array[j-delta])<0)
{
array[j]=array[j-delta];
}
else break;
}
array[j]=tmp;
}
}
}クイックソートクイックソートは、現在最も広く使用されているソートアルゴリズムです.
一般的には、次の手順に従います.
1)ピボット要素を選択する(選択方法がよく、私の実現では中間要素を除去する簡単な方法を採用している)
2)このピボット要素を使用して配列を分割し、その要素より小さい要素がその左側にあり、それより大きいものが右側にあるようにします.ピボット要素を適切な位置に配置します.
3)ピボット要素の最後に決定された位置に基づいて,配列を3つの部分に分け,左,右,ピボット要素自身,左,右のそれぞれに対して高速ソートアルゴリズムを再帰的に呼び出せばよい.
高速ソートの核心は分割アルゴリズムにあり,最もテクニックのある部分ともいえる.
package algorithms;
public class QuickSorter<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) {
q_sort(array,from,from+len-1);
}
private final void q_sort(E[] array, int from, int to) {
if(to-from<1)return;
int pivot=selectPivot(array,from,to);
pivot=partion(array,from,to,pivot);
q_sort(array,from,pivot-1);
q_sort(array,pivot+1,to);
}
private int partion(E[] array, int from, int to, int pivot) {
E tmp=array[pivot];
array[pivot]=array[to];//now to's position is available
while(from!=to)
{
while(from<to&&array[from].compareTo(tmp)<=0)from++;
if(from<to)
{
array[to]=array[from];//now from's position is available
to--;
}
while(from<to&&array[to].compareTo(tmp)>=0)to--;
if(from<to)
{
array[from]=array[to];//now to's position is available now
from++;
}
}
array[from]=tmp;
return from;
}
private int selectPivot(E[] array, int from, int to) {
return (from+to)/2;
}
}集計ソートアルゴリズムの考え方は,並べ替えられるシーケンスを2つの部分に分割するたびに,この2つの部分をそれぞれ再帰的に集計ソートし,完了後にこの2つのサブ部分を1つに統合することである.
シーケンス.
集計ソートは、集計を容易にするためにグローバル一時配列を用い、このアルゴリズムのコアは集計にある.
package algorithms;
import java.lang.reflect.Array;
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++;
}
}
}スタックソートスタックは完全な二叉木であり、一般的に配列を使用して実現される.
スタックには主に2つのコア操作があります.
1)指定されたノードから上方への調整(shiftUp)
2)指定ノードから下方調整(shiftDown)
ヒープの作成、およびヒープノードの削除にはshiftDwonが使用されますが、ノードを挿入するときは一般的に2つの操作を組み合わせて使用されます.
スタックソートは最大値スタックによって実現され、i回目にスタックトップから最大値を除去して配列の最後からi番目の位置に配置し、shiftDownから最後からi+1番目の位置に配置し、Nの調整を行い、ソートを完了する.
スタックソートも、i番目に大きい要素を選択するたびに選択的なソートであることは明らかである.
package algorithms;
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;
}
}バケツソートバケツソートは、比較に基づいているわけではありません.基数ソートと同じ割当クラスのソートに属します.このソートの特徴は、事前にソートされるシーケンスのいくつかの特徴を知っておくことです.
バケツソートは、並べ替えられるシーケンスが1つの範囲内であり、この範囲は大きくないことを事前に知っておく必要があります.
例えば、配列待ちシーケンスが[0,M)内であることが分かると、M個のバケツが割り当てられ、I番目のバケツはIの出現状況を記録し、最後に各バケツが受信した位置情報に基づいてデータを秩序ある形式に出力することができる.
ここでは,位置情報を記録するための2つの一時配列と,データの出力を容易にするための秩序化方式を用い,また,データが0からMAXに落ちると仮定し,与えられたデータが0からでなければ,各数から最小の数を減算することができる.
package algorithms;
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]+",");
}
}
}基数ソート基数ソートは、拡張されたバケツソートと言える.例えば、0から999999のようなソート対象が広い範囲にある場合、バケツソートはスペースの無駄である.基数ソートは、各ソートコードをd個のソートコード、例えば6桁未満(6桁前補0未満)に分解する6つのソートコードに分解して、それぞれビット、10ビット、100ビットです...
ソートは、6回に分けて完了し、毎回i番目のソートコードで並べます.
一般的には2つの方法があります.
1)上位優先(MSD):上位から下位へ順にシーケンスを並べ替える
2)下位優先(LSD):下位から上位へ順にシーケンスを並べ替える
コンピュータは一般的に低位優先法(人間は一般的に高位優先を用いる)を採用するが,低位優先を採用する場合はソートアルゴリズムの安定性を確保しなければならない.
基数ソートはバケツソートにより、N番目のビットでソートされるたびにバケツソートされます.同じバケツに落ちるデータをどのように配置するかには、次の2つの方法があります.
1)逐次格納:バケツ式ソートを使用するたびに、r個のバケツに入れ、同時にカウントを増やす.
2)チェーンストレージ:各バケツは静的キューによって追跡される.
package algorithms;
import java.util.Arrays;
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]+",");
}
}
}