(选择，冒泡，插入，归并，希尔，快速)排序算法java预览

刚捣鼓了一下数据结构和算法 把总结写下，本内容和 my csdn一样http://blog.csdn.net/maomaolingyu

package source.datastruct_algorithm;

import java.util.Random;

public class SortUtil {
??? static int size =10000;
??? static VirtualObj[] persion ;
??? static long[] arr ;
??? @SuppressWarnings("unchecked")
??? static synchronized void init(){
??? ??? persion = new VirtualObj[size];
??? ??? arr = new long[size];
??? ??? int[] ran_arr = randomInt();
??? ??? for(int i=0;i<size;i++){
??? ??? ??? persion[i] = new VirtualObj("tom"+ran_arr[i],ran_arr[i],ran_arr[i]);
??? ??? }
??? ??? for(int i =0;i<size;i++){
??? ??? ??? arr[i] = ran_arr[i];
??? ??? }
??? ??? Proxy.serviceProxy().initLongArr(arr);
??? ??? Proxy.serviceProxy().initObjArr(persion);
??? }
??? private static int[] randomInt(){
??? ??? Random ran = new Random();
??? ??? ?boolean[] bool = new boolean[size];
??? ??? ?int rs[] = new int[size];
??? ??? int temp,j=0;
??? ??? for(int i=0;i<size;i++){
??? ??? ??? do{
??? ??? ??? ??? temp = ran.nextInt(size);
??? ??? ??? }while(bool[temp]);
??? ??? ??? bool[temp] =true;
??? ??? ??? rs[j++]=temp;
??? ??? }
??? ??? return rs;
??? }
??? public void setBaseArray(long[] array){
??? ??? arr= array;
??? ??? size= array.length;
??? }
???
??? public void setObjArray(Object[] arr){
??? ??? persion = (VirtualObj[])arr;
??? ??? size= persion.length;
??? }
??? public static void bubbleSort(){
??? ??? Proxy.serviceProxy().baseBubbleSort();
??? ??? Proxy.serviceProxy().objBubbleSort();
??? }
??? public static void selectSort(){
??? ??? Proxy.serviceProxy().baseSelectSort();
??? ??? Proxy.serviceProxy().objSelectSort();
??? }???
??? public static void insertSort(){
??? ??? Proxy.serviceProxy().baseInsertSort();
??? ??? Proxy.serviceProxy().objInsertSort();
??? }
??? public static void mergeSort(){
??? ??? Proxy.serviceProxy().baseUnionSort();
??? ??? Proxy.serviceProxy().objUnionSort();???
??? }???
??? public static void shellSort(){
??? ??? Proxy.serviceProxy().baseShellSort();
??? ??? Proxy.serviceProxy().objShellSort();
??? }???
??? public static void quickSort(){
??? ??? Proxy.serviceProxy().baseQuickSort();
??? ??? Proxy.serviceProxy().objQuickSort();
??? }
??? public static void main(String[] args) {
??? ??? init();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? bubbleSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("bubble sort ..............................");
??? ??? init();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? selectSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("select sort ..............................");
??? ??? System.out.println(System.currentTimeMillis());
??? ??? init();
??? ??? insertSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("insert sort ..............................");
??? ??? init();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? mergeSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("merge sort ..............................");
??? ??? init();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? shellSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("shell sort ..............................");
??? ??? init();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? quickSort();
??? ??? System.out.println(System.currentTimeMillis());
??? ??? System.out.println("quick sort ..............................");
??? }

}

class Proxy{
??? @SuppressWarnings("rawtypes")
??? private static SortService service = new SortService();
??? @SuppressWarnings("rawtypes")
??? public static SortService serviceProxy(){
??? ??? return service;
??? }
}


