快速排序
快速排序是先找到一个基准数字(可以随机),任何将不大于该数的数字左移,不小于该数的数字右移,再递归调用自己。
#include<iostream> #include <cstdlib> #include<time.h> using namespace std; int input[50]; int n; //产生随机数 int random(int start,int end) { srand(time(NULL));//以当前系统时间产生随机数种子 return start+rand()%((end-start)); } //交换数字 void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; } //找到划分数字下标 int findPartition(int data[],int start,int end) { int index=random(start,end); swap(&data[index],&data[end]); int mid=start-1; for(int index=start;index<n;++index) { if(data[index]<data[end]) { ++mid; if(data[index]!=data[mid]) { swap(&data[index],&data[mid]); } } } ++mid; swap(&data[mid],&data[end]); return mid; }
//递归调用自己进行排序 void quickSort(int data[],int start,int end) { if(start==end||data==NULL) { return; } int index=findPartition(data,start,end); if(index>start) quickSort(data,start,index-1); if(index<end) quickSort(data,index+1,end); } int main(int argc, char const *argv[]) { char temp; while((temp=cin.get())!=‘\n‘) { if (temp>=‘0‘&&temp<=‘9‘) { input[n++]=temp-‘0‘;//数字字符与数字的转换通过加减‘0’ }else { cout<<"Invalid input"<<endl; return 0; } } quickSort(input,0,n-1); for(int i=0;i<n;++i) cout<<input[i]; return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。