快速排序算法的平均性能非常好：期望时间复杂度为O(nlgn)，而且其中的隐含的常数因子非常小，另外它具有原址排序的优点，即在内部排序，不用再新建一个数组。与归并排序一样，快速排序也是用了分治法的思想。快速排序主要思想是：将一个大数组分成两块，并且两块的中间的一个数起分割作用，数的左边均小于它，数的右边均大于它。然后将子数组再分割为两块，同样的规律......直到子数组的元素只有一个位置，于是所有的地方都已经排好序了。所以，我们可以想象，分割的终止条件是数组只有一个元素了。
分割
首先，我们实现对一个数字进行分割，并且找出这个分割数（主元，pivot）的位置。思想很简单，先假设第一个元素为分割数（主元），然后，我们设定两个移动的索引分别是left和right，left从左往右遍历，遇到比主元小的直接跳过，遇到不满足的就停下;同理，right从右往左遍历，遇到比主元大的就跳过，遇到不满足的就停下。于是，当两者都停下时，我们比较一下left与right的位置，若left在right的左边，则我们将left和right分别所指的两个元素进行互换，交换过后，再分别接着遍历，同样的规律，直到right在left的左边为止。此时，我们将pivot和right分别所指的两个数进行交换，并且返回right。那么，right的值就是分割数的索引，即主元的位置。具体代码如下：
int partition(int* A,int start,int end)
{
int left=start+1;
int right=end;
int tmp;
while(right>left) {
while(*(A+left)<*(A+start)) {
left++;
}
while(*(A+right)>*(A+start)) {
right--;
}
if(left<right) {
tmp=*(A+left);
*(A+left)=*(A+right);
*(A+right)=tmp;
}
}
tmp=*(A+right);
*(A+right)=*(A+start);
*(A+start)=tmp;
return right;
}
分治法的运用
现在假设我们已经将一个数组分为了两个部分了，中间由一个主元分割开。那么，我们接下来要做的就是继续分别对这两个子数组进行分割，寻找主元。在这个过程中，要明白主元的位置一定是固定的。因此，显然，我们的做法就是一直分割下去直到子数组只有一个元素为止，即一开始就有right=left。那么，在这个整体过程中，我们将一个大数组二分直到只有一个元素位置的步骤是logn步，然后我们找主元相当于每次确定一个元素的位置，因此共有n个元素，因此，算法复杂度为nlogn。
void quickSort(int* A,int start,int end)
{
if(start<end) {
int pivot=partition(A,start,end);
quickSort(A,start,pivot-1);
quickSort(A,pivot+1,end);
}
}
主函数
#include<stdio.h>
int main()
{
int a[7]={3,2,5,0,9,8,1};
quickSort(a,0,6);
int i;
for(i=0;i<7;i++)
printf("%d\n",a);
return 0;
}
编写Makefile
# this is a makefile
main.o:main.c quickSort.o partition.o
gcc quickSort.o partition.o main.c -o main.o
quickSort.o:quickSort.c partition.o
gcc -c quickSort.c
partition.o:partition.c
gcc -c partition.c
来源： 张下泽旺 深度学习每摘要
智造家