归并排序
概述: 主要思想是将2个已经有序的数组归并为一个有序数组
1.自顶向下归并排序
/**
* 自顶向下归并排序(递归)
*/
public void merge(int[] arr,int lo,int hi){
if(lo>=hi)
return;
int mid = (lo+hi)/2;
merge(arr,lo,mid);
merge(arr,mid+1,hi);
inPlaceMerge(arr,lo,mid,hi);
} /**
* 归并操作(将2个有序数组归并为一个有序数组)
* @param arr 数组(包含2个有序数组)
* @param lo 第一个数组起始索引
* @param mid 第一个数组结束索引
* @param hi 第二个数组结束索引
*/
public static int[] aux; //辅助数组,最开始初始化与数组arr一致
public void inPlaceMerge(int[] arr,int lo,int mid,int hi){
//将[lo...hi]复制到数组aux中对应位置
for(int i=lo;i<=hi;++i)
aux[i] = arr[i];
//merge(归并)
int i = lo,j = mid+1; //记录2个有序数组起始索引
for(int k=lo;k<=hi;k++){ //每次确定arr[k]的值即可
if(i>mid) arr[k] = aux[j++];
else if(j>hi) arr[k] = aux[i++];
else if(aux[i]>aux[j]) arr[k] = aux[j++];
else arr[k] = aux[i++];
}
}- 测试
@Test public void testMerge() { //创建数组 int[] arr = Arrays.stream(SortTemplate.getArray(111)).mapToInt(x -> (int) x).toArray(); aux = arr.clone(); //辅助数组初始化,与arr相同 merge(arr, 0, arr.length - 1); //归并排序 System.out.println("\n" + SortTemplate.isSorted(arr)); //是否有序 }
- 优化
1.当数组规模小时,不使用归并,采用更高效方式进行排序(例插入排序)
2.对已经有序的数组进行判断,不需要再进行归并
3.每次归并操作不再往辅助数组复制,而是交替使用arr与aux作为辅助数组,从而减少复制次数
- 方案一: 递归中传入一个标志参数,从而实现每次交替使用arr与aux作为辅助数组
/**
* 归并排序优化
*/
public void merge(int[] arr,int[] aux,int lo,int hi,boolean flag){
int mid = (lo+hi)/2;
if(hi-lo<=15){ //优化1.数组规模小于15时使用插入排序
if(flag)
insertion(aux,lo,hi);
else
insertion(arr,lo,hi);
return;
}
merge(arr,aux,lo,mid,!flag);
merge(arr,aux,mid+1,hi,!flag);
/* if(arr[mid]<arr[mid+1]) { //优化2.已经有序,无需进行归并操作
return; //注意: 交替使用arr与aux作为辅助数组时,不能使用此方法
}*/ //因为每次必须进行归并,如果不归并操作可能会造成[lo...mid]在arr上,而[mid+1...hi]在aux上
if(flag) //优化3.交替使用arr与aux作为辅助数组(初始传入false时,最终排序结果会在arr上,true时在aux上)
inPlaceMerge(aux,arr,lo,mid,hi);
else
inPlaceMerge(arr,aux,lo,mid,hi);
} /**
* 归并操作
*/
public static int[] aux; //辅助数组,最开始初始化与数组arr一致
public void inPlaceMerge(int[] arr,int[] aux,int lo,int mid,int hi){
//arr为排序后结果数组,aux为归并辅助数组
//无需再将arr[lo...hi]复制到aux辅助数组上,减少了复制次数
int i = lo, j = mid+1;
for(int k=lo;k<=hi;++k){
if(i>mid) arr[k] = aux[j++];
else if(j>hi) arr[k] = aux[i++];
else if(aux[i] > aux[j]) arr[k] = aux[j++];
else arr[k] = aux[i++];
}
} /**
* 插入排序: 对数组arr [lo...hi]部分进行插入排序
*/
public void insertion(int[] arr,int lo,int hi){
for(int i=lo+1;i<=hi;++i)
for(int j=i;j>lo && arr[j]<arr[j-1];--j){
//交换
arr[j] = arr[j]^arr[j-1];
arr[j-1] = arr[j]^arr[j-1];
arr[j] = arr[j]^arr[j-1];
}
}- 测试
@Test
public void testMerge() {
//创建数组
int[] arr = Arrays.stream(SortTemplate.getArray(111)).mapToInt(x -> (int) x).toArray();
aux = arr.clone(); //辅助数组初始化,与arr相同
merge(arr,aux,0,arr.length-1,false); //优化后的归并排序
System.out.println("\n" + SortTemplate.isSorted(arr)); //是否有序
}
- 方案二:使用全局变量作为标志,实现交替使用arr与aux作为辅助数组
/**
* 归并排序优化
*/
public static boolean flag = true; //静态变量,根据静态变量值确定辅助数组
public void merge(int[] arr,int[] aux,int lo,int hi){
if(lo>=hi) return;
int mid = (lo+hi)/2;
flag = !flag;
if(hi-lo<=15){ //数组规模小于15时使用插入排序
if(flag)
insertion(aux,lo,hi); //插入排序
else
insertion(arr,lo,hi);
flag = !flag;
return;
}
merge(arr,aux,lo,mid);
merge(arr,aux,mid+1,hi);
/* if(arr[mid]<arr[mid+1]) { //已经有序,无需进行归并操作(交替使用arr与aux作为辅助数组时无法使用方式)
return;
}*/
if(flag)
inPlaceMerge(aux,arr,lo,mid,hi);
else
inPlaceMerge(arr,aux,lo,mid,hi);
flag = !flag;
} /**
* 归并操作
*/
public static int[] aux; //辅助数组,最开始初始化与数组arr一致
public void inPlaceMerge(int[] arr,int[] aux,int lo,int mid,int hi){
//arr为排序后结果数组,aux为归并辅助数组
//无需再将arr[lo...hi]复制到aux辅助数组上,减少了复制次数
int i = lo, j = mid+1;
for(int k=lo;k<=hi;++k){
if(i>mid) arr[k] = aux[j++];
else if(j>hi) arr[k] = aux[i++];
else if(aux[i] > aux[j]) arr[k] = aux[j++];
else arr[k] = aux[i++];
}
} /**
* 插入排序: 对数组arr [lo...hi]部分进行插入排序
*/
public void insertion(int[] arr,int lo,int hi){
for(int i=lo+1;i<=hi;++i)
for(int j=i;j>lo && arr[j]<arr[j-1];--j){
//交换
arr[j] = arr[j]^arr[j-1];
arr[j-1] = arr[j]^arr[j-1];
arr[j] = arr[j]^arr[j-1];
}
}- 测试
@Test
public void testMerge() {
//创建数组
int[] arr = Arrays.stream(SortTemplate.getArray(111)).mapToInt(x -> (int) x).toArray();
aux = arr.clone(); //辅助数组初始化,与arr相同
merge(arr,aux,0,arr.length-1); //优化后的归并排序
System.out.println("\n" + SortTemplate.isSorted(arr)); //是否有序
}2.自底向上的归并排序
概述:
对于需要排序的数组先取子序列长度为1进行两两归并,归并后成为子序列长度为2的多个有序序列(最后一个子序列长度小于等于2)
再对子序列为2的多个有序序列进行两两归并,归并后成为子序列长度为4的多个有序序列(末尾子序列长度<=4)
依次类推按照8,16,32…进行归并,直到最后归并为一个序列结束,此时数组排序完成
/**
* 自底向上的归并排序
*/
public static int[] aux; //辅助数组
public void merge(int[] arr){
aux = arr.clone();
for(int i=1,len=arr.length;i<len;i<<=1)
for(int lo =0;lo<len-i;lo += i<<1)
inPlaceMerge(arr,lo,lo+i-1,Math.min(lo+(i<<1)-1,len-1));
} /**
* 将2个有序序列归并为一个有序序列
*/
public void inPlaceMerge(int[] arr,int lo,int mid,int hi){
for(int i=lo;i<=hi;++i)
aux[i] = arr[i];
int i = lo,j = mid+1;
for(int k=lo;k<=hi;++k) {
if (i > mid) arr[k] = aux[j++];
else if (j > hi) arr[k] = aux[i++];
else if (aux[i] > aux[j]) arr[k] = aux[j++];
else arr[k] = aux[i++];
}
}3.多线程并行归并排序
利用Fork/Join框架多线程并行归并
//使用Fork/Join进行归并排序
class Merge<E> extends RecursiveAction{
private E[] elements;
private E[] aux;//辅助数组
private Comparator<E> comparator; //比较器
private int lo;
private int hi;
public Merge(E[] elements, Comparator<E> comparator) {
this.elements = elements;
this.aux = (E[])new Object[elements.length];
this.comparator = comparator;
//准备数据
this.lo = 0;
this.hi = elements.length-1;
}
public Merge(E[] elements){
this.elements = elements;
this.aux = (E[])new Object[elements.length];
this.comparator = (E x,E y) -> {
if(x instanceof Comparable) return ((Comparable) x).compareTo(y);
else throw new RuntimeException("需要传入Comparator或者实现Comparable");
};
//准备数据
this.lo = 0;
this.hi = elements.length-1;
}
//私有构造方法用于分支调用
private Merge(E[] elements, E[] aux, Comparator<E> comparator, int lo, int hi) {
this.elements = elements;
this.aux = aux;
this.comparator = comparator;
this.lo = lo;
this.hi = hi;
}
//单线程归并
public void sort(){
merge(elements,aux,lo,hi);
}
//多线程并行归并
public void parallelSort(){
ForkJoinPool forkJoin = (ForkJoinPool) Executors.newWorkStealingPool();
try {
forkJoin.submit(this).get();//提交任务并获取等待结束
} catch (InterruptedException e) {
e.printStackTrace();
} catch (ExecutionException e) {
e.printStackTrace();
}
forkJoin.shutdown();
}
@Override
protected void compute() {
if(hi - lo <= 10000) merge(elements,aux,lo,hi);
else{
//分成两部分,分别进行归并操作
int mid = lo + (hi-lo)/2;
Merge<E> mergeTask1 = new Merge<>(elements,aux,comparator,lo,mid);
Merge<E> mergeTask2 = new Merge<>(elements,aux,comparator,mid+1,hi);
//mergeTask1.fork(); //分支(异步): 子任务交给其他线程处理
//mergeTask2.fork();
//mergeTask1.join(); //获取(同步): 阻塞当前线程并等待获取结果
//mergeTask2.join();
invokeAll(mergeTask1,mergeTask2); //批量提交子任务,会阻塞到结果返回: 与fork不同,mergeTask1会分配给当前线程
inPlaceMerge(elements,lo,mid,hi);
}
}
//归并排序(对arr数组[lo,hi]部分进行归并排序)
private void merge(E[] arr,E[] aux,int lo,int hi){
for(int i=lo;i<=hi;++i)
aux[i] = arr[i];
for(int i=1,len=hi-lo+1;i<len;i<<=1)
for(int j = lo;j<=hi-i;j += i<<1)
inPlaceMerge(arr,j,j+i-1,Math.min(j+(i<<1)-1,hi));
}
private void inPlaceMerge(E[] elements,int lo,int mid,int hi){
for(int i=lo;i<=hi;++i)
aux[i] = elements[i];
int i = lo,j = mid+1;
for(int k=lo;k<=hi;++k) {
if (i > mid) elements[k] = aux[j++];
else if (j > hi) elements[k] = aux[i++];
else if (((Comparable)aux[i]).compareTo(aux[j]) > 0) elements[k] = aux[j++];
else elements[k] = aux[i++];
}
}
}