快速排序（C语言实现）

快速排序（C语言实现）

1.起因
今天在acm刷题的时候，之前的排序算法一直都是冒泡，可能九度OJ的难度题考察的都是快速排序，导致我都是死在time limited上，因此我下决心要学习一下快速排序，心得跟大家进行分享！

2.算法思想
快速排序采用了一种分治策略，我感觉它就是归并排序的优化，学术上称之为分治法（Divide-and-ConquerMethod）
(1)分治的基本思想：
将原问题分解成若干个规模更小但是结构跟原问题相似的子问题。递归的解决这些子问题，然后将这些子问题的解喝并为原问题的解
(2)快速排序的思想：
设当前需要排序的数组为int A[low..high]
分解：
在A[]中任选一个记录作为基准（pivot），以pivot为基准将数组A划分为两个小的数组A[low..pivot-1]和A[pivot+1..high],并使左边的数组元素均小于等于pivot，右边数组元素均大于等于piovt。此时，pivot处于正确的位置上，它不需要再参加后续的排序
求解：
递归的调用快速排序，对A[low..pivot-1]和A[pivot+1..high]进行快速排序
组合：
跟归并排序不同，因为每次调用快速排序，左右两个数组均已有序，因此对于快速排序来说，组合是一个空操作

3.快速排序程序实现
主流程：

/**
 * Description:快速排序主流程
 */ 
void quicksort(int *A, int p, int r) 
{ 
    int pivot; 
 
    if( p < r) 
    { 
        pivot = partition(A, p, r); 
        quicksort(A, p, pivot - 1); 
        quicksort(A, pivot+1, r); 
    } 
} 

注意：为排序整个数组，只需要在main函数中调用一个quicksort(A,begin,end)即可完成对数组的排序。