解题思路:
快速排序最关键的一点就是将整个序列分解:(~~~)a[i] (~~~)
其中a[i]为序列中任意一项,一般默认为序列第一项,书上把这一项叫做枢轴或者支点。
假设我们已经有了这样一个partition函数能够做上述这件事,那么接下来我们显然就可以用递归了,因为原序列已经分解成两个小序列了,接下来可以对小序列进行同样操作,直到最后序列变成单个值。
所以最关键就是如何实现partition函数。
题目已经给了代码,那么我主要说一下关键点帮助不太懂的快速理解:这个函数中所进行的操作的原则是始终要确保high右边的值(不包括high所指的)不小于支点值,low左边值(不包括low所指的)不大于支点值。这样在high移动过程中假如碰到了第一个小于支点值得项x,把该项放置到low所指的位置,然后low+1,其结果就是将x移动到了low左边,然后再从low那边做类似的事,直到完成任务。
注意事项:
参考代码:
#include<iostream> using namespace std; void quick_sort(int a[],int,int); int partition(int a[],int low,int high); int main() { int n; cin>>n; int a[n+1];//保留a[0]作监视哨,很关键。递归时可以多次利用该监视哨 for(int i=1;i<=n;i++) cin>>a[i]; quick_sort(a,1,n); for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; return 0; } void quick_sort(int a[],int low,int high) { if(low<high) { int pivot=partition(a,low,high); quick_sort(a,low,pivot-1); quick_sort(a,pivot+1,high); } } int partition(int a[],int low,int high) { a[0]=a[low];//将支点保存在监视哨中 while(low<high) { while(low<high&&a[high]>=a[0]) high--; a[low]=a[high]; while(low<high&&a[low]<=a[0]) low++; a[high]=a[low]; } a[low]=a[0]; return low; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题10.5 (C语言代码)浏览:552 |
C语言程序设计教程(第三版)课后习题6.10 (C语言代码)浏览:880 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:449 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:937 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:635 |
三角形 (C++代码)递推浏览:760 |
数组与指针的问题浏览:718 |
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:686 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:643 |
分解质因数 (C++代码)浏览:1482 |