C++ qsort函数详解快速排序

小咪咪 2024-02-18 22:24 9阅读 0赞

qsort排序 是快速排序，时间复杂度是nlog2（n）

用起来挺方便的。

控制排序方向的cmp函数，默认是从小到大，return返回语句：若为1，则按照参数列表，第一个参数排在第二个参数之后，若为-1，则相反，若为0，二数相等，无所谓。

![70][]

![70 1][]

![70 2][]

![70 3][]

![70 4][]

/\*  
C++ qsort函数 练习3：对结构体排序  
anthor：nice1998  
time：2018.8.5  
\*/  
\#include<iostream>  
\#include<string.h>  
\#include<algorithm>  
\#include<stdlib.h>  
using namespace std;  
struct node  
\{  
int data;  
int d;  
\}a\[100\];  
int cmp(const void \*a,const void \*b)  
\{  
node \*k=(node \*)a;  
node \*j=(node \*)b; // 这个地方 必须先把a和b进行类型转换，不能在return里进行类型转换，否则报错  
return k->data-j->data;// 如果return的结果大于等于1，那么，按照参数列表，a将会被排在b后面，  
\}  
int main()  
\{  
int n,i,j,k;  
  
cin>>n;  
  
for(i=0;i<n;i++)  
\{  
  
scanf("%d",&a\[i\].data);  
a\[i\].d=i+1;  
  
\}  
  
qsort(a,n,sizeof(a\[0\]),cmp);  
for(i=0;i<n;i++)  
printf("%d %d\\n",a\[i\].d,a\[i\].data);  
return 0;  
\}

/\*  
C++ qsort函数 练习3：对结构体排序  
anthor：nice1998  
time：2018.8.5  
\*/  
\#include<iostream>  
\#include<string.h>  
\#include<algorithm>  
\#include<stdlib.h>  
using namespace std;  
struct node  
\{  
int data;  
int d;  
\}a\[100\];  
int cmp(const void \*a,const void \*b)  
\{  
node \*k=(node \*)a;  
node \*j=(node \*)b; // 这个地方 必须先把a和b进行类型转换，不能在return里进行类型转换，否则报错  
if(k->data==j->data)  
return k->d-j->d;  
else  
return k->data-j->data;// 如果return的结果大于等于1，那么，按照参数列表，a将会被排在b后面，  
\}  
int main()  
\{  
int n,i,j,k;  
  
cin>>n;  
  
for(i=0;i<n;i++)  
\{  
  
scanf("%d",&a\[i\].data);  
a\[i\].d=i+1;  
  
\}  
  
qsort(a,n,sizeof(a\[0\]),cmp);  
for(i=0;i<n;i++)  
printf("%d %d\\n",a\[i\].d,a\[i\].data);  
return 0;  
\}

[70]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/1e450f97602344b3baba23d06b0364d0.png
[70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/09489a2f476743019a596c67d0388c12.png
[70 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/2781d6748c144fe587df5c6e9348f6ee.png
[70 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/5b8d37cd839b44f2a184cc0979c3a52f.png
[70 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/29/0e7c0b622e8c4762853ba34c4a3393d0.png