快速排序

快速排序算法

快速排序一直是各大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所在位置分成两个部分，分别对这两个部分再先填坑，然后分治。显然是一个迭代的过程。不多赘述。

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

// try.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#define FOR(n) for (int i=0;i<n;i++)
//快速排序
int A[100];
int adjust(int *a,int head,int tail){
        int key;
        key=a[head];//head 为坑了
        while(head<tail)//先让tail--找，找到小于key的，用该找到的来填坑。填完坑后tail指向新形成的坑。同理head
        {
            while (tail!=head)
            {
                if(a[tail]<=key){
                    a[head]=a[tail];//tail为坑了
                    break;
                }
                tail--;
            }
            while (tail!=head)
            {
                if(a[head]>key){
                    a[tail]=a[head];//head为坑了
                    break;
                }
                head++;
            }
        }
        a[tail]=key;//用key填最后重合的坑
        return tail;
    }
void divide(int *point ,int tail,int head){
    
    int p;
    if(tail>head){
        p=adjust(point,head,tail);
        divide(point,p-1,head);
        divide(point,tail,p+1);
    }
}
int main(int argc, char* argv[])
{
    int n;
    while(scanf("%d",&n)!=EOF){//input n digits
        FOR(n){
            scanf("%d",A+i);
        }
        divide(A,n-1,0);
        FOR(n){
            printf("%d",A[i]);
        }
        printf("
");
    
    }
    
    return 0;
}