常用排序算法的java实现

public class Sort{ /** *直接插入排序 */ public static <T extends Comparable<? super T>> void insertSort(T[] a) { int j; for (int i = 1; i < a.length; i++) { T tmp=a[i]; for (j = i; j>0&&tmp.compareTo(a[j-1])<0; j--) { a[j]=a[j-1]; } a[j]=tmp; } } /** *希尔排序 */ public static <T extends Comparable<? super T>> void shellSort(T[] a) { int j; for (int gap = a.length/2; gap>0; gap/=2) { for (int i = gap; i < a.length; i++) { T tmp=a[i]; for (j = i; j>=gap&&tmp.compareTo(a[j-gap])<0; j-=gap) { a[j]=a[j-gap]; } a[j]=tmp; } } } /** *冒泡排序 */ public static <T extends Comparable<? super T>> void bubbleSort(T[] a) { for (int i = 0; i < a.length; i++) { for (int j = a.length-1; j>i; j--) { if (a[j].compareTo(a[j-1])<0) { T tmp=a[j]; a[j]=a[j-1]; a[j-1]=tmp; } } } } private static <T extends Comparable<? super T>> void swapReferences(T[] a,int left,int right) { T tmp=a[left]; a[left]=a[right]; a[right]=tmp; } private static <T extends Comparable<? super T>> int getMiddle(T[] a,int left,int right) { T tmp=a[left]; while (left<right) { while (left<right&&a[right].compareTo(tmp)>=0) { right--; } a[left]=a[right]; while (left<right&&a[left].compareTo(tmp)<=0) { left++; } a[right]=a[left]; a[left]=tmp; } return left; } private static <T extends Comparable<? super T>> void qSort(T[] a,int left,int right) { if (left<right) { int middle=getMiddle(a,left,right); qSort(a, left, middle-1); qSort(a, middle+1,right); } } /** *快速排序 */ public static <T extends Comparable<? super T>> void quickSort(T[] a) { if (a.length>0) { qSort(a, 0, a.length-1); } } /** *选择排序 */ public static <T extends Comparable<? super T>> void selectSort(T[] a) { T min; for (int i = 0; i < a.length-1; i++) { min=a[i]; for (int j = i+1; j < a.length; j++) { if (a[j].compareTo(min)<0) { min=a[j]; swapReferences(a, i, j); } } } } private static int leftChild(int i) { return 2*i+1; } public static <T extends Comparable<? super T>> void percolateDownSort(T[] a,int i,int n) { int child; T tmp; for (tmp=a[i];leftChild(i)<n;i=child) { child=leftChild(i); if (child<n-1&&a[child].compareTo(a[child+1])<0) { child++; } if (tmp.compareTo(a[child])<0) { a[i]=a[child]; }else { break; } } a[i]=tmp; } /** *堆排序 */ public static <T extends Comparable<? super T>> void heapSort(T[] a) { for (int i = a.length/2-1; i >=0; i--) { percolateDownSort(a, i, a.length); } for (int i = a.length-1; i >0; i--) { swapReferences(a, 0, i); percolateDownSort(a, 0, i); } } private static <T extends Comparable<? super T>> void merge(T[] a,T[] tmp,int leftPos,int rightPos,int rightEnd) { int leftEnd=rightPos-1; int tmpPos=leftPos; int numEles=rightEnd-leftPos+1; while (leftPos<=leftEnd&&rightPos<=rightEnd) { if (a[leftPos].compareTo(a[rightPos])<=0) { tmp[tmpPos++]=a[leftPos++]; }else { tmp[tmpPos++]=a[rightPos++]; } } while (leftPos<=leftEnd) { tmp[tmpPos++]=a[leftPos++]; } while (rightPos<=rightEnd) { tmp[tmpPos++]=a[rightPos++]; } for (int i = 0; i < numEles; i++,rightEnd--) { a[rightEnd]=tmp[rightEnd]; } } private static <T extends Comparable<? super T>> void mergeSort(T[] a,T[] tmp,int left,int right) { if (left<right) { int center=(left+right)/2; mergeSort(a, tmp, left, center); mergeSort(a, tmp,center+1, right); merge(a, tmp, left, center+1, right); } } /** *归并排序 */ @SuppressWarnings("unchecked") public static <T extends Comparable<? super T>> void mergeSort(T[] a) { T[] tmp=(T[]) new Comparable[a.length]; mergeSort(a, tmp,0, a.length-1); } }