算法 最大时间平均时间最小时间辅助空稳定 间代价性 排序e(n")en")(")()不 小结 快遠排序emn2) e(nlog n)e( nlog n)e(og叫不 n很小或基本有序时插入排序比 较有效 归并排序enga)e( nlog n) e(nlog n)e(n)稳定 She11排序选择增量以3的倍数递 「堆排序6loga) 9(nlog n).(nlog)e()|不秘 减 桶式排序0(a+m)e(m+m)|e(u+m)e(an+m稳定 需要保证最后一趟增量为1 基数排序(d(a+)e(d(a+r)e(d(m+r)e(u+r)稳定 ■综合性能快速排序最佳 真大物单张写 测试环境 随机生成待排序数组 ■硬件环境: /设置随机种子 /返回一个0到n之间的随机整数值 inline void Randomized i srand CPU: Intel p4 3G 内存:1G inline int Random(int n) return rando %o n:] ■软件环境 /产生随机数组 windows xp ELEM *sortarray =new ELEM[1000000] for(inti=0;i<1000000};i++) visual c++6.0 sortarray[]=Random(32003) 京大管息张铭编写 莉命究 北真大张写 热m时展测试。n 排序的时间测试 +define clocks per sec 1000 Settime o; for (i=o; i<ARRAYSIZE; i+=listsize)t clock_ t tstart= O; //Time at beginning sort<int intintCompare>(&array[i] //Initialize the program timer listsize) void Settimeo i tstart= clocko:] print(&array[i], listsize); // The elapsed time since last Settimeo cout < Sort with list size < listsize double Gettimeo array size< return(double(double)clocko << and threshold < THRESHOlD (double)tstart)/ < Gettime<<seconds\n (double)cLoCKs_PER_ SEC; 1 北京大息学 长铭端写 北真大脆张铭编写 2626 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 151 稳定 性 辅助空 间代价 算法 最大时间 平均时间 最小时间 基数排序 Θ(d·(n+r)) Θ(d·(n+r)) Θ(d·(n+r)) Θ(n+r) 稳定 桶式排序 Θ(n+m) Θ(n+m) Θ(n+m) Θ(n+m) 稳定 不稳 定 堆排序 Θ(nlog n) Θ(nlog n) Θ(nlog n) Θ(1) 归并排序 Θ(nlog n) Θ(nlog n) Θ(nlog n) Θ(n) 稳定 不稳 定 Θ(n Θ(nlog n) Θ(nlog n) Θ(log n) 2 快速排序 ) 不稳 定 Θ(n Θ(1) 3/2 Θ(n ) 3/2 Θ(n ) 3/2 Shell排序(3) ) 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 152 小结 „ n很小或基本有序时插入排序比 较有效 „ Shell排序选择增量以3的倍数递 减 „ 需要保证最后一趟增量为1 „ 综合性能快速排序最佳 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 153 测试环境 „ 硬件环境： „ CPU：Intel P4 3G „ 内存：1G „ 软件环境： „ windows xp „ Visual C++ 6.0 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 154 随机生成待排序数组 //设置随机种子 inline void Randomize() { srand(1); } // 返回一个0到n之间的随机整数值 inline int Random(int n) { return rand() % (n); } //产生随机数组 ELEM *sortarray =new ELEM[1000000]; for(int i=0;i<1000000;i++) sortarray[i]=Random(32003); 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 155 #include <time.h> /* Clock ticks macro - ANSI version */ 时间测试 #define CLOCKS_PER_SEC 1000 clock_t tstart = 0; // Time at beginning // Initialize the program timer void Settime() { tstart = clock(); } // The elapsed time since last Settime() double Gettime() { return (double)((double)clock() - (double)tstart)/ (double)CLOCKS_PER_SEC; } 北京大学信息学院 张铭编写 ©版权所有，转载或翻印必究 Page 156 排序的时间测试 Settime(); for (i=0; i<ARRAYSIZE; i+=listsize) { sort<int,intintCompare>(&array[i], listsize); print(&array[i], listsize); } cout << "Sort with list size " << listsize << ", array size " << ARRAYSIZE << ", and threshold " << THRESHOLD << ": " << Gettime() << " seconds\n";