快速排序（Quick Sort）
快速排序算法是对冒泡排序的一种改进，冒泡排序一趟比较后只能使排序序列的长度减少1，而快速排序希望经过一趟扫描后使得排序序列的长度大幅度减少。它的基本思想是通过一趟排序将序列划分为两部分，其中一部分所有的数据比另一部分所有的数据都要小。然后对这两部分分别进行快速排序，整个排序是一个递归调用的过程，最终实现整个序列有序。
排序流程：
a) 设置两个变量，first、last，排序开始的时候first = 0，last = N-1；
b) 以第一个数组元素作为关键数据，赋值给key，即key = A[0]；
c)从j开始向前搜索，如果A[j]<key，则A[j]与A[i]互换；否则，j--；
d)从i开始向后搜素，如果A[i]>key，则A[i]与A[j]互换；否则，i++；
e)重复c)，d)，直至i==j。
示例代码：
1、qsort函数的用法
qsort函数是编译器函数库自带的函数，原型如下：
void qsort(void *base, int nelem, int width, int (*fcmp)(const void *,const void *)); 其中：
base：待排序数组的首地址。
nelem：待排序数组中元素的个数。
width：待排序数组中元素占用空间的大小。
fcmp：排序函数指针
int cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}
……
函数调用：
qsort(orgArray,ARRAY_SIZE, sizeof(orgArray[0]),cmp)2、自己写qsort函数
void QuickSortMethod(int arr[], int lowIndex, int highIndex)
{
int key = arr[lowIndex];
int first = lowIndex;
int last = highIndex;
if (first >= last)
{
return;
}
while(first < last)
{
while((first < last) && (arr[last] >= key))
{
last--;
}
arr[first] = arr[last];
while((first < last) && (arr[first] <= key))
{
first++;
}
arr[last] = arr[first];
}
arr[first] = key;
QuickSortMethod(arr, lowIndex, first-1);
QuickSortMethod(arr, first+1, highIndex);
}算法的时间复杂度：
最坏情况下的时间复杂度：（逆序排列）
如： 8 1 2 3 4 5 6 7
第一趟排序后：7 1 2 3 4 5 6 8，执行了8次比较操作，游标索引first = last = 7,
第二趟排序的队列为：7 1 2 3 4 5 6，需要执行7次比较操作，排序后序列为：6 1 2 3 4 5 7，游标索引first = last = 6
……
此时已经退化为冒泡排序，时间复杂度为O(n^2)
理想情况下的时间复杂度：
需要对队列中的每个元素执行一次操作，如果队列长度为n，则需要执行n次操作。
将队列划分为两部分，则需要对每个队列执行n/2次操作，共n次操作。
再将子队列分别划分为两部分，则需要对每个队列执行n/4次操作，4个小队列，共n次操作。
……
一共可以划分logn次，所以一共需要执行nlogn次操作。
快速排序算法的时间复杂度用递归的方法比较容易计算。现在还没有完全读懂，之后来完善。~~~~~~
结论：最坏情况下的时间复杂度O(n^2)，平均时间复杂度O(nlogn)
参考资料：
1、 快速排序算法——百度百科
2、qsort函数的用法——博客园
3、快速排序算法的时间复杂度分析——博客园