快速排序算法

快速排序一直是各大IT公司面试上机题的常考题目，如何破解一直很困惑，或者说一直忘记。下面用一种简单而且形象的描素来解决战斗。

该思想是基于填坑法和分治法的思想。下面先写算法：

填坑法：

head，tail，key

（1）       set key=A[head],so A[head] is the first “empty”(当然不是真正的空)

（2）       do tail--until find a data which is not bigger (==or <)than key, than do A[head](“empty”)=A[tail], now A[tail] is “empty”;

（3）       do head++ until find a data which is bigger than key, than do A[tail](“empty”)=A[head], so now A[head] is “empty”

（4）       do (2),(3) until head==tail;

Example:

Input: 3,2,6,5,9,0,4;

(1)     Now head=0, tail=6,key=A[head];A[head](A[0]) is “empty”

(2)     Tail--,when tail==5,A[tail]==0<key; so A[head](A[0])=A[tail]; now A[tail] is “empty”, 0,2,6,5,9,0,4;

(3)     Do head++ until head ==2,A[head]=6>key; so A[tail]()=A[head];now A[head] is “empty”;0,2,6,5,9,6,4;

(4)     Do (2),(3) until head==tail; 

Followed by: 0,2,3,5,9,6,4;

然后分治法，将上一次的key所在位置分成两个部分，分别对这两个部分再先填坑，然后分治。显然是一个迭代的过程。不多赘述。

光说不干，等于扯淡，直接上代码。

 

1 // try.cpp : Defines the entry point for the console application. 2 // 3  4 #include "stdafx.h" 5 #define FOR(n) for (int i=0;i
      
       key){24                     a[tail]=a[head];//head为坑了25                     break;26                 }27                 head++;28             }29         }30         a[tail]=key;//用key填最后重合的坑31         return tail;32     }33 void divide(int *point ,int tail,int head){34     35     int p;36     if(tail>head){37         p=adjust(point,head,tail);38         divide(point,p-1,head);39         divide(point,tail,p+1);40     }41 }42 int main(int argc, char* argv[])43 {44     int n;45     while(scanf("%d",&n)!=EOF){
    //input n digits46         FOR(n){47             scanf("%d",A+i);48         }49         divide(A,n-1,0);50         FOR(n){51             printf("%d",A[i]);52         }53         printf("\n");54     55     }56     57     return 0;58 }