快速排序的思路：
假如对数组（arr[]）进行排序，那么定义一个基准（datum）并把数组第一个数据赋给datum，定义两个下标（low 和 high）分别记录数组第一个数据下标和数据最后一个数据下标。首先，从数组arr[high]往前遍历，如果arr[high]中的数据比基准datum中的大，那么继续往前遍历(arr[high--])找到第一个数据比基准datum小的位置，并把arr[high]中的数据赋给arr[low]。然后从前面往后遍历（arr[low]）找到第一个比基准datum大的数据，并把arr[low]中的数据赋给arr[high]。如果low 还是小于 high 那么继续上边的操作直至low < high。最后把datum中的值赋给arr[low]。此时，完成的是一趟操作。形成了一基准为中心左边是小于基准的，右边是大于基准。这时基准已经的位置已经不会改变了，再对左边和右边分别进行上面操作的内容。
如下图所示：一趟排序的图解
1.
2.
3.
4.
5.
6.
进行一趟排序的代码：
int Partition(int *arr,int low,int high)//O(n),O(1){if(arr == NULL || low < 0 || low > high){return -1;}int datum = arr[low];while(low < high){while((low<high) && arr[high]>=datum)high--;arr[low] = arr[high];while((low<high) && arr[low]<=datum)low++;arr[high] = arr[low];}arr[low] = datum;return low;}
进行递归的函数：
static void Quick(int *arr,int start,int end){if(arr == NULL || start < 0 || start > end){return -1;}int par = Partition(arr,start,end);if(start < par-1){Quick(arr,start,par-1);}if(par < end-1){Quick(arr,par+1,end);}}void QuickSort(int *arr,int len){Quick(arr,0,len-1);}
完整代码如下：
#include<stdio.h>#include<stdlib.h>int Partition(int *arr,int low,int high){if(arr == NULL || low < 0 || low > high){return -1;}int datum = arr[low];while(low < high){while((low<high) && arr[high]>=datum)high--;arr[low] = arr[high];while((low<high) && arr[low]<=datum)low++;arr[high] = arr[low];}arr[low] = datum;return low;}static void Quick(int *arr,int start,int end){int par = Partition(arr,start,end);if(start < par-1){Quick(arr,start,par-1);}if(par < end-1){Quick(arr,par+1,end);}}void QuickSort(int *arr,int len){Quick(arr,0,len-1);}void Show(int *arr,int len){for(int i=0;i<len;i++){printf("%d ",arr[i]);}printf("\n");}int main(){int arr[]={5,0,3,8,89,45,66,12,35};QuickSort(arr,sizeof(arr)/sizeof(arr[0]));Show(arr,sizeof(arr)/sizeof(arr[0]));return 0;}
