算法思想：快速排序时这样的一种排序，选取数组中的第一个元素arr[0]作为依据，遍历一遍数组后，使得数组中的第一个元素进入正确的位置，即在该位置左面的元素均小于等于arr[0]，在该位置右面的元素均大于等于arr[0]。然后，在对该位置左面和右面的元素分别进行快速排序，如此一来完成整个数组的排序。
算法代码：
#include <iostream> using namespace std; void swap(int &x,int &y) { x = x + y; y = x - y; x = x - y; } void quick_sort(int *arr,int s,int e) { if(s+1 < e) { int tmp = arr[s]; int i = s+1; int j = e-1; while(i < j) { while(i <= j && arr[i] <= tmp) { i++; } while(i <= j && arr[j] >= tmp) { j--; } if(i < j) { swap(arr[i],arr[j]); } } swap(arr[s],arr[i-1]); quick_sort(arr,s,i-1); quick_sort(arr,i,e); } } int main() { int arr[] = {2,1,4,3,8,7,5,6}; quick_sort(arr,0, 8); for(int i = 0 ; i < 8 ; ++i) { cout<<arr[i]<<" "; } cout<<endl; return 0; }
小结：首先还是说明快速排序时不稳定的，但是是原地排序，不需要额外的空间，时间复杂度是O(nlog n)，实际上，这种把第一个元素作为依据元素只是快速排序的一种，STL中的sort内部实现是根据排序到了不同的阶段选用不同的排序算法。当数据量大是采用 quick_sort排序，当分段递归到了数据量小于某个数值时，为避免quick_sort的递归调用带来的额外开销，就改用insert_sort 了；如果递归层次过深，还会考虑使用heap_sort 。
