首页 > 代码库 > 快速排序
快速排序
快速排序算法
快速排序一直是各大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 }
快速排序