首页 > 代码库 > 快速排序

快速排序

快速排序算法

快速排序一直是各大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<n;i++) 6 //快速排序 7 int A[100]; 8 int adjust(int *a,int head,int tail){ 9         int key;10         key=a[head];//head 为坑了11         while(head<tail)//先让tail--找,找到小于key的,用该找到的来填坑。填完坑后tail指向新形成的坑。同理head12         {13             while (tail!=head)14             {15                 if(a[tail]<=key){16                     a[head]=a[tail];//tail为坑了17                     break;18                 }19                 tail--;20             }21             while (tail!=head)22             {23                 if(a[head]>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 }
View Code

 

快速排序