SCAU 数据结构 实验六 排序算法

2024-06-05 17:36
文章标签 算法 数据结构 排序 实验 scau

本文主要是介绍SCAU 数据结构 实验六 排序算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
![[Pasted image 20240在这里插入图片描述

8638 直接插入排序

Description

用函数实现直接插入排序，并输出每趟排序的结果.

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

4 5 8 0 9 3 2 6 7 1
4 5 8 0 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 3 4 5 8 9 2 6 7 1
0 2 3 4 5 8 9 6 7 1
0 2 3 4 5 6 8 9 7 1
0 2 3 4 5 6 7 8 9 1
0 1 2 3 4 5 6 7 8 9
在这里插入图片描述

1.插入排序：在原有的序列基础上，一次插入一个元素
2.插入排序是一种稳定的排序算法，如果碰见一个和插入元素相 等的，那么插入元素把想插入的元素放在相等元素的后面。
3.时间复杂度为 O(n^2)，在最坏情况下需要进行 n*(n-1)/2 次比较和移动操作。

#include<iostream>
using namespace std;int main()
{int n,i,j,k;cin >> n;int a[n+5];for(i=1;i<=n;i++)   cin >> a[i];//输入for(i=2;i<=n;i++){//如果未排序的比已排序的最大的那个数要小
//例如括号内的是已排序的（13，38，49，65,76,97）27，
//这里就是97比27要大，需要排序if(a[i]<a[i-1]){a[0]=a[i];//把要排序的那个27保存起来//a[i]=a[i-1];//27的位置放置97这个数字，此时的情况是（13，38，49，65,76，97）,97for(j=i-1;a[0]<a[j];j--)//全部往后移，为要插入的数腾出空间，最后是（13，38，38，49,65，76）,97a[j+1]=a[j];a[j+1]=a[0];//把暂存的27放到第一个38的位置}for(int k=1;k<=n;k++)   cout << a[k] << " ";cout << endl;}return 0;
}

8639 折半插入排序

Description

用函数实现折半插入排序，并输出每趟排序的结果.

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

4 5 8 0 9 3 2 6 7 1
4 5 8 0 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 4 5 8 9 3 2 6 7 1
0 3 4 5 8 9 2 6 7 1
0 2 3 4 5 8 9 6 7 1
0 2 3 4 5 6 8 9 7 1
0 2 3 4 5 6 7 8 9 1
0 1 2 3 4 5 6 7 8 9

#include<iostream>
#include<algorithm>
using namespace std;int d[200000];  // 定义一个足够大的数组// 遍历函数，用于输出数组中的元素
void Travers(int n) {for(int i = 1; i <= n; i++) {cout << d[i] << " ";}cout << endl;
}int main() {int n;cin >> n;  // 读取数组的元素数量// 将元素输入到数组中，从下标1开始for(int i = 1; i <= n; i++) {cin >> d[i];}int low, high, mid;// 从第二个元素开始进行插入排序for(int i = 2; i <= n; i++) {d[0] = d[i];  // 将当前元素暂存到哨兵位置d[0]low = 1;high = i - 1;// 二分查找插入位置while(low <= high) {mid = (low + high) / 2;  // 计算中间位置if(d[0] < d[mid]) {high = mid - 1;  // 如果待插入元素小于中间元素，在左半部分查找} else {low = mid + 1;  // 如果待插入元素大于等于中间元素，在右半部分查找}}// 将元素右移，为插入元素腾出位置for(int j = i - 1; j >= high + 1; j--) {d[j + 1] = d[j];}// 将暂存的哨兵元素插入到正确位置d[high + 1] = d[0];// 每趟排序后输出数组的当前状态Travers(n);}return 0;
}

8640 希尔(shell)排序

Description

用函数实现希尔(shell)排序，并输出每趟排序的结果,初始增量d=n/2,其后d=d/2

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出一趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

3 2 6 0 1 5 4 8 7 9
1 0 3 2 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9

在这里插入图片描述

1.希尔排序：插入排序的升级版
当刚开始元素很无序的时候，增量最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，增量很小， 插入排序对于有序的序列效率很高。
2.不稳定：3 5 1 5 0 8
第一个5会交换到第二个5后面

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <malloc.h>
#include <algorithm>
#include <vector>
using namespace std;int n, a[100005];// 打印数组函数
void print()
{for (int i = 0; i < n; i++)  // 从下标0到n-1输出数组元素cout << a[i] << ' ';cout << endl;
}// 希尔排序函数
void shellSort() {for (int gap = n / 2; gap > 0; gap /= 2) {  // 初始化步长为数组长度的一半，逐次减半for (int i = gap; i < n; i++) {  // 从当前步长开始遍历数组for (int j = i - gap; j >= 0 && a[j] > a[j + gap]; j -= gap) {  // 插入排序，将元素按步长间隔进行比较和交换swap(a[j], a[j + gap]);  // 交换元素位置}}print();  // 每次步长变化后打印数组}
}int main()
{cin >> n;  // 输入数组长度for (int i = 0; i < n; i++)  // 输入数组元素cin >> a[i];shellSort();  // 调用希尔排序函数return 0;  // 程序结束
}

8641 冒泡排序

Description

用函数实现冒泡排序，并输出每趟排序的结果(要求当一趟冒泡过程中不再有数据交换，则排序结束)

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出每趟排序结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

4 5 0 8 3 2 6 7 1 9
4 0 5 3 2 6 7 1 8 9
0 4 3 2 5 6 1 7 8 9
0 3 2 4 5 1 6 7 8 9
0 2 3 4 1 5 6 7 8 9
0 2 3 1 4 5 6 7 8 9
0 2 1 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
在这里插入图片描述
冒泡：
1.元素俩俩比较，将大的元素向后调，若元素大小相等，则不交换，所以是稳定排序
2.双重循环：
时间复杂度O(n^2)
空间复杂度O(1)
3.注意flag判断是否发生交换


#include <iostream>
#include <queue>
#include<cstring>
using namespace std;
const int N = 550, M = 10010; 
int a[N];int main()
{int n;cin >> n;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++){int mark = 1;for (int j = 0; j < n-i-1; j++)if (a[j+1] < a[j]){swap(a[j], a[j + 1]);mark = 0;}for (int k = 0; k < n; k++)cout << a[k]<<" ";cout << endl;//某一趟全部不交换才结束if (mark)break;//最后一趟也要输出}return 0;
}

8642 快速排序

Description

用函数实现快速排序，并输出每次分区后排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出每趟排序的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

1 4 2 0 3 5 9 6 7 8
0 1 2 4 3 5 9 6 7 8
0 1 2 4 3 5 9 6 7 8
0 1 2 3 4 5 9 6 7 8
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 7 6 8 9
0 1 2 3 4 5 6 7 8 9
![[Pasted image 20240605143858.png]]在这里插入图片描述
1.快排：双指针在左右两侧，若右指针所指向的元素比中枢小，则将左指针指向的值赋值未右指针指向的值。移动左指针，同理；
2.不稳定：5 3 3 4 3 8 9 10 11
3.时间复杂度：O（nlogn）

#include <iostream>
#include <cstdio>
using namespace std;// 定义常量 N 表示数组最大长度
const int N = 1000;// 定义数组 q 和变量 n
int q[N];
int n;// 快速排序函数
void sort(int q[], int l, int r) {// 基准条件：如果子数组长度为 0 或 1，则不需要排序if (l >= r) return;// 选择枢轴元素 x，并初始化左右指针 i 和 jint x = q[l], i = l, j = r;// 分区操作while (i < j) {// 从右向左扫描，找到第一个小于枢轴 x 的元素while (i < j && q[j] >= x) j--;// 将该元素放到左侧位置q[i] = q[j];// 从左向右扫描，找到第一个大于枢轴 x 的元素while (i < j && q[i] <= x) i++;// 将该元素放到右侧位置q[j] = q[i];}// 将枢轴元素放到正确位置q[i] = x;// 输出当前排序结果，用于调试for (int i = 0; i < n; i++) cout << q[i] << ' ';cout << endl;// 对左右子数组递归排序sort(q, l, j - 1);sort(q, j + 1, r);
}// 主函数
int main() {// 输入数组长度 ncin >> n;// 输入数组元素for (int i = 0; i < n; i++) cin >> q[i];// 调用快速排序函数sort(q, 0, n - 1);// 返回 0 表示程序正常结束return 0;
}

8643 简单选择排序

Description

用函数实现简单选择排序，并输出每趟排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出每趟排序的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

0 4 8 5 9 3 2 6 7 1
0 1 8 5 9 3 2 6 7 4
0 1 2 5 9 3 8 6 7 4
0 1 2 3 9 5 8 6 7 4
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 8 6 7 9
0 1 2 3 4 5 6 8 7 9
0 1 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9
在这里插入图片描述
1.选择排序：给每个位置选存在的最小值
2.选择排序不稳定：举个例子 5 8 5 2 9，
3.时间复杂度：O（n^2）空间复杂度：O（1）；

//选择排序 
void SelectSort(int a[], int n){for(int i = 0; i < n; i ++){int min = i;//min记录最下元素的下标 for(int j = i; j < n; j ++){if(a[j] < a[min]) min = j;}if(min != i) swap(a[i], a[min]);//交换两个值 }
}

8644 堆排序

Description

用函数实现堆排序，并输出每趟排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

第一行：初始建堆后的结果
其后各行输出交换堆顶元素并调整堆的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

9 7 8 6 4 3 2 5 0 1
8 7 3 6 4 1 2 5 0 9
7 6 3 5 4 1 2 0 8 9
6 5 3 0 4 1 2 7 8 9
5 4 3 0 2 1 6 7 8 9
4 2 3 0 1 5 6 7 8 9
3 2 1 0 4 5 6 7 8 9
2 0 1 3 4 5 6 7 8 9
1 0 2 3 4 5 6 7 8 9
0 1 2 3 4 5 6 7 8 9

代码1

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>using namespace std;int n, a[100005];void print()
{for (int i = 1; i <= n; i++)cout << a[i] << ' ';cout << endl;
}void HeapAdjust(int Start, int End)//将a[S...E]调整为以a[S]为根的大根堆
{int dad = Start;int son = dad * 2;while (son <= End)//子结点在范围内才能进行比较{if (son + 1 <= End && a[son] < a[son + 1])son++;//选择大的子结点if (a[dad] > a[son])return;else{swap(a[dad], a[son]);dad = son;son = dad * 2;}}
}void HeapSort()
{for (int i = n / 2; i >= 1; i--){HeapAdjust(i, n);//初建堆}print();for (int i = n; i > 1; i--){swap(a[1], a[i]);HeapAdjust(1, i - 1);print();//输出调整堆的结果}
}int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];HeapSort();return 0;
}

代码2

#include <iostream>
using namespace std;const int N = 1000;
int a[N];
int n; // 堆的大小// 向下调整函数：调整堆
void down(int len,int u) {int t = u;if (2 * u <= len && a[2 * u] > a[t]) t = 2 * u;if (2 * u + 1 <= len && a[2 * u + 1] > a[t]) t = 2 * u + 1;if (t != u) {swap(a[t], a[u]);down(len,t);}
}
void heapSort(int len) {// 建堆for (int i = len / 2; i >= 1; i--) down(len, i);// 输出初始堆for (int i = 1; i <= len; i++) cout << a[i] << ' ';cout << endl;// 排序过程for (int i = 1; i < len; i++) {swap(a[1], a[len - i + 1]); // 将堆顶元素（最大值）交换到数组末尾down(len - i, 1); // 对剩余堆进行调整// 输出调整后的堆for (int j = 1; j <= n; j++) cout << a[j] << ' ';cout << endl;}
}int main() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];heapSort(n);// 输出排序后的数组return 0;
}

8645 归并排序（非递归算法）

Description

用函数实现归并排序（非递归算法），并输出每趟排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出每趟排序的结果，数据之间用一个空格分隔

输入样例

10
5 4 8 0 9 3 2 6 7 1

输出样例

4 5 0 8 3 9 2 6 1 7
0 4 5 8 2 3 6 9 1 7
0 2 3 4 5 6 8 9 1 7
0 1 2 3 4 5 6 7 8 9

在这里插入图片描述
1.非递归的归并排序：
先将n个元素按顺序划分为n/2组（n为奇数，则最后一个为一组）
每一组在组内进行排序
将相邻的两个组一一合并在排序
不断重复直到完成排序
2.稳定：合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结 果序列的前面
3.时间复杂度O（nlogn）

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1010;
int len;
int arr[N], temp[N];void merge(int arr[], int l, int mid, int r)
{int k = 0, i = l, j = mid + 1;// 合并两个有序子数组while (i <= mid && j <= r){if (arr[i] < arr[j])temp[k++] = arr[i++];elsetemp[k++] = arr[j++];}while (i <= mid)temp[k++] = arr[i++];while (j <= r)temp[k++] = arr[j++];// 将合并后的数组复制回原数组for (i = l, j = 0; i <= r; i++, j++)arr[i] = temp[j];
}void merge_sort(int arr[], int len)
{// 迭代合并的步长从 1 开始for (int step = 1; step < len; step *= 2){// 每个步长内进行合并for (int i = 1; i <= len; i += 2 * step){int mid = i + step - 1;int r = min(i + 2 * step - 1, len);merge(arr, i, mid, r);}// 输出排序后的数组for (int i = 1; i <= len; i++)cout << arr[i] << " ";cout << endl;}
}int main()
{cin >> len;for (int i = 1; i <= len; i++)cin >> arr[i];// 调用归并排序算法对数组进行排序merge_sort(arr, len);return 0;
}

8646 基数排序

Description

用函数实现基数排序，并输出每次分配收集后排序的结果

输入格式

第一行：键盘输入待排序关键的个数n
第二行：输入n个待排序关键字，用空格分隔数据

输出格式

每行输出每趟每次分配收集后排序的结果，数据之间用一个空格分隔

输入样例

10
278 109 063 930 589 184 505 069 008 083

输出样例

930 063 083 184 505 278 008 109 589 069
505 008 109 930 063 069 278 083 184 589
008 063 069 083 109 184 278 505 589 930
在这里插入图片描述
1.稳定
2.时间复杂度：O（n * k）
k为位数

#include <iostream>
#include <algorithm>
using namespace std;int x=1;  //用于算每个位数的值bool cmp(int a,int b)
{a/=x;b/=x;if(a%10<b%10) //当前要比较的值比较小的靠前return true;return false;
}int main()
{int n;cin>>n;int a[n];for(int i=0;i<n;i++)scanf("%d",&a[i]);while(x<=100){sort(a,a+n,cmp);for(int i=0;i<n;i++)printf("%03d ",a[i]);  //按格式输出printf("\n");x*=10;  //每次要求的位数乘10}return 0;
}

这篇关于SCAU 数据结构 实验六 排序算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1033717。

相关文章

springboot+dubbo实现时间轮算法

springboot+dubbo实现时间轮算法

《springboot+dubbo实现时间轮算法》时间轮是一种高效利用线程资源进行批量化调度的算法,本文主要介绍了springboot+dubbo实现时间轮算法,文中通过示例代码介绍的非常详细,对大家... 目录前言一、参数说明二、具体实现1、HashedwheelTimer2、createWheel3、n
阅读更多...
Mybatis 传参与排序模糊查询功能实现

Mybatis 传参与排序模糊查询功能实现

《Mybatis传参与排序模糊查询功能实现》：本文主要介绍Mybatis传参与排序模糊查询功能实现,本文通过实例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录一、#{ }和${ }传参的区别二、排序三、like查询四、数据库连接池五、mysql 开发企业规范一、#{ }和${ }传参的
阅读更多...
C#数据结构之字符串(string)详解

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》：本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘
阅读更多...
SpringBoot实现MD5加盐算法的示例代码

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.
阅读更多...
Java时间轮调度算法的代码实现

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组（时间轮）和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时
阅读更多...
C++快速排序超详细讲解

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快
阅读更多...
如何通过Golang的container/list实现LRU缓存算法

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣：146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.
阅读更多...
golang字符串匹配算法解读

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt（KMP）算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串（称为
阅读更多...
通俗易懂的Java常见限流算法具体实现

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》：本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1
阅读更多...
Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2