使用Matlab实现快速排序.doc

使用Matlab实现快速排序算法快速排序算法是基于分治策略的排序算法，基本思想是：对于输入的子数组ap,r,按照以下三个步骤进行排序：（1） 分解。以ap为基准元素将ap,r划分为3段(a中各元素的值不相同)，ap,q1，aq, aq+1,r，使得ap,q1中的所有元素都小于aq，aq+1,r中所有元素都大于aq。下表q的值在分解过程中确定。（2） 递归求解。递归调用快速排序算法分别对ap,q1和aq+1,r进行排序。（3） 合并。由于对ap,q1和aq+1,r的排序是在元数组中进行的，对ap,q1和aq+1,r排序完成后，不需执行任何计算，ap,r中的元素已完成排序。用Matlab实现如下: function a = quick_sort(a, p, r)% 快速排序算法。% a： 待排序的数组% p，r： 指定待排序子数组的下标范围。% 即对数组a的子数组ap,p+1,.,r进行排序% 用法举例：% a = 3 7 1 8 5 2 4 6; quick_sort(a,1,length(a);if(p r) % 以ap为基准元素将ap,r划分为3段, 并获得下标q. a, q = partition(a, p, r); % 递归调用. 对左半段数组进行排序. a = quick_sort(a, p, q-1); % 递归调用. 对右半段数组进行排序. a = quick_sort(a, q+1, r);end;% 以ap为基准元素将ap,r划分为3段, ap,q1，% aq, aq+1,r，使得ap,q1中的所有元素都% 小于或等于aq，aq+1,r中所有元素都大于或等于% aq。% 并获得下标q.%function b, q = partition(a, p, r)i = p; j = r; % 获得最左下标i和最右下标j.ref = a(p); % 以元素ap作为基准ref.% 将不大于ref的元素交换到左边区域, % 将不小于ref的元素交换到右边区域.while(1) % 从数组左端开始扫描,找到不小于ref的元素的下标i while(a(i)=r) break; end;% 如果到数组右端,则跳出循环 end; % 从数组右端开始扫描,找到不大于ref的元素的下标i while(a(j)ref) j = j-1; % 向左扫描 end; if(i=j) break; end; % 如果i=j, 跳出循环. % 交换a(i)和a(j)的值 a = swap(a, i, j);end;% 计算函数返回值.b = a;q = j;disp(num2str(a); % 显示处理结果.% 交换数组a中i和j两个元素的值.%function b = swap(a, i, j)tmp = a(i); a(i)=a(j); a(j) = tmp;b = a;将以上代码保存为quick_sort.m在命令行输入以下命令:a = 3 7 1 8 5 2 4 6; quick_sort(a,1,length(a);执行结果为: 2 1 3 8