常见排序算法(二)

/** * 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; } private static int partition(int[] a,int low,int high){ int temp=a[low]; while(low<high){ while(low<high && a[high]>=temp) high--; int x=a[low];a[low]=a[high];a[high]=x; while(low<high && a[low]<=temp) low++; int y=a[low];a[low]=a[high];a[high]=y; } print(a,a.length,-1); return low; } /** * 快速排序. * 基本思想： * 1）选择一个基准元素,通常选择第一个元素或者最后一个元素, * 2）通过一趟排序讲待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。 * 3）此时基准元素在其排好序后的正确位置 * 4）然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。 * @param a * @param low * @param high */ public static void quickSort(int[] a,int low,int high){ if(low<high) { int x=partition(a, low, high); quickSort(a,low,x-1); quickSort(a,x+1,high); } } private static void merge(int[] a,int left,int middle,int right){ int[] b=new int[a.length]; int temp=left; int siginB=left; int mid = middle+1; //右边的起始位置 //从两个数组中选择小的加入辅助数组 while(left<=middle && mid<=right){ if(a[left]<a[mid]) b[siginB++]=a[left++]; else b[siginB++]=a[mid++]; } //当不对称时,将多的数组剩余的数据加入辅助数组 while(left<=middle) b[siginB++]=a[left++]; while(mid<=right) b[siginB++]=a[mid++]; //将辅助数组的数据取出 while(temp<=right){ a[temp]=b[temp++]; } print(a,a.length,-9); } /** * 归并排序. * 基本思想: * 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表， * 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。 * @param a * @param left * @param right */ public static void mergeSort(int[] a,int left,int right){ if(left<right){ int middle=(left+right)/2; mergeSort(a,left,middle); mergeSort(a,middle+1,right); merge(a,left,middle,right); } } public static void main(String[] args){ int[] a=new int[]{6,4,3,1,5,5,2}; int[] b=new int[]{6,4,3,1,5,5,2}; quickSort(a,0,a.length-1); mergeSort(b,0,b.length-1); } }