用快速排序法(C++)排序 从小到大排,最好能讲一下原理,谢谢啦

发布网友 发布时间：2022-04-23 12:40

我来回答

共1个回答

热心网友 时间：2023-06-28 06:38

#include <iostream>
#include <ctime>
using namespace std;

void swap(int& a,int& b)
{
int c;
c=a;
a=b;
b=c;
}

void sort(int* a, int n)//快排函数,从小到大
{
if(n<=1) return;
if(n==2){
if(a[1]<a[0])
swap(a[1],a[0]);
return;
}
swap(a[0],a[n/2]);
int t = *a;
int* L=a+1;//从左向右走，遇到不小于分界值的停下
int* R=a+n-1;//从右向左走，遇到小于分界值的停下
while(L<R){
while(L<R&&*L<t) ++L;
while(a<R&&*R>=t) --R;
if(L<R) swap(*L,*R);
}
swap(*a,*R);
sort(a,R-a);
sort(R+1,n-(R-a)-1);
}

void show(int a[], int n)//显示函数
{
for(int i=0; i<n; i++)
cout << a[i] << ' ';
cout << endl;
}

int main()//主函数
{
srand(time(NULL));//随机数种子
const int N = 102400;
int a[N];
for(int i=0; i<N; i++)
a[i] = N-i;
show(a, 10);
clock_t t1 = clock();//测试本次排序所耗时间
sort(a, N);
clock_t t2 = clock();
show(a, 10);
cout << "time:" << double(t2-t1)/CLOCKS_PER_SEC << endl;
}
测试过了，102400个数倒过来才花了0.031秒，相当可观。很明显，快排采用的是递归的思想，折半来进行，因此，递归的使用有时能产生神奇的效果！祝你好运！