首页 > 代码库 > 夯实基础——快速排序
夯实基础——快速排序
逻辑结构:递归栈
物理结构:数组
快速排序分析:
最优时间复杂度:O(nlog2n)在乱序情况下
最坏时间复杂度:O(n^2) 在顺序情况下
平均时间复杂度:O(nlog2n)
空间复杂度:O(n)
稳定性:不稳定
快速排序主要有两个函数:
1 一次划归 int partition(int a[],int low,int high);
2 递归快速排序 void QuickSort(int a[],int low,int high);
3 非递归快速排序 void NonQuickSort(int *a,int low,int high);(用于解决数据量过大所产生的栈溢出)
//一次划归,pivot左端都比pivot小,pivot右端都比pivot大 //返回划归后pivot的位置 int partition(int a[],int low,int high) { int pivot=a[low]; while(low<high) { while(low<high&&a[high]>=pivot) --high; a[low]=a[high]; while(low<high&&a[low]<=pivot) ++low; a[high]=a[low]; } a[low]=pivot; return low; }
//递归快速排序 void QuickSort(int a[],int low,int high) { int pivot; if(low<high) { pivot=partition(a,low,high); QuickSort(a,low,pivot-1); QuickSort(a,pivot+1,high); } }
//非递归快速排序 void NonQuickSort(int *a,int low,int high) { int l,h,pivot; if(low>=high) return ; int *s=(int *)malloc(sizeof(int)*(high-low+1)); int p=0; pivot=partition(a,low,high); if(low<pivot-1) { s[p++]=low; s[p++]=pivot-1; } if(pivot+1<high) { s[p++]=pivot+1; s[p++]=high; } while(p>0) { h=s[--p];//相反顺序取出,后放进去的先取 l=s[--p];//先放进去的后取 pivot=partition(a,l,h); if(l<pivot-1) { s[p++]=l; s[p++]=pivot-1; } if(pivot+1<h) { s[p++]=pivot+1; s[p++]=h; } } free(s); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。