《算法导论(第三版)》第七章，快速排序

Zedd

《算法导论(第三版)》第七章，快速排序
1 K$ H7 a) |' w1 ~
+ F5 ~2 N! Y6 H2 ]$ a; w( j9 f; Wmain
& l6 l) B( ~; Y2 @* g9 X( P4 s1 M

• clear;clc
• A=[2 8 7 1 3 5 6 4]%测试数组
• A=QUICKSORT(A,1,length(A))
  & J7 d1 `( X/ J: |# Y

1 Z1 j6 u/ G6 X1 D! I
" K0 Q+ C4 a  Q  z; Z4 XQUICKSORT
2 _: H. @+ ]( b; `3 d% d. p2 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
  6 ?2 X4 ^" [  g5 O; Z

2 R9 {* z6 n. x- _, \/ _7 ]2 H
8 l( C* S5 J& S/ V* @- m  l) s3 H
PARTITION

• 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
    o, z" N" R0 Z, |1 s& M$ R' J

+ }* Z& J  D9 x5 n& w( H9 \) o; S

wu68aq

看看楼主分享的快速排序代码。