网站搜索优化找哪家,昌吉建设局网站,wordpress 自动换行,semester怎么读A. DS内排—直插排序
题目描述
给定一组数据#xff0c;使用直插排序完成数据的升序排序。
--程序要求--
若使用C只能include一个头文件iostream#xff1b;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件#xff0c;不看代码#xff0c;作0分…
A. DS内排—直插排序
题目描述
给定一组数据使用直插排序完成数据的升序排序。
--程序要求--
若使用C只能include一个头文件iostream若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件不看代码作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
数据个数nn个数据
输出
直插排序的每一趟排序结果
样例查看模式
正常显示查看格式
输入样例1
7 34 23 677 2 1 453 3
输出样例1
23 34 677 2 1 453 3\n 23 34 677 2 1 453 3\n 2 23 34 677 1 453 3\n 1 2 23 34 677 453 3\n 1 2 23 34 453 677 3\n 1 2 3 23 34 453 677\n
AC代码
#includeiostream
using namespace std;
const int N 1e5;
int a[N];
int n;
void insert_sort()
{for (int i 1; i n; i){int t a[i];int j;for (j i - 1; j 0; j--){if (a[j] t){a[j 1] a[j];}else break;}a[j1] t;for (j 0; j n; j){cout a[j];if (j ! n - 1)cout ;else cout endl;}}
}
int main()
{cin n;for (int i 0; i n; i){cin a[i];}insert_sort();return 0;
}
B. DS排序--希尔排序
题目描述
给出一个数据序列使用希尔排序算法进行降序排序。
间隔gap使用序列长度循环除2直到1
输入
第一行输入t表示有t个测试示例 第二行输入n表示第一个示例有n个数据(n1) 第三行输入n个数据都是正整数数据之间用空格隔开 以此类推
输出
对每组测试数据输出每趟排序结果。不同组测试数据间用空行分隔。
样例查看模式
正常显示查看格式
输入样例1
2\n 6\n 111 22 6 444 333 55\n 8\n 77 555 33 1 444 77 666 2222\n
输出样例1
444 333 55 111 22 6\n 444 333 111 55 22 6\n \n 444 555 666 2222 77 77 33 1\n 666 2222 444 555 77 77 33 1\n 2222 666 555 444 77 77 33 1\n
AC代码
#includeiostream
using namespace std;
int n;
const int N 1e5;
int a[N];
void shell_sort(int gap)
{for (int i gap; i n; i )//每一个元素{int t a[i];int j;for (j i - gap; j 0; j - gap){if (a[j] t){a[j gap] a[j];}else break;}a[j gap] t;}
}
int main()
{int t;cin t;while (t--){cin n;for (int i 0; i n; i){cin a[i];}int gap n;while (gap ! 1){gap / 2;shell_sort(gap);for (int j 0; j n; j){cout a[j];if (j ! n - 1)cout ;else cout endl;}}if (t)cout endl;}return 0;
}
C. 冒泡排序
题目描述
给定一个包含从0到n-1各一次的数组若使用冒泡排序将其排为升序问其中需要进行多少次交换
输入
测试数据有多组
每组由两行组成第一行包含正整数nn 5000; 下一行包含从0到n-1的n个整数的序列。
输出
对于每组测试数据
输出交换次数
样例查看模式
正常显示查看格式
输入样例1
10\n 1 3 6 9 0 8 5 7 4 2
输出样例1
22
AC代码
#includeiostream
using namespace std;
int n;
const int N 1e5;
int a[N];
void pop_sort()
{int ans 0;for (int i 0; i n - 1; i){for (int j i 1; j n; j){if (a[j] a[i])swap(a[j], a[i]),ans;}}cout ans endl;
}
int main()
{while (cinn){for (int i 0; i n; i){cin a[i];}pop_sort();}return 0;
}
D. DS排序--快速排序
题目描述
给出一个数据序列使用快速排序算法进行从小到大的排序
--程序要求--
若使用C只能include一个头文件iostream若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件不看代码作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
第一行输入t表示有t个测试示例 第二行输入n表示第一个示例有n个数据 第三行输入n个数据都是正整数数据之间用空格隔开 以此类推
输出
每组测试数据输出每趟快排的结果即每次排好一个数字结果长度为1的子序列不用排不用输出。不同测试数据间用空行分隔。
样例查看模式
正常显示查看格式
输入样例1
2\n 6\n 111 22 6 444 333 55\n 8\n 77 555 33 1 444 77 666 2222\n
输出样例1
55 22 6 111 333 444\n 6 22 55 111 333 444\n 6 22 55 111 333 444\n 6 22 55 111 333 444\n \n 1 33 77 555 444 77 666 2222\n 1 33 77 555 444 77 666 2222\n 1 33 77 77 444 555 666 2222\n 1 33 77 77 444 555 666 2222\n 1 33 77 77 444 555 666 2222\n
AC代码
#includeiostream
using namespace std;
int n;
const int N 1e5;
int a[N];
void quick_sort(int low, int high)
{int i low, j high;if (i j)return;int t a[low];while (i ! j){while (a[j] t i j)j--;if (i j)break;a[i] a[j];i;while (a[i] t i j)i;if (i j){swap(a[i], a[j]);}}a[i] t;//重合for (int k 1; k n; k){cout a[k];if (k ! n)cout ;else cout endl;}quick_sort(low, i - 1);quick_sort(i 1, high);
}
int main()
{int t;cin t;while (t--){cin n;for (int i 1; i n; i){cin a[i];}quick_sort(1, n);if(t)coutendl;}return 0;
} E. 大数据量的冒泡排序 (计次数)
题目描述
给定一个包含从0到n-1各一次的数组若使用冒泡排序将其排为升序问其中需要进行多少次交换
输入
测试数据有多组
每组由两行组成第一行包含正整数nn 5000; 下一行包含从0到n-1的n个整数的序列。
输出
对于每组测试数据输出一行输出交换总次数
样例查看模式
正常显示查看格式
输入样例1
10\n 1 3 6 9 0 8 5 7 4 2\n
输出样例1
22\n
AC代码
#includeiostream
using namespace std;
int n;
const int N 1e5;
int a[N];
void pop_sort()
{int ans 0;for (int i 0; i n - 1; i){for (int j i 1; j n; j){if (a[j] a[i])swap(a[j], a[i]),ans;}}cout ans endl;
}
int main()
{while (cinn){for (int i 0; i n; i){cin a[i];}pop_sort();}return 0;
}
F. 与零交换
题目描述
将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难这里加一点难度要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 }我们可以通过下列操作完成排序
Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }Swap(0, 4) ⟹ { 0, 1, 2, 3, 4 }
本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。
输入
输入在第一行给出正整数 N (≤105)随后一行给出{ 0, 1, 2, ..., N-1 } 的一个排列。数字间以空格分隔。
输出
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。
样例查看模式
正常显示查看格式
输入样例1
10\n 3 5 7 2 6 4 9 0 8 1
输出样例1
9
AC代码
#includeiostream
using namespace std;
int n;
const int N 1e5;
int a[N];
bool st[N];
int ans;
int main()
{cin n;for (int i 0; i n; i)cin a[i];for (int i 0; i n; i){if (!st[i] a[i] ! i){bool flag 0;int idx i;int cnt 0;while (!st[idx]){if (a[idx] 0)flag 1;st[idx] 1;idx a[idx];cnt;}if (flag)ans (cnt - 1);else ans (cnt 1);}else st[i] 1;}cout ans endl;return 0;
}
