1.归并排序
解题代码：
package 第七天分治思想;
public class 归并排序 {
static int [] a;
static int [] b;
static void paixu(int []a,int s,int e,int [] b){
if(s<e){//为什么要用if，而不能用while
int m=s+(e-s)/2;
paixu(a,s,m,b);
paixu(a,m+1,e,b);
paixu1(a,s,m,e,b);
}
}
static void paixu1(int[] a,int s,int m,int e,int [] b){//此函数的作用为将数组a里面的[a,m],[m+1],e段进行排序
int p0=0;//作为新数组的指针
int p1=s;
int p2=m+1;//两个数组开头的指针
while(p1<=m&&p2<=e){
if(a[p1]<a[p2]){
b[p0++]=a[p1++];
}else {
b[p0++]=a[p2++];
}
}
while(p1<=m){
b[p0++]=a[p1++];
}
while(p2<=e){
b[p0++]=a[p2++];
}
for(int i=0;i<e-s+1;i++){
a[s+i]=b[i];
}
}
public static void main(String[] args) {
a=new int[5];
b=new int[5];
a[0]=12;
a[1]=15;
a[2]=3;
a[3]=8;
a[4]=0;
//排序算法
paixu(a,0,4,b);
for(int i:b){
System.out.println(i);
}
}
}
2.快速排序
解题代码：
package 第七天分治思想;
public class 快排 {
// static void swap(int a,int b){//交换函数
//
// int temp=a;
// a=b;
// b=temp;
// }
static void quicksort(int [] a,int i,int j){
if(i>=j){
return;
}
int k=a[i];
int s=i;
int e=j;
while(s!=e){
while(s<e&&a[e]>=k){
e--;
}
a[s]=a[e];
while(s<e&&a[s]<=k){
s++;
}
a[e]=a[s];
}
a[s]=k;//这一句
//还有swap函数在这里为什么不能起作用？？？
quicksort(a,i,s-1);
quicksort(a,s+1,j);
}
public static void main(String[] args) {
int []a=new int[5];
a[0]=7;
a[1]=8;
a[2]=3;
a[3]=4;
a[4]=11;
quicksort(a,0,4);
for(int i :a){
System.out.println(i);
}
}
}