class SortService<T extends VirtualObj>{
??? private long[] longArr;
??? private T[] objArr;
??? private int size;
??? public void initLongArr(long[] arr){
??? ??? longArr = arr;
??? ??? size = arr.length;
??? }
??? public void initObjArr(T[] arr){
??? ??? objArr = arr;
??? ??? size = arr.length;
??? }
???
??? public void baseQuickSort(){
??? ??? baseRecQuicSort(0, size-1);
??? ??? displayLongArr();
??? }
??? //基本类型的快速排序
??? private void baseRecQuicSort(int left,int right){
??? ??? if(right - left +1 <=10){
??? ??? ??? baseInsertSort(left,right);
??? ??? }else{
??? ??? ??? long povit = baseGetPivot(left, right);
??? ??? ??? //long povit = longArr[right];
??? ??? ??? int compareIndex = basePartition(left,right,povit);
??? ??? ??? baseRecQuicSort(left,compareIndex);
??? ??? ??? baseRecQuicSort(compareIndex+1, right);
??? ??? }
??? }
??? //快速排序时的插入排序
??? private void baseInsertSort(int left,int right){
??? ??? int j=0;
??? ??? for(int i=left+1;i<=right;i++){
??? ??? ??? long temp = longArr[i];
??? ??? ??? for(j =i;j>left&&longArr[j-1]>temp;j--){
??? ??? ??? ??? longArr[j]=longArr[j-1];
??? ??? ??? }
??? ??? ??? longArr[j] = temp;
??? ??? }
??? ???
??? }
??? //3项取中，防止数据不随机
??? private long baseGetPivot(int left,int right){
??? ??? int center = (left + right)/2;
??? ??? if(longArr[left] <= longArr[center]){
??? ??? ??? swap(left, center);
??? ??? }
??? ??? if(longArr[left]<= longArr[right]){
??? ??? ??? swap(left, right);
??? ??? }
??? ???? if(longArr[center] > longArr[right]){
??? ???? ??? swap(center, right);
??? ???? }
??? ???
??? ??? return longArr[right];
??? }
??? //快速排序
??? private int basePartition(int left,int right,long povit){
??? ??? int leftindex = left;
??? ??? int rightindex = right-1;
??? ??? while(true){
??? ??? ??? while(longArr[++leftindex] < povit);
??? ??? ??? while((--rightindex)>0&&longArr[rightindex] > povit);
??? ??? ??? if(leftindex >= rightindex)break;
??? ??? ??? else{
??? ??? ??? ??? swap(leftindex, rightindex);
??? ??? ??? }
??? ??? }swap(leftindex, right -1);
??? ??? return leftindex;
??? }
??? //交换
??? private void swap(int indexFrom,int indexTo){
??? ??? long temp = longArr[indexFrom];
??? ??? longArr[indexFrom] = longArr[indexTo];
??? ??? longArr[indexTo] = temp;
??? }
??? //对象类型快速排序
??? public void objQuickSort(){
??? ??? objRecQuickSort(0,size-1);
??? ??? displayObjArr();
??? }
??? //对象类型快速排序
??? private void objRecQuickSort(int left,int right){
??? ??? if(right - left <10){
??? ??? ??? objInsertSort(left,right);
??? ??? }
??? ??? else{
??? ??? ??? T compareObj = objGetPovit(left,right);
??? ??? ??? //T compareObj = objArr[right];
??? ??? ??? int compareIndex = objPartion(left,right,compareObj);
??? ??? ??? objRecQuickSort(left, compareIndex);
??? ??? ??? objRecQuickSort(compareIndex+1, right);
??? ??? }
??? }
??? //对象快速排序
??? private int objPartion(int left,int right,T povit){
??? ??? int leftindex = left;
??? ??? int rightindex = right-1;
??? ??? while(true){
??? ??? ??? while(objArr[++leftindex].getStr().compareTo(povit.getStr())<0);
??? ??? ??? while(objArr[--rightindex].getStr().compareTo(povit.getStr())>0);
??? ??? ??? if(leftindex >= rightindex)break;
??? ??? ??? else{
??? ??? ??? ??? swapObj(leftindex, rightindex);
??? ??? ??? }
??? ??? }swapObj(leftindex, right-1);
??? ??? return leftindex;
??? }
??? //对象插入排序
??? private void objInsertSort(int left,int right){
??? ??? int i=0;
??? ??? for(int j =left+1;j<size;j++){
??? ??? ??? T temp = objArr[j];
??? ??? ??? for(i=j;i>left&&objArr[i-1].getStr().compareTo(temp.getStr())>0;i--){
??? ??? ??? ??? objArr[i] = objArr[i-1];
??? ??? ??? }
??? ??? ??? objArr[i] = temp;
??? ??? }
??? }
??? //3项取中 针对数组不大小不随机
??? private T objGetPovit(int left,int right){
??? ??? int center = (right + left)/2;
??? ??? T t_left = objArr[left];
??? ??? T t_center = objArr[center];
??? ??? T t_right = objArr[right];
??? ??? if(t_left.getStr().compareTo(t_center.getStr()) >0){
??? ??? ??? swapObj(left,center);
??? ??? }
??? ??? if(t_center.getStr().compareTo(t_right.getStr()) <0){
??? ??? ??? swapObj(center, right);
??? ??? }
??? ??? if(t_left.getStr().compareTo(t_right.getStr()) >0){
??? ??? ??? swapObj(left, right);
??? ??? }???
??? ??? return objArr[right];
??? }
??? //对象交换
??? private void swapObj(int from,int to){
??? ??? T temp = objArr[from];
??? ??? objArr[from] = objArr[to];
??? ??? objArr[to] = temp;
??? }
???
??? //基本类型希尔排序? 增量-3
??? public void baseShellSort(){
??? ??? int h=1;
??? ??? int in,out;
??? ??? while(h<size/3){
??? ??? ??? h=h*3+1;
??? ??? }
??? ???
??? ??? while(h>0){
??? ??? ??? for(out = h;out<size;out++){
??? ??? ??? ??? long temp = longArr[out];
??? ??? ??? ??? for(in=out;in > h-1&&longArr[in-h] >= temp;in-=h){
??? ??? ??? ??? ??? longArr[in] = longArr[in-h];
??? ??? ??? ??? }
??? ??? ??? ??? longArr[in] = temp;
??? ??? ??? }
??? ??? ??? h=(h-1)/3;
??? ??? }
??? ??? displayLongArr();
??? }
??? //对象类型希尔排序? 增量-3
??? public void objShellSort(){
??? ??? int h=1;
??? ??? int in,out;
??? ??? while(h<size/3){
??? ??? ??? h=h*3+1;
??? ??? }
??? ???
??? ??? while(h>0){
??? ??? ??? for(out = h;out<size;out++){
??? ??? ??? ??? T temp = objArr[out];
??? ??? ??? ??? for(in=out;in > h-1&&objArr[in-h].getStr().compareTo(temp.getStr())>0;in-=h){
??? ??? ??? ??? ??? objArr[in] = objArr[in-h];
??? ??? ??? ??? }
??? ??? ??? ??? objArr[in] = temp;
??? ??? ??? }
??? ??? ??? h=(h-1)/3;
??? ??? }
??? ??? displayObjArr();
??? }
???
??? //基本类型归并排序
??? public void baseUnionSort(){
??? ??? long[] workspace = new long[size];
??? ??? baseMergeSort(workspace,0, workspace.length-1);
??? ??? displayLongArr();
??? }

??? //归并算法
??? private void baseMergeSort(long[] arr,int lower,int upper){
??? ??? if(lower == upper)return;
??? ??? int mid = (upper+lower)/2;
??? ??? baseMergeSort(arr,lower,mid);
??? ??? baseMergeSort(arr,mid+1,upper);
??? ??? baseMerge(arr,lower,mid+1,upper);
??? }
??? //归并排序算法
??? private void baseMerge(long[] arr,int lower,int mid,int upper){
??? ??? int i=0,middle = mid-1;
??? ??? int low = lower;
??? ??? int size = (upper - lower)+1;
??? ??? while(lower <=middle&&mid<=upper){
??? ??? ??? if(longArr[lower] < longArr[mid]){
??? ??? ??? ??? arr[i++] = longArr[lower++];
??? ??? ??? }
??? ??? ??? else{
??? ??? ??? ??? arr[i++] = longArr[mid++];
??? ??? ??? }
??? ??? }
??? ??? while(lower<=middle){
??? ??? ??? arr[i++] = longArr[lower++];
??? ??? }
??? ??? while(mid<=upper){
??? ??? ??? arr[i++] = longArr[mid++];
??? ??? }
??? ??? for(int j=0;j<size;j++){
??? ??? ??? longArr[low+j] = arr[j];
??? ??? }
??? ???
??? }
???
??? //对象类型归并排序 ： 当有大量重复时，结果不准确
??? public void objUnionSort(){
??? ??? VirtualObj[] t = new VirtualObj[size];
??? ??? objMergeSort((T[])t,0,size-1);
??? ??? displayObjArr();
??? }
??? //归并算法
??? private void objMergeSort(T[] arr,int lower,int upper){
??? ??? if(lower == upper)return;
??? ??? int mid = (upper+lower)/2;
??? ??? objMergeSort(arr,lower,mid);
??? ??? objMergeSort(arr,mid+1,upper);
??? ??? objMerge(arr,lower,mid+1,upper);
??? }
??? //归并排序算法
??? public void objMerge(T[] arr,int lower,int mid,int upper){
??? ??? int low = lower;
??? ??? int i=0;
??? ??? int size = (upper - lower)/2;
??? ??? int middle = mid-1;
??? ??? while(lower <=middle&&mid<=upper){
??? ??? ??? if(objArr[lower].getStr().compareTo(objArr[mid].getStr())<0){
??? ??? ??? ??? arr[i++] = objArr[lower++];
??? ??? ??? }else{
??? ??? ??? ??? arr[i++] = objArr[mid++];
??? ??? ??? }
??? ??? }
??? ??? while(lower <= middle){
??? ??? ??? arr[i++] = objArr[lower++];
??? ??? }
??? ??? while(mid<=upper){
??? ??? ??? arr[i++] = objArr[mid++];
??? ??? }
??? ??? for(int j=0;j<size;j++){
??? ??? ??? objArr[low+j] = arr[j];
??? ??? }
??? }
???
??? //基本类型冒泡排序
??? public void baseBubbleSort(){
??? ??? for(int i =size-1; i>1;i--){
??? ??? ??? for(int j = 0 ; j < i ; j ++){
??? ??? ??? ??? if(longArr[j] > longArr[j+1]){
??? ??? ??? ??? ??? long temp;
??? ??? ??? ??? ??? temp = longArr[j];
??? ??? ??? ??? ??? longArr[j] = longArr[j+1];
??? ??? ??? ??? ??? longArr[j+1] = temp;
??? ??? ??? ??? }
??? ??? ??? }
??? ??? }
??? ??? displayLongArr();
??? }
??? //对象类型冒泡排序
??? public void objBubbleSort(){
??? ??? T temp;
??? ??? for(int i =size-1; i>1;i--){
??? ??? ??? for(int j = 0 ; j < i ; j ++){
??? ??? ??? ??? if(objArr[j].getStr().compareTo(objArr[j+1].getStr())>0){
??? ??? ??? ??? ??? temp = objArr[j];
??? ??? ??? ??? ??? objArr[j] = objArr[j+1];
??? ??? ??? ??? ??? objArr[j+1] = temp;
??? ??? ??? ??? }
??? ??? ??? }
??? ??? }
??? ??? displayObjArr();
??? }
???
??? //基本类型插入排序
??? public void baseInsertSort(){
??? ??? int j;
??? ??? for(int i=1;i<size;i++){
??? ??? ??? long temp = longArr[i];
??? ??? ??? for(j=i;j>i-1&& longArr[j-1]>temp;j--){??? ??? ??? ???
??? ??? ??? ??? longArr[j]=longArr[j-1];
??? ??? ??? }
??? ??? ??? longArr[j]=temp;
??? ??? }
??? ??? displayLongArr();
??? }
??? //对象类型插入排序
??? public void objInsertSort(){
??? ??? int j;
??? ??? for(int i=1;i<size;i++){
??? ??? ??? T temp = objArr[i];
??? ??? ??? for(j=i;j>i-1&& objArr[j-1].getStr().compareTo(temp.getStr())>0;j--){??? ??? ??? ???
??? ??? ??? ??? objArr[j]=objArr[j-1];
??? ??? ??? }
??? ??? ??? objArr[j]=temp;
??? ??? }
??? ??? displayObjArr();
??? }
??? //基本类型选择排序
??? public void baseSelectSort(){
??? ??? for(int i=0;i<size;i++){
??? ??? ??? for(int j=i;j<size;j++){
??? ??? ??? ??? if(longArr[i]>longArr[j]){
??? ??? ??? ??? ??? long temp;
??? ??? ??? ??? ??? temp = longArr[i];
??? ??? ??? ??? ??? longArr[i] = longArr[j];
??? ??? ??? ??? ??? longArr[j] = temp;
??? ??? ??? ??? }
??? ??? ??? }
??? ??? }
??? ??? displayLongArr();
??? }
??? //对象类型选择排序
??? public void objSelectSort(){
??? ??? T temp;
??? ??? for(int i=0;i<size;i++){
??? ??? ??? for(int j=i;j<size;j++){
??? ??? ??? ??? if(objArr[i].getStr().compareTo(objArr[j].getStr()) > 0){
??? ??? ??? ??? ??? temp = objArr[i];
??? ??? ??? ??? ??? objArr[i] = objArr[j];
??? ??? ??? ??? ??? objArr[j] = temp;
??? ??? ??? ??? }
??? ??? ??? }
??? ??? }
??? ??? displayObjArr();
??? }
??? public void displayLongArr(){
??? ???
??? ??? for(int i =0 ;i<size;i++){
??? ??? ??? System.out.print(longArr[i]+" ");
??? ??? }System.out.println();
??? }
??? public void displayObjArr(){
??? ??? for(int i =0 ;i<size;i++){
??? ??? ??? System.out.print(objArr[i].getStr()+" ");
??? ??? }System.out.println();
??? }

}

class VirtualObj{
??? public VirtualObj() {
??? ??? super();
??? }
??? public VirtualObj(String str, int age, float idCard) {
??? ??? super();
??? ??? this.str = str;
??? ??? this.age = age;
??? ??? this.idCard = idCard;
??? }
??? public String getStr() {
??? ??? return str;
??? }
??? public void setName(String str) {
??? ??? this.str = str;
??? }
??? public int getAge() {
??? ??? return age;
??? }
??? public void setAge(int age) {
??? ??? this.age = age;
??? }
??? public float getIdCard() {
??? ??? return idCard;
??? }
??? public void setIdCard(float idCard) {
??? ??? this.idCard = idCard;
??? }

??? private String str;
??? private int age;
??? private float idCard;
???
}

总结 ： 在次测试了数组在1000 和10000的情况 看出 冒泡，选择，插入这三个0(N平方)算法 冒泡最慢，插入稍微由于选择.不过大致相当

而归并和希尔表现出色 . 但是快速排序本以为很好的 表现不如前两者，但是有序前面简单派算法。 经过重复和不重复数据的测试，（只是在该环境下的效率大概如此）.推荐在数据较多重复情况下优先选择 希尔和归并排序.

希尔和归并 随数据增大效率提高可在10倍N

?