首页 > 代码库 > 快速排序(递归与分治的思想)
快速排序(递归与分治的思想)
快排具有递归和分治的思想,实现步骤如下。
第一步:对数组A中的第一个元素x执行操作,使得数组变成新的数组B,B中C段表示小于x的元素,D段表示大于x的元素
第二步:把C段,D段,当成2个独立的数组,然后对这2个数组执行类似于第一步中A的操作
第三步:这样B和D数组又同样被分成了三部分,依次类推反复执行相同的操作。
代码:
#include<iostream> using namespace std; void swap(int &a,int &b) { int c; c=a; a=b; b=c; } //返回分割点的位置i int split(int *A,int low,int high) { int i,j,a; i=low; a=A[low]; for(j=low+1;j<=high;j++) { if(a>=A[j]) { i++; if(i!=j) { swap(A[i],A[j]); } } } swap(A[low],A[i]); return i; } //使用分治的思想调用递归 void quick_sort(int *A,int low,int high) { if(low<high) { int mid; mid=split(A,low,high); quick_sort(A,low,mid-1); quick_sort(A,mid+1,high); } } void main() { int a[4]={22,33,1,28}; quick_sort(a,0,3); for(int i=0;i<4;i++) cout<<a[i]<<endl; system("pause"); }
第一步:先让i指向第一个元素9,j指向第2个元素3,如果j的元素比9小,j往前走一步,i也往前走一步
第二步:如果j指向的数,比如图中的21比第一个元素9要大,那么i停住,j继续往前面走
第三步:j一直走到找到一个元素,它的值比9小,此时j停住,i往前走一步,然后i与j所指向的值互换
第四步:互换后如果j后没有元素,则停住,否则重复第1到第3步。
第四步:把i的值与第一个元素9互相换
快速排序时间复杂度分析:
最坏情况下是,元素是按照递增或者递减排序好了的,此时操作的时间为O(n2)
平均情况下是,O(nlogn)
因此,它是不稳定的排序
快速排序(递归与分治的思想)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。