c++快速排序详解

~

　　 基本思想： 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分所有数据要小，然后再按此方法对这两部分数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　将数列变成上述形式，这一步很关键，做好这一步，才能对主元左右的部分进行递归调用。以下是实现这一部分的代码：

　　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 <iostream>

　　#include <math.h>

　　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]<t){

　　swap(arr[j+1],arr[i]);

　　j++;

　　}

　　}

　　swap(arr[l],arr[j]);

　　return j;

　　}

　　//实现递归的调用函数

　　void partition(int arr[],int l,int r)

　　{

　　if(l>=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<5;i++)

　　{

　　cin>>a[i];

　　}

　　partition(a,0,4);

　　for(int i=0;i<5;i++)

　　{

　　cout<<a[i]<<" ";

　　}

　　return 0;

　　}

---

南山区13713705582： C++中的快速排序 - ？
晋栋珈力： 快速排序实际上就是分治之排序实际上是将复杂排序划分为多个子排序,对不同的子排序利用不同的算法以提高效率.数量大的采用二分排序,如果雷同元素多,可能会导致二分区间划不出来,则采用堆排序.前两种都是利用堆栈排序,开销还是...

南山区13713705582： 用快速排序法(C++)排序 从小到大排,最好能讲一下原理,谢谢啦 - ？
晋栋珈力： #include using namespace std;void swap(int& a,int& b) {int c;c=a;a=b;b=c; }void sort(int* a, int n)//快排函数,从小到大 {if(n<=1) return;if(n==2){if(a[1] swap(a[1],a[0]);return;}swap(a[0],a[n/2]);int t = *a;int* L=a+1;//从左向右走,遇到...

南山区13713705582： C++快速排序的算法 - ？
晋栋珈力： 从你要排序的数组中选取一个位置作为分界线,比如是中间的那个位置,现在你遍历这个数组,和你选择的这个数比较,如果比这个数大就放大他右边,小就放到左边,现在经过这次排列,整体来说肯定还不是有序的,但是可以肯定的是,你选择的那个分界线左边的任何一个数肯定比右边的小,也就是说只看左右他是有序的,但是左边的哪个区域和右边的那个区域里面还是无序的,接下来的任务就是排列左边和右边,简单地,根据上面的方法选择分界线,递归做,到什么时候结束呢,如果最终你发现一个区域里只有一个数了,那么肯定不需要排序了,所以就倒头了.希望你能理解.

南山区13713705582： c++ 快排的思想详细 - ？
晋栋珈力： 快速排序:快速排序的基本原理是划分.通过反复划分,将数组分解成一个个划分段,当每个划分段长度都不超过1时,数组排序完毕.开始时只有一个划分段,就是数组本身.下面介绍划分方法和实现步骤 快速排序划分方法:用一对下标表示...

南山区13713705582： c++快速排序法 - ？
晋栋珈力： int qpass(RecordYype r[],int left,int right)/*对记录数组r中的r[left]至r[right]部分进行一趟排序,并得到枢轴的位置,使得排序后的结果满足期之后(前)的记录的关键字均不小于(大于)枢轴记录*/ { x=r[left]; low=left; high=right; while(low<high) { ...

南山区13713705582： C++怎样实现数的排序 - ？
晋栋珈力： 把数存在数组中,然后把小的放在前面,大的放在后面. 那么就有很多种方法了. 1找小的放前面,第二个以后和第一个比小了就交换位置.也可以从最后一个开始找大的放后面. 2两头同时进行,鸡尾酒排序. 3快速排序,算法中有的. 其他排序要涉及一些稍微男的数据结构..

南山区13713705582： 快速排序c++代码 - ？
晋栋珈力： 随机生成N个整数显示,经过快速排序后输出排序后的结果.程序代码如下所示,仅供参考:(已通过编译运行,正确无误!)# include ＂stdio.h＂# include ＂time.h＂# include ＂stdlib.h＂# define N 10 int partition(int a[],int low,int high){//快速...

南山区13713705582： C++ 快速排序 - ？
晋栋珈力： #include <iostream>#include <algorithm> using namespace std; void print(int*a, int n){ for(int i=0; i<n; i++){ cout << a[i] << ' '; } cout << endl; } void sort(int*a, int n){ for(int i=0; i<n-1; i++){ int k = i;//最小值的下标 for(int j=i; j<n; j++){ if(a[j]<a[k]) k = j; } ...

南山区13713705582： c++中,详细讲解一下选择排序法. - ？
晋栋珈力： 这是直接选择排序 void SelectSort(DataType a[],int n) { int i,j,small; DataType temp; for( i = 0; i < n - 1;i ++) { small = i; for (j = i+1; j < n; j++ ) if( a[j] < a[small] ) small = j; if ( small != i) { temp = a[i]; a[i] = a[ small]; a[small] = temp; } } } 还有堆排序也是选择排序,如果想要的话再来问,并加分,还可以给你测试主程序

南山区13713705582： 快速排序c++代码 - ？
晋栋珈力： #include ＂stdio.h＂void QuickSort(int e[], int first, int end){ int i=first,j=end,temp=e[first]; while(i<...