快速排序算法
浏览数：24 /
时间：2015年06月08日
关于递归调用的应用——快速排序
快速排序的思路如下：
- 从需要排序的数据中，找到一个适当的基准值（pivot）。
- 将需要排序的数据按照小于pivot和大于pivot进行分类。
- 对分类后的两类数据各自再次进行上述的1和2的处理。
如果排列对象是数组，上边第二个步骤就麻烦点。下边是在不使用打的临时内存区域的情况下，对数组进行分类
的思路（默认为升序排序）：
- 从左向右，检索比pivot大的数据。
- 从右向左，检索比pivot小的数据。
- 如果两个方向都能检索到数据，将找到的数据交换。
- 重复进行1~3的操作，直到从左开始检索的下标和从右开始检索的下标发送冲突为止。
代码清单
-
#define SWAP(a,b){int temp; temp=a; a=b; b=temp;} void quick_sort_sub(int*data,int left,int right) { int left_index=left; int right_index=right; int pivot=data[(left+right)/2]; while(left_index<=right_index) { for(;data[left_index]<pivot;left_index++) ; for(;data[right_index]<pivot;right_index++) ; if(left_index<=right_index) { SWAP(data[left_index],data[right_index]); left_index++; right_index--; } } if(right_index>left) { quick_sort_sub(data,left,right_index); } if(left_index<right) { quick_sort_sub(data,left_index,right); } } void quick_sort(int*data,int data_size) { quick_sort_sub(data,0,data_size-1); }
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
