EDA365电子论坛网
标题:
《算法导论(第三版)》第七章，快速排序
[打印本页]
作者:
Zedd
时间:
2020-3-10 10:24
标题:
《算法导论(第三版)》第七章，快速排序
《算法导论(第三版)》第七章，快速排序
v4 a5 J, ~8 M
, T4 [( y: W \3 ]& a/ g/ W; e
main
/ R# r: x( g& `( d5 i
clear;clc
A=[2 8 7 1 3 5 6 4]%测试数组
A=QUICKSORT(A,1,length(A))
& a. p8 R, x- |* G' z' p
7 g9 q; @- b) Q9 G/ z
0 ]" D6 n) a0 r- p5 ]. h* W! I
( t L- J9 f+ [: X1 I G
QUICKSORT
) f+ e# G r. E0 U7 P
function [A] = QUICKSORT(A,p,r)
if p<r %还存在未排序的子数组
[A q]=PARTITION(A,p,r);%以A(r)作为中间值来划分数组，中间值最后保存为A(q)
A=QUICKSORT(A,p,q-1);%q的前半部分排序
A=QUICKSORT(A,q+1,r);%q的后半部分排序
end
end
l; }# l. b$ ^' i
1 p |3 _" V( Q
! E& | O$ G& T- N7 @: k
. [! m$ u `' `/ ^9 l
PARTITION
3 a, Z, y# U( f6 c+ ^6 I7 S1 o
function [A,q] = PARTITION(A,p,r)
flag=A(r);%A(r)为中间值
q=p-1;%中间值q。可能末尾为最大值，则不存在分开两侧，所以从起始前一位置分段
for j=p:r-1%起始值到(最后值的前一位)
if A(j)<=flag
q=q+1;
temp=A(q);
A(q)=A(j);
A(j)=temp;
end
end
q=q+1;%中间值的位置
%交换
temp=A(q);
A(q)=A(r);
A(r)=temp;
end
! V) R$ y% D9 `4 Y
" s4 |: S( k1 e- R9 X9 ~
" I0 Z* Y8 V0 S- d d
: D; B9 b( O, Y* l, x
0 T4 \( e. N3 p [& F
作者:
wu68aq
时间:
2020-3-10 17:50
看看楼主分享的快速排序代码。
欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/)
Powered by Discuz! X3.2