快速排序

快速排序的基本思路：

从需要排序的数据中，找到一个适当的基准值（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); }

这个程序将数组分成两部分之后，再进行递归调用。此时，在栈中分配了新的用于当前部分数组的内存区域。另外，当某部分数组的数据处理完毕，函数调用返回的时候，栈会收缩，调用前的状态恰好处于栈的最初位置。正因为如此，处理才这样不断地向右移动。