logo资料库

中科大快速排序算法及优化实验报告.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.15M 资料格式：doc 举报 版权申诉
第1页 / 共4页
第2页 / 共4页
第3页 / 共4页
第4页 / 共4页
资料共4页，全文预览结束
    《算法设计与分析》上机报告 姓名： 学号： 日期： 上机题目： 快速排序算法及优化 ;软件平台： vs2017 ; ; 内存: 4G ;操作系统： win10 实验环境： CPU： i7 一、算法设计与分析： 题目：快速排序算法及优化 分治法思想：首先对整个区间进行划分，为两个子区间，递归地对两个子区间进 行快排，然后将区间组合到一起。 改进思想：引入三数取中方法，虽然随机选取基准时可以减少出现不好分割的几 率，但是还是最坏情况下是 O(n2)，要缓解这种情况就引入了三数取中选取基准 的方法。 二、核心代码： 快速排序核心代码： templatevoid QuickSort(T* arr, int begin, int end) { assert(arr); if (begin int SelectMid(T* arr, int begin, int end) { int left = begin; int right = end; //(begin+end)>>1; int mid = begin + ((end - begin) >> 1);
    if (arr[left]arr[mid]) return mid; if (arr[left] < arr[right]) return right; else return left; } else { if (arr[right] < arr[mid]) return mid; if (arr[right]>arr[left]) return left; return right; else } } 三、结果与分析： 运行时间分析： 快速排序是一种分而治之的算法，它是已知的最快的排序算法，其平均运行 时间为 O(nlgn)。它的速度主要归功于一个非常紧凑的并且高度优化的内部循环。 但是它也是一种不稳定的排序，当基准数选择的不合理的时候，它的效率会变成 O(n2)。 最好、最坏情况： 最好的情况是每次选出的关键字接近中位数，其运行时间就为 O(nlgn)； 最坏的情况是当分组重复生成一个空序列的时候或者选取的关键字不科学的时 候。 分析： 最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用 序列的中间的值，也就是第 N/2 个数。可是，这很难算出来，并且会明显减慢快 速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作 为基准元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左 端、右端和中心位置上的三个元素的中值作为基准元。显然使用三数中值分割法 消除了预排序输入的不好情形，并且减少快排大约 14%的比较次数。 四、备注（* 可选）： 有可能影响结论的因素： 每一次关键字的选取。
    总结： 快速排序最坏情况时间复杂度为 O(n2)，在元素互异的情况下，期望石家金 复杂度是 O(nlgn)。 算法源代码（C/C++/JAVA 描述） #include #include #include using namespace std; int partition(vector &vi, int low, int up) { int pivot = vi[up]; int i = low - 1; //记录 A[low,,,,up]<=pivot for (int j = low; j < up; j++) { } if (vi[j] <= pivot) { //如果<，往左交换 i++; //左边扩大 swap(vi[i], vi[j]); //交换 } swap(vi[i + 1], vi[up]); //将划分元 vot 置入 A[low+1]，好处是不用 使用额外的空间 附录（源代码） return i + 1; } //C++'s array range should be [low, up], the same as [low, up+1) void quickSort(vector &vi, int low, int up) { } if (low < up) { } int mid = partition(vi, low, up); quickSort(vi, low, mid - 1); //快排第一个子问题 quickSort(vi, mid + 1, up); //快排第二个子问题 void qSort(vector &vi) { } quickSort(vi, 0, vi.size() - 1); int main() { int a[] = { 3,5,7,9,2,3,1,0,7,5,4 }; vectorva(a, a + 11);
    cout << "输入的是：" << "\n"; for (auto x : va) cout << x << " "; cout << endl; qSort(va); cout << "快排后的是：" << "\n"; for (auto x : va) cout << x << " "; cout << endl; system("pause"); return 0; }
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料