2024年4月14日发(作者：)
1) 冒泡排序：
冒泡排序每遍历一次数组，便将最大的元素放到数组最后边。下次遍历将次大的元素放到数组
倒数第二位，依次类推，直至将最小的元素放到最前边，此时冒泡排序完成。
2) 快速排序：
快速排序是采用了分而治之的思想，但与合并排序有所不同的是快速排序先“工作〞〔这里是
分割或partition〕，再递归。快速排序的主要思想是保证数组前半局部小于后半局部的元素，
然后分别对前半局部和后半局部再分别进行排序，直至所有元素有序。
3) 两路合并排序
此外还对快速排序进行了改进，改进算法流程图如下所示：
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 { i=left; j=right+1; do { do i++;while (A[i] do j--;while (A[j]>A[left]); if(i Swap(A[i],A[j]); }while(i Swap(A[left],A[j]); QSort(A,left,j-1); } QSort(A,j+1,right); } } else { InsertSort(A,right-left+1); return ; } 五、测试和调试 1. 测试用例和结果 测试结果如以下图 1) 生成随机数据 2) 简单项选择择排序及其所需时间 3) 直接插入排序及其所需时间 4) 冒泡排序及其所需时间 5) 快速排序及其所需时间 6) 改进快速排序及其所需时间 7) 两路合并排序及其所需时间 2. 结果分析 简单项选择择排序的最好、最坏的平均情况的时间复杂度都为O(n)；冒泡排 序最好情况的时间复杂度为O(n)，最坏情况的时间复杂度为O(n)，最坏情况的时 间复杂度为O(nlog 2 两路合并排序的时间复杂度为O(nlog 2 22 22 六、 实习小结
发布评论