南邮数据结构上机实验四内排序算法的实现以及性能比较(2)

GQuickSort ()

四、程序代码

template

void GQuickSort(T A[],int n) //改进的快速排序 { GQSort(A,0,n-1); }

template

void GQSort(T A[],int left,int right) { int i,j;

}

if(right>=9) {

if(left

五、测试和调试

1. 测试用例和结果

测试结果如下图 1) 生成随机数据

2) 简单选择排序及其所需时间

3) 直接插入排序及其所需时间

4) 冒泡排序及其所需时间

5) 快速排序及其所需时间

6) 改进快速排序及其所需时间

7) 两路合并排序及其所需时间

2. 结果分析

简单选择排序的最好、最坏的平均情况的时间复杂度都为O(n),是不稳定的排序方法；直接插入排序的最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n)；冒泡排序最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n)，是稳定的排序方法；快速排序最好情况的时间复杂度为O(n)，最坏情况的时间复

2

2

2

2