快速排序和归并排序

《快速排序和归并排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三：快速排序和归并排序的实现与效率比较一、实验环境：windowsxpMatlabR2010b二、实验内容：对数组进行升序排序，运用快速排序和归并排序的方法实现。三、问题分析：1.快速排序2.归并排序四、算法描述：快速排序：是对冒泡排序的一种改进通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。伪代码：算法quick_sort输入一串乱序的整数输出一串递增的整数1.以第一个数a为ref，如果while

2、(a(i)ref)，4.j=j-1,向左扫描，找到第一个大于ref的值，执行swap算法5.递归执行，直到i=j;归并排序：归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列设定两个指针，最初位置分别为两个已经排序序列的起始位置比较两个指针所指向的元素，选择相

3、对小的元素放入到合并空间，并移动指针到下一位置重复步骤3直到某一指针达到序列尾将另一序列剩下的所有元素直接复制到合并序列尾。五、实验结果分析：归并排序，时间复杂度为O(nlogn)这是该算法中最好、最坏和平均的时间性能。赋值操作的次数是(2nlogn)。归并算法的空间复杂度为：0(n)。归并排序比较占用内存，但却效率高且稳定的算法。快速排序算法是不稳定的，最理想的情况下，算法时间复杂度为O(nlog2n),最坏为O(n2)，在最坏情况下的时间消耗不如归并排序。一、程序源代码：快速排序算法：Part1function[b,q]=Partition(a,p

4、,r)i=p;j=r;ref=a(p);%基准值while(1)while(a(i)=r)break;end;end;while(a(j)>ref)j=j-1;%向左扫描end;if(i>=j)break;end;a=swap(a,i,j);endb=a;q=j;disp(num2str(a));Part2functiona=quick_sort(a,p,r)if(p

5、%右半end调用函数：Part3a=[45361853723048931535];quick_sort(a,1,length(a));运行结果：35361815304548937253301518353645489372531815303536454893725315183035364548937253151830353645489372531518303536454853729315183035364548537293Elapsedtimeis0.257036seconds.归并排序算法：Part1function[tt,A]=ms(A,p,r)%Ê

6、µÏÖÒ»´Î¹é²¢ÅÅÐòx=A(r);i=p-1;temp=0;forj=p:r-1ifA(j)<=x%ɸѡ½ÏСµÄÔªËطŵ½Êý×éA(i)ÖÐi=i+1;temp=A(i);A(i)=A(j);A(j)=temp;endendtemp=A(i+1);A(i+1)=A(r);A(r)=temp;tt=i+1;endPart2functionA=mysort(A,p,r)%ʵÏֹ鲢ÅÅÐòº¯Êýifp

7、Part3tic;clear;clcA=[45361853723048931535];N=length(A);p=1;r=N;A=mysort(A,p,r)toc;运行结果：A=15183035364548537293Elapsedtimeis0.009773seconds.