{"id":321,"date":"2016-08-26T02:53:01","date_gmt":"2016-08-25T18:53:01","guid":{"rendered":"http:\/\/www.bookcard.net\/wordpress\/?p=321"},"modified":"2016-08-27T01:22:10","modified_gmt":"2016-08-26T17:22:10","slug":"algorithm_quicksort","status":"publish","type":"post","link":"https:\/\/www.bookcard.net\/wordpress\/algorithm_quicksort\/","title":{"rendered":"\u6392\u5e8f\u7b97\u6cd5-\u5feb\u901f\u6392\u5e8f"},"content":{"rendered":"

\u6392\u5e8f\u7b97\u6cd5-\u5feb\u901f\u6392\u5e8f
\n\u5feb\u901f\u6392\u5e8f\u662f\u7531C.A.R.Hoare\u57281960\u5e74\u63d0\u51fa.\u5bf9\u4e8e\u5927\u578b\u6570\u636e,\u5feb\u901f\u6392\u5e8f\u7b97\u6cd5\u7684\u6027\u80fd\u662f\u5e0c\u5c14\u6392\u5e8f\u76845\u523010\u500d.
\n\u5feb\u901f\u6392\u5e8f\u662f\u4e00\u79cd\u5206\u800c\u6cbb\u4e4b\u7b97\u6cd5,\u5b83\u5c06\u7d20\u7ec4\u5212\u5206\u6210\u4e24\u90e8\u5206,\u7136\u540e\u5206\u522b\u5bf9\u4e24\u4e2a\u90e8\u5206\u8fdb\u884c\u6392\u5e8f.
\n1.\u9009\u5219\u6700\u53f3\u5219\u7684\u5143\u7d20\u4f5c\u4e3a\u5212\u5206\u5143\u7d20v,\u7136\u540e\u4ece\u5de6\u5219\u626b\u63cf\u5c0f\u4e8ev\u7684\u5143\u7d20,\u7136\u540e\u4ece\u53f3\u5219\u626b\u63cf\u5927\u4e8ev\u7684\u5143\u7d20.
\n\u4ea4\u6362\u90a3\u4e9b\u4f7f\u626b\u63cf\u505c\u6b62\u7684\u5143\u7d20.
\n2.\u91cd\u590d\u8fdb\u884c\u8fd9\u6837\u7684\u8fc7\u7a0b\u76f4\u5230\u4e24\u4e2a\u6307\u9488\u76f8\u9047.
\n3.\u7136\u540e\u5206\u522b\u5bf9\u5de6\u53f3\u4e24\u6b65\u5206\u8fdb\u884c\u9012\u5f52\u5904\u7406.\u6700\u7ec8\u5f97\u5230\u4e00\u4e2a\u6392\u597d\u5e8f\u7684\u6570\u7ec4.<\/p>\n

\u4e0b\u9762\u7ed9\u51faC\u4ee3\u7801\u7684\u5b9e\u73b0.
\n\/\/ \u5212\u5206\u7b97\u6cd5
\n\/\/a:\u6570\u7ec4
\n\/\/l:\u6570\u7ec4\u7684\u5de6\u5219\u7d22\u5f15
\n\/\/r:\u6570\u7ec4\u7684\u53f3\u5219\u7d22\u5f15
\nint \u00a0 partition(int a[],int l,int r)
\n{
\nint i,j,v,t;
\ni = l;
\nj = r;
\nv = a[j];\/\/\u9009\u5219\u6700\u53f3\u5219\u7684\u5143\u7d20\u4f5c\u4e3a\u5212\u5206\u5143\u7d20v
\nwhile(true)
\n{
\nwhile(a[i]<v)
\n++i;\/\/ i\u7684\u5de6\u5219\u5c0f\u4e0ev<\/p>\n

while(v<a[j])
\n{
\n++j;\/\/ j\u7684\u53f3\u5219\u5927\u4e0ev
\nif(j==l)
\nbreak;\/\/ \u8df3\u51fa
\n}<\/p>\n

if(i>=j)
\nbreak;\/\/ \u4e24\u4e2a\u6307\u9488\u76f8\u9047\u8df3\u51fa\u626b\u63cf.<\/p>\n

\/\/ \u4ea4\u6362i,j,\u4ea4\u6362\u90a3\u4e9b\u4f7f\u626b\u63cf\u505c\u6b62\u7684\u5143\u7d20.
\nt=a[i];
\na[i]=a[j];
\na[j]=t;
\n}<\/p>\n

\/\/ \u4ea4\u6362i,r,\u4fdd\u8bc1v\u7684\u5de6\u5219\u5c0f\u4e8e\u4e8e\u5b83,v\u7684\u53f3\u5219\u5927\u4e8e\u5b83.
\nt=a[i];
\na[i]=a[r];
\na[r]=t;<\/p>\n

return i;
\n}<\/p>\n

\/\/\u5feb\u901f\u6392\u5e8f
\n\/\/a:\u6570\u7ec4
\n\/\/l:\u6570\u7ec4\u7684\u5de6\u5219\u7d22\u5f15
\n\/\/r:\u6570\u7ec4\u7684\u53f3\u5219\u7d22\u5f15
\nvoid quicksort(int a[],int l,int r)
\n{
\nint i;
\nif(l<=0)
\nreturn ;
\nquicksort(a,l,\u00a0 i-1);
\nquicksort(a,i+1,r);
\n}<\/p>\n

\/\/\u5feb\u901f\u6392\u5e8f
\n\/\/a:\u6570\u7ec4
\n\/\/c:\u6570\u7ec4\u7684\u957f\u5ea6
\nvoid quicksort(int a[],int c)
\n{
\nquicksort(a,0,c-1);
\n}<\/p>\n

 <\/p>\n