C++实现快速排序归并排序算法设计
5星 · 超过95%的资源 需积分: 10 73 浏览量
2010-04-23
23:55:45
上传
评论
收藏 44KB DOC 举报 
1.实验题目
快速排序、归并排序
2.实验要求
运用快速排序和归并排序算法，对记录进行排序。
3.实验思路
快速排序：通过一组排序将要排序的数据分割成独立的两部分，其中一部分的
所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据
分别进行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列。
对于输入的子数组 a[l,r],按以下 3 个步骤进行排序
1）分解(divide):以 a[l]为基准元素将 a[l,r]划分成 3 段 a[l:i-1],a[i],a[i+1:r],使得
a[l:i-1]中任何一个元素小于等于 a[i]，a[i+1,r]中任何一个元素大于等于 a[i]。下
标 i 在划分过程中确定。
2）递归求解(conquer):通过递归调用快速排序算法，分别对 a[l:i-1]和 a[i+1:r]进
行排序。
3）合并(merge)：由于对 a[l:i-1]和 a[i+1:r]的排序是就地进行的，所以在 a[l:i-1]
和 a[i+1:r]都已排好的序后不需要执行任何计算，a[l:r]就已排好序了。伪代码
归并排序：对一个数组进行排序，可以将之分解为 n 个已经排序的子问题，然
后进行合并就可以得到了原问题的解。分治法的基本思想是将一个规模为 n 的
问题分解为 k 个规模较小的子问题，这些子问题相互独立且与原问题相同。递
归的解这些子问题，然后将个子问题的解合并得到原问题的解。分为三步：
1）把大的问题分解成小的问题：MergeSort;
2）把两个较小的子问题合并成一个较大的问题：Merge；
3）对已排序数组进行拷贝：Copy;
4.伪代码
快速排序伪代码：
void quicksort(int R[],int left,int right)
{
If(lift<right){
Pivot=partition(r,lift,right);
Quicksort(r,lift,pivot-1);
Quicksort(r,pivot+1,right);
}
}
归并排序伪代码：
Void mergesort(int r[],int r1[],int s,int t)
{
If(s==t)r1[s]=r[s];
Else{
M=(s+r)/2;
Mergesort(r,r1,s,m);
资源评论
freehero0242014-08-11感谢楼主的分享，目前的一个项目正好需要这个算法，好用！
