基本排序的实现与性能比较

    基本排序一般有：选择排序，插入排序，冒泡排序。

    //专门的sort排序类    public class Sort {	static boolean less(int a, int b){		return a
    
     l;j--){				comExch(array,j-1,j);			}		}	}	//选择排序,每次序最小的	static void selection(int array[],int l,int r){		for(int i=l;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
      
       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);		}	}    }
      
     
    

    它们之间的性能比较：在最坏情况和平均情况三者都是二次方时间复杂度。基本不用额外的存储控件。但还是有一个系数的差距。还要比较的是移动次数和比较次数。

    选择排序进行了约n*n/2次的比较，和n次交换。

    插入排序进行了n*n/4 次比较，n*n/4 次移动。

    冒泡排序进行n*n/2 次的比较和移动。

    根据实验研究（国外研究的结论）：对小文件的排序，插入排序和选择排序比冒泡排序快2倍。当比较的是String 或者是对象数组时，插入排序比其他两个方法快的多。如果交换次数开销很大的时候：选择排序是最好的，时间就不是第一位考虑了。