2020-8-16
private void merge(Comparable[] a,int lo,int mid,int hi){
for(int i=lo;i<=hi;i++){
tep[i]=a[i];//辅助数组tep
}
int left=lo;//左部分开始
int right=mid+1;//右部分开始元素下标
for(int i=lo;i<=hi;i++){
if(left>mid) a[i]=tep[right++];//左部分用完
else if(right>hi) a[i]=tep[left++];//右部分用完
else if(less(tep[left],tep[right])) a[i]=tep[right++];//比较大小
else a[i]=tep[left++];//比较大小
}
}
package Algorithm;
public class Merge {
private boolean less(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
Comparable[] tep;
public void sort(Comparable[] a){
tep=new Comparable[a.length];
sort(a,0,a.length-1);
}
private void sort(Comparable[] a,int lo,int hi){
if(hi<=lo) return;
int mid=lo+(hi-lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
private void merge(Comparable[] a,int lo,int mid,int hi){
for(int i=lo;i<=hi;i++){
tep[i]=a[i];//辅助数组tep
}
int left=lo;//左部分开始
int right=mid+1;//右部分开始元素下标
for(int i=lo;i<=hi;i++){
if(left>mid) a[i]=tep[right++];//左部分用完
else if(right>hi) a[i]=tep[left++];//右部分用完
else if(less(tep[left],tep[right])) a[i]=tep[right++];//比较大小
else a[i]=tep[left++];//比较大小
}
}
}
可用于链表排序
public void sort(Comparable[] a){
tep=new Comparable[a.length];
int n=a.length;
for (int sz= 1; sz<n; sz=sz+sz) {//sz,数组大小（从0计算，o-5,则sz=5）
for (int lo=0;lo<n-sz;lo+=sz+sz){//lo,数组开始下标。每次lo=lo+sz+sz,合并两个数组大小
merge(a,lo,lo+sz-1,Math.min(n-1,lo+sz+sz-1));
}
}
}
private void sort(Comparable[] a,int lo,int hi){
if(hi<=lo) return;
if(hi-lo<=7){//小规模采用插入排序**********
for(int i=lo;i<=hi;i++){
for(int j=i;j>lo;j--){
if(a[j].compareTo(a[j-1]<0)){
Comparable t=a[j];
a[j]=a[j-1];
a[j-1]=t;
}
}
}
}
int mid=lo+(hi-lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
merge(a,lo,mid,hi);
}
private void sort(Comparable[] a,int lo,int hi){
if(hi<=lo) return;
int mid=lo+(hi-lo)/2;
sort(a,lo,mid);
sort(a,mid+1,hi);
****if(a[mid].compareTo(a[mid+1])<=0) return;*****//判断是否有序
merge(a,lo,mid,hi);
}
注意空间不能优化
将此辅助数组变为在递归中的参数即可。这样的话，上面两个代码都要改变。
package Algorithm;
public class Merge {
private boolean less(Comparable v,Comparable w){
return v.compareTo(w)>0;
}
private void exch(Comparable[] a,int i,int j){
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
public void sort(Comparable[] a){
Comparable[] tep=a.clone();
sort(tep,a,0,a.length-1);
}
private void sort(Comparable[] src, Comparable[] dst, int lo, int hi){
if(hi<=lo) return;
if(hi<=lo+7){
for(int i=lo;i<=hi;i++){
for(int j=i;j>lo;j--){
if(less(dst[j-1],dst[j])){
exch(dst,j,j-1);
}
}
}
return;
}
int mid=lo+(hi-lo)/2;
sort(dst,src,lo,mid);
sort(dst,src,mid+1,hi);
if(less(src[mid+1],src[mid])){
System.arraycopy(src,lo,dst,lo,hi-lo+1);
return;
}
merge(src,dst,lo,mid,hi);
}
private void merge(Comparable[] src,Comparable[] dst,int lo,int mid,int hi){
int left=lo;//左部分开始
int right=mid+1;//右部分开始元素下标
for(int i=lo;i<=hi;i++){
if(left>mid) dst[i]=src[right++];//左部分用完
else if(right>hi) dst[i]=src[left++];//右部分用完
else if(less(src[left],src[right])) dst[i]=src[right++];//比较大小
else dst[i]=src[left++];//比较大小
}
}
}
参考自：https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/MergeX.java
2019-4-23
分解：将待排序的n个元素分成n/2两个子序列
解决：使用归并排序递归的排序两个子序列
合并：合并两个已排序好的子序列来生成排序好的答案。
当待排序的序列长度为1时，递归回升，因为这时长度为1的序列，已经排序好了。我们不需要任何操作。
这里讲一下具体操作：将要排序的一组数分成两堆（这里我们选取中间点为划分标准），然后我们从两堆中的第一个元素比较，小的（或者大的，这里要求我们是降序还是升序排列）就放到一个新开的数组里面，来保存我们所需要的答案。
#include<stdio.h>
void MERGE(int *num,int p,int q,int r)
{
int n1,n2;//两边各多少个元素
n1=q-p+1;
n2=r-q;
int am[50]={0};
int ab[50]={0};
for(int i=0;i<n1;i++)
{
am[i]=num[p+i];
}
am[n1]=0x3f3f3f3f;//作为结束的哨兵
for(int i=0;i<n2;i++)
{
ab[i]=num[q+1+i];
}
ab[n2]=0x3f3f3f3f;
int j=0;
int i=0;//分别是两个待排序数组的下标
for(int k=p;k<=r;k++)//从p到r,保证了所有元素都被排序
{
if(am[i]<=ab[j])
{
num[k]=am[i];
i++;
}
else
{
num[k]=ab[j];
j++;
}
}
}
void MERGE_SORT(int *num,int p,int r)
{
if(p<r)
{
int q=(p+r)/2;
MERGE_SORT(num,p,q);
MERGE_SORT(num,q+1,r);
MERGE(num,p,q,r);
}
}
int main(void)
{
int num[50]={96,1,2,3,66,805,45,63,67,59,57,50,52,23,24};//15个
printf("排序前\n");
for(int j=0; j<=14; j++)
{
printf("%d ",num[j]);
}
putchar('\n');
MERGE_SORT(num,0,14);
printf("排序后\n");
for(int j=0; j<=14; j++)
{
printf("%d ",num[j]);
}
putchar('\n');
}
`
因篇幅问题不能全部显示，请点此查看更多更全内容