排序算法Java泛型实现

本文实现的排序算法有：选择排序算法、插入排序算法、冒泡排序算法、希尔排序算法、归并排序算法、快速排序算法、大根堆排序算法。一共七种算法。

并将这些算法打包成一个Sort类，方便使用。

package sort;public class Sort{	//选择排序	public static <T extends Comparable<T>> void selectSort(T[] a){		for(int i=0 ; i<a.length ; i++){			int j=i;			for(int k=i+1 ; k<a.length ;k++){				if(a[k].compareTo(a[j])<0){					j=k;				}			}			if(j!=i){				swap(a[i],a[j]);			}		}	}	//插入排序	public static <T extends Comparable<T>> void insertSort(T[] a){		for(int i=1 ; i<a.length ; i++){			T key = a[i];			int j;			for(j=i-1 ; j>=0 ;j--){				if(a[j].compareTo(key)>0){					a[j+1] = a[j];				}else{					break;				}			}			a[j+1] = key;		}	}	//冒泡排序	public static <T extends Comparable<T>> void bubbleSort(T[] a){		for(int i=0 ; i<a.length-1 ;i++){			for(int j=0 ; j<a.length-i-1 ; j++){				if(a[j].compareTo(a[j+1])>0){					swap(a[j],a[j+1]);				}			}		}	}	//希尔排序	public static <T extends Comparable<T>> void shellSort(T[] a){		for(int increment = a.length/2 ; increment>0 ; increment /=2){			for(int i=0 ; i<increment ; i++){				//对每一组分别用插入排序排序				for(int j=i+increment; j<a.length ; j += increment){					T key = a[j];					int k; 					for(k=j-increment ; k>=i ;k -=increment){						if(a[k].compareTo(key)>0){							a[k+increment] = a[k]; 						}else{							break;						}					}					a[k+increment] = key; 				}			}		}		}	//归并排序	public static <T extends Comparable<T>> void mergeSort(T[] a){		mergesort(a,0,a.length-1);	}	//归并算法合并操作	PRivate static <T extends Comparable<T>> void mergearray(T a[], int first, int mid, int last)  	{  	    int i = first, j = mid + 1;  	    int m = mid,   n = last;  	    int k = 0;  	    @SuppressWarnings("unchecked")		T[] temp = (T[]) new Comparable[last-first+1];	    while (i <= m && j <= n)  	    {  	        if (a[i].compareTo(a[j])<0)  	            temp[k++] = a[i++];  	        else  	            temp[k++] = a[j++];  	    }  	      	    while (i <= m){	    	temp[k++] = a[i++];	    } 	          	      	    while (j <= n) {	    	temp[k++] = a[j++];	    } 	          	      	    for (i = 0; i < k; i++){	    	a[first + i] = temp[i];	    } 	          	}	private static <T extends Comparable<T>> void mergesort(T a[], int first, int last)  	{  	    if (first < last)  	    {  	        int mid = (first + last) / 2;  	        mergesort(a, first, mid);    //左边有序  	        mergesort(a, mid + 1, last); //右边有序  	        mergearray(a, first, mid, last); //再将二个有序数列合并  	    }  	}  	//快速排序	public static <T extends Comparable<T>> void quickSort(T[] a){		quicksort(a,0,a.length-1);	}		private static <T extends Comparable<T>> void quicksort(T[] a, int first, int last) {		if(first >= last){			return;		}		T key = a[first];		int left,index,right = last;		left = index=first;		while(index < right){			if(index == left){				if(a[right].compareTo(key)<0){					swap(a[left++],a[right]);					key = a[right];					index = right;				}else{					right--;				}			}			if(index == right){				if(a[left].compareTo(key)>0){					swap(a[left],a[right--]);					key = a[left];					index = left;				}else{					left++;				}			}		}		quicksort(a,first,index-1);		quicksort(a,index+1,last);	}	//堆排序	public static <T extends Comparable<T>> void heapSort(T[] a){		for(int i=0 ; i<a.length-1 ; i++){			createHead(a,a.length-i);			swap(a[0],a[a.length-1-i]);		}		}	//创建大根堆	private static <T extends Comparable<T>> void createHead(T[] a, int lastIndex) {		for(int i = (lastIndex-1)/2 ; i>=1 ; i--){			 // 保存当前正在判断的节点              int k = i;              // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点              int biggerIndex = 2 * k;              if (2 * k + 1 <= lastIndex) {                  // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex                  if (a[biggerIndex-1].compareTo(a[biggerIndex])<0) {                      // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值                      biggerIndex++;                  }              }             if(a[k-1].compareTo(a[biggerIndex-1])<0){            	swap(a[k-1],a[biggerIndex-1]);            }  		}		}	//实现交换	private static <T extends Comparable<T>> void swap(T a, T b) {		T temp;		temp =a;		a=b;		b=temp;	}	}
使用范例：
package sort;public class Test {	public static void main(String[] args) {		Integer a[] = {9,8,7,6,5,4,3,2,1,0};		Double d[] = {9.44,4.534,5.666,8.888,1.111};		String[] str = {"zzz","aaa","ttt","mmm","kkj","opq"};				Sort.selectSort(a);		Sort.selectSort(d);		Sort.selectSort(str);				for(int i=0 ; i<a.length ; i++){			System.out.print(a[i]+"/t");		}		System.out.println();		for(int i=0 ; i<d.length ; i++){			System.out.print(d[i]+"/t");		}		System.out.println();		for(int i=0 ; i<str.length ; i++){			System.out.print(str[i]+"/t");		}					}}	输出结果：
0	1	2	3	4	5	6	7	8	9	1.111	4.534	5.666	8.888	9.44	aaa	kkj	mmm	opq	ttt	zzz