数据结构实验之排序二:交换排序 (SDUT 3399)
2023-06-13 09:17:22 时间
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//int sum = 0;
int a[100004]; //题目是长整型,不过这里 int 也可以。。
int b[100005];
void qusort(int l, int r, int a[], int &sum) //这里如果不想传sum,就把sum定义成全局,如注释
{
int i = l, j = r;
int x = a[i];
if(i >= j) return ;
while(i < j)
{
while(i < j && a[j] >= x) j --;
if(a[j] != a[i]) sum ++;
a[i] = a[j];
while(i < j && a[i] <= x) i ++;
if(a[j] != a[i]) sum ++;
a[j] = a[i];
}
a[i] = x;
qusort(l,i-1,a,sum);
qusort(i+1,r,a,sum);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i = 0; i < n; i ++)
{
scanf("%d",&a[i]);
b[i] = a[i];
}
int num = 0; // 冒泡
int sum = 0; //快排
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < n - i - 1; j ++)
{
if(a[j] > a[j +1])
{
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
num ++;
}
}
}
qusort(0,n-1,b,sum);
printf("%d %d\n",num,sum);
}
return 0;
}
相关文章
- 数据结构与算法 队列_数据结构中的排序算法
- 数据结构与算法(十五):二叉排序树[通俗易懂]
- mysql 符串类型的数字排序(字符串转数字)[通俗易懂]
- TreeMap数据结构之排序二叉树
- 字典树的数据结构_数据结构快速排序
- 数据结构之快速排序
- 数据结构–链表的排序详解
- 哪些属于网页抓取算法_网页排序算法有哪些
- Go 数据结构和算法篇(六):选择排序
- Go 数据结构和算法篇(八):快速排序
- 数据结构实验之排序四:寻找大富翁(SDUT 3401)
- 数据结构实验之排序六:希尔排序 (SDUT 3403)
- 【数据结构】八大经典排序(两万字大总结)
- Redis sort 排序命令详解
- Oracle中简单查询、限定查询、数据排序SQL语句范例和详细注解
- Oracle中对数字加汉字的排序(完善)详解数据库
- Oracle数据库的排序方法详解(oracle数据库排序)
- MySQL实现数据随机获取,让数据随机排序成为可能。(mysql随机获取数据)
- Oracle数据库中实现全拼排序的实践(oracle全拼排序)
- Oracle数据库优化排序把时间变成分秒(oracle优化排序)
- php归并排序数组交集
- python算法学习之桶排序算法实例(分块排序)
- 一个PHP二维数组排序的函数分享