首页 > 代码库 > 第七章 快速排序
第七章 快速排序
快速排序最坏情况下时间复杂度是O(n*n),但是它平均时间复杂度是O(N*logn),并且常数因子很小,可实现就地排序,所以被作为内排序的常用排序方法.
#include <iostream> using namespace std; void swap(int &i,int &j) { int temp=i; i=j; j=temp; } int partition(int *vector, int low, int high) { int pivotpos=low; int pivot=vector[low]; for(int i=pivotpos+1;i<=high;i++) { if (vector[i]<pivot) { pivotpos++; if(i!=pivotpos) { swap(vector[i],vector[pivotpos]); } } } vector[low]=vector[pivotpos]; vector[pivotpos]=pivot; return pivotpos; } void quickSort(int *vector,int low,int high) { if(low<high) { int pivotpos=partition(vector,low,high); quickSort(vector, low, pivotpos-1); quickSort(vector, pivotpos+1, high); } } int main(int argc, const char * argv[]) { int A[]={100,11,43,65}; //int A[]={56,3,5,68,100,32}; //int A[]={68,100,32}; quickSort(A, 0, sizeof(A)/sizeof(int)-1); for(int i=0;i<sizeof(A)/sizeof(int);i++) { cout<<A[i]<<" "; } cout <<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。