2.3.25切换到插入排序。实现一个快速排序，在子数组元素少于M时切换到插入排序。用快速排序处理大小N分别为10^3、10^4、10^5和10^6的随机数组，根据经验给出使其在你的计算环境中运行速度最快的M值。将M从0变化到30的每个值所得到的平均运行时间绘成曲线。注意：你需要为算法2.2添加一个需要三个参数的sort()方法以使Insertion.sort(a,lo,hi)将子数组a[lo..hi]排序。
答：
1）使用10^6长度的数组，M从2到99,进行了100次测试，排序用时最少的M在6至25之间，其中M=11时，排序用时最少的次数出现最多。具体有：M=11时
15次用时最少，M=15时 12次用时最少，M=13时 12次用时最少,M=10时 11次用时最少。
2)见图
import java.awt.Color;
public class E2d3d25
{
public static void sort(Comparable[] a,int M)
{
//StdRandom.shuffle(a);
sort(a,0,a.length-1,M);
}
private static void sort(Comparable[] a,int lo,int hi,int M)
{
//数组少于等于M个元素时使用插入排序
if (hi-lo+1<M)
{
InsertSort(a,lo,hi);
return;
}
int j=partition(a,lo,hi);
sort(a,lo,j-1,M);
sort(a,j+1,hi,M);
}
private static int partition(Comparable[] a,int lo,int hi)
{
int i=lo,j=hi+1;
Comparable v=a[lo];
while(true)
{
while(less(a[++i],v)) if(i==hi) break;
while(less(v,a[--j])) if(j==lo) break;
if(i>=j) break;
exch(a,i,j);
}
exch(a,lo,j);
return j;
}
private static void InsertSort(Comparable[] a,int lo,int hi)
{
for (int i=lo+1;i<hi+1;i++)
{
for (int j=i;j>0 && less(a[j],a[j-1]);j--)
exch(a,j,j-1);
}
}
private static boolean less(Comparable v,Comparable w)
{ return v.compareTo(w)<0;}
private static void exch(Comparable[] a,int i,int j)
{
Comparable t=a[i];
a[i]=a[j];
a[j]=t;
}
private static void show(Comparable[] a)
{
for (int i=0;i<a.length;i++)
StdOut.print(a[i]+" ");
StdOut.println();
}
public static boolean isSorted(Comparable[] a)
{
for (int i=1;i<a.length;i++)
if(less(a[i],a[i-1])) return false;
return true;
}
public static void bestM()
{
//用来记录M不同值时排序花费的时间
Double[] T=new Double[100];
//使用一个10^6方的数组进行排序测试
int N=1000000;
Double[] a=new Double[N];
for(int i=0;i<N;i++)
a[i]=StdRandom.random();
//子数组最小长度只可能是1,所以M必须从1开始
//跳过为0、1的索引使得索引与M一一直接对应
for(int M=2;M<T.length;M++)
{
//对于不同的M使用相同的排列进行排序
Double[] aClone=new Double[a.length];
for(int i=0;i<a.length;i++)
aClone[i]=a[i];
//开始排序并计时
Stopwatch timer=new Stopwatch();
sort(aClone,M);
T[M]=timer.elapsedTime();
//StdOut.printf("%d %f
",M,T[M]);
}//end for M
//找出用时最小的M
int minM=2;
for(int i=3;i<T.length;i++)
if (less(T[i],T[minM])) minM=i;
StdOut.println("best M=" +minM);
}//end bestM
public static void drawAverageTime()
{
//
StdDraw.setXscale(0,35);
StdDraw.setYscale(-0.5,3);
//
int Nlen[]={100000,1000000,3000000};//
for(int Ni=0;Ni<Nlen.length;Ni++)
{
int N=Nlen[Ni];
//生成一个长度为N的数组a
Double[] a=new Double[N];
for(int i=0;i<N;i++)
a[i]=StdRandom.random();
//M从0至30对数对组a的副本进行排序,同一长度的N,不同的M时待排序数组内容相同
Double totalTime=0.0;
StdDraw.setPenColor(Color.BLACK);
StdDraw.setPenRadius(0.02);
for(int M=2;M<=30;M++)
{
//生成一个数组a的副本aClone
Double[] aClone=new Double[N];
for (int i=0;i<a.length;i++)
aClone[i]=a[i];
//数组长度为N,小于等于M时切换到插入排序的快速排序
Stopwatch timer=new Stopwatch();
sort(aClone,M);
totalTime=totalTime+timer.elapsedTime();
StdDraw.point(M,timer.elapsedTime());
}//end for M
StdDraw.setPenColor(Color.RED);
StdDraw.setPenRadius(0.01);
StdDraw.line(2,totalTime/29,30,totalTime/29);
}//end for Ni
}
public static void main(String[] args)
{
//for (int i=0;i<100;i++)
// bestM();
drawAverageTime();
}//end main
}//end class