基本ソートの実装とパフォーマンスの比較

基本ソートの実装とパフォーマンスの比較
基本ソートには、一般的に、ソートの選択、ソートの挿入、バブルソートがあります.

    // sort 
    public class Sort {
	static boolean less(int a, int b){
		return a<b;
	}
	
	static void exch(int array[],int i,int j){
		int temp=array[i];
		array[i]=array[j];
		array[j]=temp;
	}
	
	static void comExch(int array[],int i,int j){
		if(less(array[j],array[i]))
			exch(array,i,j);
	}
	
	static void sort(int array[] ,int l,int r){
		example(array,l,r);
	}
	
	static void example(int array[],int l,int r){
		for(int i=l+1;i<r;i++){
			for(int j=i;j>l;j--){
				comExch(array,j-1,j);
			}
		}
	}
	// , 
	static void selection(int array[],int l,int r){
		for(int i=l;i<r;i++){
			int min=i;
			for(int j=i+1;j<r;j++){
				if(less(array[j],array[min])){
					min=j;
				}
			}
			exch(array,i,min);
		}
	}
	// 
	static void insertion(int array[],int l,int r){
		int i;
		for(i=r;i>l;i--)
		comExch(array, i-1, i);
		for(i=l+2;i<=r;i++){
		    int j=i;
		    int v=array[i];
		    while(less(v,array[j-1])){
			array[j]=array[j-1];
			j--;
		    }
		    array[j]=v;
		}
	}
	// 
	static void bubble(int array[],int l,int r){
		for(int i=l;i<r;i++){
		    for(int j=r;j>i;j--){
			comExch(array, j-1, j);
		    }
		}
	}
	public static void main(String args[]){
		int array[]={1,3,2,5,4,9,8,0};
		bubble(array,0,7);
		for(Integer n:array){
		System.out.println(n);
		}
	}
    }

それらの間の性能比較:最悪の場合と平均の場合の3つはいずれも二乗時間の複雑さである.追加のストレージコントロールはほとんど使用されません.しかし、係数の差があります.また比較するのは移動回数と比較回数です.
選択ソートは,n*n/2回程度の比較を行い,n回と交換した.
挿入ソートはn*n/4回比較し,n*n/4回移動した.
n*n/2回の比較と移動をバブルソートで行った.
実験研究(国外研究の結論):小ファイルのソートに対して、挿入ソートと選択ソートは泡ソートより2倍速い.Stringまたはオブジェクト配列を比較すると、挿入ソートは他の2つの方法よりも速くなります.交換回数がオーバーヘッドが大きい場合:ソートを選択するのが一番で、時間は第一に考えられません.