排序算法（Java、C++）归并排序（二）
归并排序
分成两边 左边就行排序 右边进行排序
然后左边在分成一半 右边也一样分成一半
不断往下分 直到成独立的就
要生成一个额外的空间，典型的空间换时间
往上归并的过程
左边和右边的进行比较谁小 就往新的空间插入
先下 然后又上 是不是觉得很像栈？这样就可以使用递归 进行解决这个问题
仔细看代码 递归 慢慢理解
//递归使用归并排序，对arr[mid+1...r]两部分进行归并
private static void sort(Comparable[] arr,int l,int r){
if(l >=r)//基本问题，也是出口
return ;
int mid=(l+r)/2;
sort(arr,l,mid);//左边的一半 一直递归排序
sort(arr,mid+1,r);//右边的一半 一直递归排序
merge(arr,l,mid,r);//往上归并
}
然后是归并的代码
private static void merge(Comparable[] arr,int l,int mid,int r){
Comparable[] aux=Arrays.copyOfRange(arr, l, r+1);//生成的额外的空间
//初始化，i指向左边部分的起始位置l:j指向右半部分起始索引位置mid+1
int i=l,j=mid+1;
for(int k=l;k<=r;k++){
if(i>mid){//如果左部分元素已经全部处理完毕
arr[k]=aux[j-l];
j++;
}else if(j>r){//如果右半部分元素已经全部处理完毕
arr[k]=aux[i-l];
i++;
}else if(aux[i-l].compareTo(aux[j-l]) <0){//左半部分所指元素 < 右半部分所指元素
arr[k]=aux[i-l];
i++;
}else{//左半部分所指元素 >=右部分所指元素
arr[k]=arr[j-l];
j++;
}
}
}
这里优化了一下
规模小于15 直接使用插入排序
// 递归使用归并排序,对arr[l...r]的范围进行排序
private static void sort(Comparable[] arr, int l, int r) {
// 优化2: 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
InsertionSort.sort(arr, l, r);
return;
}
int mid = (l+r)/2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
// 优化1: 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid].compareTo(arr[mid+1]) > 0 )
merge(arr, l, mid, r);
}
Java整体的代码
package com.binglian.Sort;
import java.util.Arrays;
public class MergeSort {
//我们的算法类不允许产生实例
private MergeSort(){}
private static void merge(Comparable[] arr,int l,int mid,int r){
Comparable[] aux=Arrays.copyOfRange(arr, l, r+1);//生成的额外的空间
//初始化，i指向左边部分的起始位置l:j指向右半部分起始索引位置mid+1
int i=l,j=mid+1;
for(int k=l;k<=r;k++){
if(i>mid){//如果左部分元素已经全部处理完毕
arr[k]=aux[j-l];
j++;
}else if(j>r){//如果右半部分元素已经全部处理完毕
arr[k]=aux[i-l];
i++;
}else if(aux[i-l].compareTo(aux[j-l]) <0){//左半部分所指元素 < 右半部分所指元素
arr[k]=aux[i-l];
i++;
}else{//左半部分所指元素 >=右部分所指元素
arr[k]=arr[j-l];
j++;
}
}
}
//递归使用归并排序，对arr[mid+1...r]两部分进行归并
private static void sort(Comparable[] arr,int l,int r){
if(l >=r)//基本问题，也是出口
return ;
int mid=(l+r)/2;
sort(arr,l,mid);//左边的一半 一直递归排序
sort(arr,mid+1,r);//右边的一半 一直递归排序
merge(arr,l,mid,r);//往上归并
}
public static void sort(Comparable[] arr){
int n=arr.length;
sort(arr,0,n-1);
}
//测试MergeSort
public static void main(String[] args) {
//Merge Sort是我们学习的第一个O(nlogn)复杂度的算法
//可以在1秒字后轻松处理100万数量级的数据
//注意:不要轻易尝试使用SelectionSort,InsertionSort或者BubbleSort处理100万级的数据
int N=1000000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
SortTestHelper.testSort("com.binglian.Sort.MergeSort", arr);
}
}
C++版本
//
// Created by liuyubobobo on 7/16/16.
//
#ifndef INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H
#define INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H
#include <iostream>
#include <algorithm>
#include "InsertionSort.h"
using namespace std;
// 将arr[l...mid]和arr[mid+1...r]两部分进行归并
template<typename T>
void __merge(T arr[], int l, int mid, int r){
//* VS不支持动态长度数组, 即不能使用 T aux[r-l+1]的方式申请aux的空间
//* 使用VS的同学, 请使用new的方式申请aux空间
//* 使用new申请空间, 不要忘了在__merge函数的最后, delete掉申请的空间:)
T aux[r-l+1];
//T *aux = new T[r-l+1];
for( int i = l ; i <= r; i ++ )
aux[i-l] = arr[i];
// 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
int i = l, j = mid+1;
for( int k = l ; k <= r; k ++ ){
if( i > mid ){ // 如果左半部分元素已经全部处理完毕
arr[k] = aux[j-l]; j ++;
}
else if( j > r ){ // 如果右半部分元素已经全部处理完毕
arr[k] = aux[i-l]; i ++;
}
else if( aux[i-l] < aux[j-l] ) { // 左半部分所指元素 < 右半部分所指元素
arr[k] = aux[i-l]; i ++;
}
else{ // 左半部分所指元素 >= 右半部分所指元素
arr[k] = aux[j-l]; j ++;
}
}
//delete[] aux;
}
// 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r){
// 对于小规模数组, 使用插入排序
if( r - l <= 15 ){
insertionSort(arr, l, r);
return;
}
int mid = (l+r)/2;
__mergeSort(arr, l, mid);
__mergeSort(arr, mid+1, r);
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
// 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
if( arr[mid] > arr[mid+1] )
__merge(arr, l, mid, r);
}
template<typename T>
void mergeSort(T arr[], int n){
__mergeSort( arr , 0 , n-1 );
}
#endif //INC_04_MERGE_SORT_BOTTOM_UP_MERGESORT_H
还有一种直接往上，因为省略了往下排序,所以不用递归都可以实现，用迭代
for( int sz = 16; sz < n ; sz += sz )
sz+=sz 就是当前加上自己 比如看一个元素，然后加上自己 第二个 然后再是第四个 就是往上的归并
public static void sort(Comparable[] arr){
int n = arr.length;
// Merge Sort Bottom Up 无优化版本
// for (int sz = 1; sz < n; sz *= 2)
// for (int i = 0; i < n - sz; i += sz+sz)
// // 对 arr[i...i+sz-1] 和 arr[i+sz...i+2*sz-1] 进行归并
// merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1));
// Merge Sort Bottom Up 优化
// 对于小数组, 使用插入排序优化
for( int i = 0 ; i < n ; i += 16 )
InsertionSort.sort(arr, i, Math.min(i+15, n-1) );
for( int sz = 16; sz < n ; sz += sz )
for( int i = 0 ; i < n - sz ; i += sz+sz )
// 对于arr[mid] <= arr[mid+1]的情况,不进行merge
if( arr[i+sz-1].compareTo(arr[i+sz]) > 0 )
merge(arr, i, i+sz-1, Math.min(i+sz+sz-1,n-1) );
}