快速排序总体思想：先找到一个枢轴，让他作为分水岭。通过一趟排序将待排序的记录分割成独立的两部分，前面一部分都比枢轴小，后面一部分来源gaodaimacom搞#代%码网逗比枢轴大，然后又分别对这两部分记录继续进行递归的排序，达到整个序列有序的目的。
说一说快速排序
快速排序，实际中最常用的一种排序算法，速度快，效率高，在N*logN的同等级算法中效率名列前茅。・
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。
将数列变成上述形式，这一步很关键，做好这一步，才能对主元左右的部分进行递归调用。以下是实现这一部分的代码：
int partition_sort(int arr[],int l,int r)//l是数组最左边，r为最右边 { int j=l;//设计标记 int t=arr[l];//设置主元 for(int i=l+1;i<=r;i++) { if(arr[i]<t){ swap(arr[j+1],arr[i]); j++; } } swap(arr[l],arr[j]); return j; }
上述代码中，我把最左边的元素当作主元，这样的代码对大多数排序都很高效，但是不排除个别情况（当数组近乎有序或者当数组内有大量重复元素），这时，我们的排序算法相比于归并排序显得并不是那么高效，这和我们的排序算法原理密不可分，细细分析，当数组近乎有序时，我们的快速排序竟然退化到了O（n^2)级别，这显然是非常不高效的。
要想实现上述不足的优化，我们可以将主元随机选择，或者采用其他方式的快速排序（双路快速排序，三路快速排序），本篇内容仅作为学习快排的基本思想和基本实现，不深入涉及，有兴趣的读者可查阅资料了解。
下面是全部的实现代码：
#include #include using namespace std; //实现函数，用于partition的递归 int partition_sort(int arr[],int l,int r)//l是数组最左边，r为最右边 { int j=l;//设计标记 int t=arr[l];//设置主元 for(int i=l+1;i<=r;i++) { if(arr[i]=r)return ; int p=partition_sort(arr,l,r); partition(arr,l,p-1); partition(arr,p+1,r); } int main() { int a[5]; for(int i=0;i>a[i]; } partition(a,0,4); for(int i=0;i<5;i++) { cout<以上就是c++快速排序详解的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：c++快速排序详解
转载请注明原文链接：c++快速排序详解
