快排是各种排序中算法，非常重要的一种。其用到的主要思想也是分治法。

这一节主要涉及到的知识点有：1 基本快排 2.快排的直观及数学分析 3 随机化的快排及其严格的数学分析(数学分析在算法笔记中)

1 快排的基本内容

快排啊，其基本思想也是分治法。它是一种原地排序的算法，即和插入排序一样，不需要额外的空间去存储。比如归并排序就不行了，就需要额外空间去移动着来排序

快排的divide-and-conquer步骤：

1 分裂： 将数组用一个pivot x 分成两个部分，左半部分≤x,右半部分≥x

2.conquer: 递归的去处理分裂的子数组

3.合并：原地算法，直接就是合并好的

所以，快排的分割子算法就非常重要了，下面给出线性时间的分割算法

PARTITION(A, p, q) ⊳A[p. . q]

x←A[p] ⊳pivot= A[p]

i←p

for j←p+ 1 to q

do if A[j] ≤x

then i←i+1 exchange A[i] ↔A[j]

exchange A[p] ↔A[i]

return i

用语言去叙述这个过程就是，一个坐标j记录当前位，i记录分割位，当发现某个后面的数比pivot小的时候，就将分割位往后移动一位，然后交换当前分割位和当前位(因为分割位往后了一位，这个时候分割位指的一定是比pivot大的数，交换之后正好又满足分割的条件了)

下面给出一个分割的具体实例：

有了分割的代码，整个快排就比较好解决了

QUICKSORT(A, p, r) ⊳Initial call: QUICKSORT(A,1,n)

if p< r then q←PARTITION(A, p, r)

QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r)

2.快排的直观及数学分析

快排的分析，先来分析最坏情况。快排的最坏情况还是很容易出现的，输入是已经排序的，或者是逆序的都会导致最坏情况，因为选取的主元都是最大或最小值。这就引出了下面的递归式：

T(n)=T(0)+T(n-1)+Θ(n)

=T(n-1)+Θ(n)

这个递归式用递归树来分析，很容易得到复杂度T(n) = Θ(n2)

最坏情况是非常糟糕的，那么最好情况以及那些没有达到最坏情况的时候呢？

当我们很幸运，每次分割都将数组平均分成两部分，此时我们得到最好情况：

T(n) = 2T(n/2) + Θ(n) = Θ(nlogn)

当分割都是0.1:0.9的时候呢？

显然树的两边是不平衡的，右边的高度要大，事实上，高度左边是log10n 右边是log10/9 n

所以复杂度T(n): cnlog10n + O(n) ≤ T(n) ≤cnlog10/9n+ Ο(n)

所以复杂度仍是 Θ(nlgn)

3 随机化版本的快排

IDEA: Partition around a random element

其方法应该是很简单咯，就是随机选一个元素作为pivot。 主要就是证明这种方法的复杂度也是 Θ(nlgn)，证明过程很多数学推导，所以我还是将其放在算法笔记当中。

最后附上自己写的快排：

1 /////////////////////////CLRS video lec4 快排/////////////////////////////////////////////////

2 //一般情况下O(lg n)的复杂度，当输入是正序或者逆序的时候最坏情况O(n^2) /////////////////////////////////////////////////////

3

4 #include

5 #include

6 #include

7 using namespace std;

8

9 #define random(x)(rand()%x)

10

11 int findpar(int* arr,int p,int q)

12 {

13 int pivot = arr[p],temp,i,j,pos;

14 i=p;

15 for(j=p+1;j<=q;j++)

16 {

17 if(arr[j]

18 {

19 temp=arr[++i];

20 arr[i]=arr[j];

21 arr[j]=temp;

22 }

23 }

24 temp=arr[i];

25 arr[i] = pivot;

26 arr[p]=temp;

27 return i;

28 }

29 void quicksort(int* arr,int p,int q)

30 {

31 int par = findpar(arr,p,q);

32 if((par-1)>p)

33 quicksort(arr,p,par-1);

34 if((par+1)

35 quicksort(arr,par+1,q);

36 //也可以写成

37 /*

38 if(p

39 int par = findpar(arr,p,q);

40 quicksort(arr,p,par-1);

41 quicksort(arr,par+1,q);

42 }*/

43 }

44

45 int main()

46 {

47 int a[100];

48 srand((int)time(0));

49 int i,j,k;

50 for(i=0;i<100;i++)

51 {

52 a[i]=random(200);

53 }

54 quicksort(a,0,99);

55 for(i=0;i<100;i++)

56 {

57 cout<

58 }

59 cout<

60 return 0;

61 }

QuickSort