常见排序算法(一)

/** * Created by ztc on 16-5-13. */ public class sort { public static long print(int a[], int n ,int i){ long atime=System.nanoTime(); System.out.print("第"+i + "趟:"); for(int j= 0; j<n; j++){ System.out.print(a[j]+" "); } System.out.println(); long btime=System.nanoTime(); return btime-atime; } /** * 直接插入排序. * 基本思想: * 将一个记录插入到已排序好的有序表中， * 从而得到一个新，记录数增1的有序表。 * 即：先将序列的第1个记录看成是一个有序的子序列， * 然后从第2个记录逐个进行插入，直至整个序列有序为止。 * @param a 要排序的数组 * @param n 数组大小 */ public static void insertSort(int[] a,int n){ long atime=System.nanoTime(); long printTime=0; for(int i=1;i<n;i++){ for(int j=i-1;j>=0;j--){ if(a[j]>a[j+1]){ int b=a[j + 1];a[j+1] = a[j];a[j]=b; } } printTime+=print(a, n, i); } long btime=System.nanoTime(); System.out.println("直接插入运行时间:" + (btime - atime-printTime)+"ns"); } /** * 冒泡排序. * 基本思想： * 在要排序的一组数中，对当前还未排好序的范围内的全部数， * 自上而下对相邻的两个数依次进行比较和调整， * 让较大的数往下沉，较小的往上冒。 * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。 * @param a * @param n */ public static void bubbleSort(int[] a,int n){ long atime=System.nanoTime(); long printTime=0; for(int i=1;i<n;i++){ for(int j=0;j<n-i;j++){ if(a[j]>a[j+1]){ int b=a[j + 1];a[j+1] = a[j];a[j]=b; } } printTime+=print(a,n,i); } long btime=System.nanoTime(); System.out.println("冒泡排序运行时间:" + (btime - atime-printTime)+"ns"); } private static int getMin(int[] a,int n,int i){ int k=i; for(int x=i+1;x<n;x++){ if(a[x]<a[k]){ k=x; } } return k; } /** * 简单选择排序. * 基本思想： * 在要排序的一组数中， * 选出最小（或者最大）的一个数与第1个位置的数交换； * 然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换， * 依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。 * @param a * @param n */ public static void selectSort(int[] a,int n){ long atime=System.nanoTime(); long printTime=0; for(int i=0;i<n;i++){ int k=getMin(a,n,i); int e=a[i];a[i]=a[k];a[k]=e; printTime+=print(a,n,i); } long btime=System.nanoTime(); System.out.println("选择排序运行时间:" + (btime - atime-printTime)+"ns"); } public static void main(String[] args){ int[] a=new int[]{6,4,3,1,5,2}; int[] b=new int[]{6,4,3,1,5,2}; int[] c=new int[]{6,4,3,1,5,2}; insertSort(a,a.length); bubbleSort(b,b.length); selectSort(c,c.length); } }