快速算法达成----挖坑填数
发布时间：2021-11-20 13:05:35 所属栏目：PHP教程 来源：互联网
导读：1、选定一个数作为基数 2、将大于这个的基数的数全放在右边，小于这个基数的数全部放在左边 3、对左右区间中的数重复1、2步骤，直到区间中只有一个数。 这样描述可能有一点难以理解，我们可以用挖坑+填数的方式来很好的理解 1、对于数组a，实现l到r的排序，
|
1、选定一个数作为基数 2、将大于这个的基数的数全放在右边，小于这个基数的数全部放在左边 3、对左右区间中的数重复1、2步骤，直到区间中只有一个数。 这样描述可能有一点难以理解，我们可以用挖坑+填数的方式来很好的理解 1、对于数组a，实现l到r的排序，首先挖坑key=a[l]，令i=l，j=r，此时形成第一个坑a[i] 2、j--直到a[j]小于key的地方，令a[i]=a[j]，此时a[j]形成一个新的坑，i++ 3、i++直到a[i]大于key的地方，令a[j]=a[i]，填上坑a[j],此时a[i]形成新的坑，j-- 4、再重复执行2，3二步，直到i==j，将key填入a[i]中 进经过上面的一番讲解，突然一下子变得清晰明了了。 代码实现就很简单了。 //一次划分 int partion(int a[],int left,int right) { //先将第一个数设置成一个坑a[left] int i=left，j=right; int key=a[left]; while(i<j) { //从最右端开始寻找小于key的数，如果大于，则j-- while(i<j&&a[j]>=key) j--; //如找到且i<j,将a[i]这个坑填上，形成一个新坑a[j]，i++ if(i<j) { a[i]=a[j]; i++; } //从左边的i开始找，如果小于key，i++ while(i<j&&a[i]<key) i++; //如找到，并且i<j，将a[j]这个坑填上，形成新坑a[i],j-- if(i<j) { a[j]=a[i]; j--; } } //将key填回坑a[i] a[i]=key; //返回轴值 return i; } void QuickSort(int a[],int left,int right) { //当left<right时 if(left<right) { //形成轴值 int mid=partion(a,left,right); //递归左半部分 QuickSort(a,left,mid-1); //递归右半部分 QuickSort(a,mid+1,right); } } int main() { int a[]={1,3,2,5,2,4}; QuickSort(a,0,5); for(int i=0;i<6;i++) { cout<<a[i]<<" "; } return 0; }  （编辑：应用网_丽江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
浙公网安备 33038102330468号