归并排序和快速排序

归并排序采用分治法实现，基本思想是：将待排序元素分成大小相等的两个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并。mergesort的递归过程只是将集合一分为二，直至待排序集合只剩下一个元素为止，然后不断合并2个排好序的数组断。

package com.rmt.mergesort; import java.util.Arrays; public class MergeSort { public static void mergesort(int [] a,int start,int end ) { int mid=(start+end)/2; if(start<end) { mergesort(a, start, mid); mergesort(a, mid+1, end); merge(a, start, mid,end); } } public static void merge(int [] a,int start,int mid ,int end) { int i=start,j=mid+1,k=0; int []newarr=new int[end-start+1];//申请一个新空间来保存排序后数组 while(i<=mid && j<=end) { if(a[i]<a[j]) { newarr[k]=a[i]; k++; i++; } else { newarr[k]=a[j]; j++; k++; } } while(i<=mid) { newarr[k]=a[i]; k++; i++; } while(j<=end) { newarr[k]=a[j]; k++; j++; } for(int m=0;m<newarr.length;m++) { a[m+start]=newarr[m]; } } public static void main(String[] args) { int [] a = {1,11,2,3,5,68,0,1}; System.out.println("未排序前数组："+Arrays.toString(a)); if(a.length>0) mergesort(a,0,a.length-1); System.out.println("排序后的数组："+Arrays.toString(a)); }

快排划定个基准元素，先开始从右边找比基准元素小的元素，再左边找比基准元素大的元素，并交换，2边碰头后将基准元素归位。接着把基准元素左边和右边子列做递归调用。

import java.util.Arrays; public class QuickSort { public static void quicksort(int []a,int start,int end ) { if(start>end) { return ; } int i=start; int j=end; int pivot= a[start]; while(i<j) { while(a[j]>pivot && i<j) { j--; } while(a[i]<=pivot && i<j) { i++; } if(i<j) { int temp=a[i]; a[i]=a[j]; a[j]=temp; } } int p=a[i]; a[i]=a[start]; a[start]=p; quicksort(a, start, i-1); quicksort(a, i+1, end); } public static void main(String[] args) { int [] a = {1,11,2,3,5,68,0,1}; System.out.println("未排序的数组："+Arrays.toString(a)); if(a.length > 0){ quicksort(a,0,a.length-1); }else{ System.out.println("空数组不能排序"); } System.out.println("排序后的数组："+Arrays.toString(a)); } }