快速排序算法C语言实现
在任何程序中，数组的排序都是极为重要的内容，我们需要按照业务需要对大量的数据进行排序，因此排序的速度或者说效率就显得极为重要了，因此选择一个效率较高的算法可以大大提升程序的性能。
如今的算法界，排序算法比较多，包括：冒泡排序，堆排序，选择排序，插入排序，交换排序等，而今天所说的快速排序（QuickSort）就是交换排序的一种，它具有快速，高效的特性而被经常使用，但它的时间复杂度也是级不稳定的，最好的情况下是O( nlogn )，最坏的情况下是O( n^2 )。
其排序的原理在于通过一趟排序，将待排序的记录分成独立的两部分，其中一部分的数据始终大于另一部分数据的值，然后在分别利用递归对这两部分进行排序，以达到整个序列的有序。
废话不多说，直接看C程序：
1.首先需要定义快速排序的递归式：
void QuickSort(ElemType arr[],int start,int end){if(start<end){int key=(start+end)/2;key=Sort(arr,start,end,key);QuickSort(arr,start,key-1);QuickSort(arr,key+1,end);}}
从代码中我们可以看出，首先需要确定一个关键点，这个点可以任意设置，一般设置成中间位置，然后先对序列进行一趟排序后，再利用递归对大于关键点的部分和小于关键点的部分进行排序。
2.子排序代码：
int Sort(ElemType arr[],int low,int high,int key){findmin(arr,&low,&high,&key);return key;}void findmin(ElemType arr[],int *low,int *high,int *key){if(low<high){int pos=-1;for(int i=*high;i>=*low;i--){if(arr[i]<=arr[*key]){pos=i;break;}}if(pos!=-1){*high=pos;Exchange(&arr[*high],&arr[*key]);*key=pos;int value=*high;value--;*high=value;findmax(arr,low,high,key);}}}void findmax(ElemType arr[],int *low,int *high,int *key){if(low<high){int pos=-1;for(int i=*low;i<=*high;i++){if(arr[i]>=arr[*key]){pos=i;break;}}if(pos!=-1){*low=pos;Exchange(&arr[*low],&arr[*key]);*key=pos;int value=*low;value++;*low=value;findmin(arr,low,high,key);}}}
一趟排序的算法为：
（1）设置low和high来表示序列的范围，从high开始向前寻找第一个小于关键点值的位置，然后与关键点进行交换.
（2）从low开始向后寻找第一个大于关键点值的位置，然后与关键点进行交换.
（3）.。。。。。。。。。。一直这样递归下去知道low=high
3.进行程序的测试
int main(){ElemType arr[]={11,26,2,5,158,176,2,4,6};int len=sizeof(arr)/sizeof(ElemType);print(arr,len);QuickSort(arr,0,len-1);printf("Quick Sort ....\n");print(arr,len);return 0;}
最后输出结果为：
代码Github地址：/xiaoqinzhao/QuickSort
