一、原理
核心原理就是划分，找一个哨兵元素（通常选第一个元素），然后根据哨兵元素将原序列所有比哨兵元素大的放哨兵后面，所有比哨兵小的放哨兵前面（升序排列，降序相反即可），那么，哨兵元素此时所在的位置就应该是排序之后它应该在的位置，也就是说哨兵的位置已经正确找到，只是他前后的序列可能还是无需的，对于前后序列用同样的方法，就能将所有元素的正确位置找到，实现序列排序。
二、算法复杂度
时间复杂度：最坏：O（n²）最好：O（nlogn）平均：O（nlogn）
空间复杂度：O（logn）
三、C/C++源码实现
#include<iostream> using namespace std; void KP(int data[],int begin,int end){ int left=begin; int right = end; int row = data[begin]; while(left<right){ while(data[right]>=row&&left<right) right--; data[left]=data[right]; while(data[left]<=row&&left<right) left++; data[right]=data[left]; } data[left]=row; if(begin<end){ KP(data,begin,left-1); KP(data,right+1,end); } } int main(){ int data[10]; int n; cin>>n; for(int i=0;i<n;i++) cin>>data[i]; KP(data,0,n-1); for(int i=0;i<n;i++) cout<<data[i]<<" "; }
原文：https://www.cnblogs.com/bucthuge/p/11521485.html
