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

  • 开发
  • 7

在这里插入图片描述
![[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）,97
            for(j=i-1;a[0]<a[j];j--)//全部往后移，为要插入的数腾出空间，最后是（13，38，38，49,65，76）,97
                a[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 和 j
    int 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() {
    // 输入数组长度 n
    cin >> 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++];
        else
            temp[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;
}
阅读全部

相关推荐

  2. SCAU 数据结构 实验四 树

    2024-06-06 04:04:01       10 阅读

  3. 数据结构奇妙旅程之六大排序算法

    2024-06-06 04:04:01       20 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-06-06 04:04:01       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-06-06 04:04:01       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-06-06 04:04:01       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-06-06 04:04:01       20 阅读

热门阅读

  3. 从0开发一个Chrome插件：创建第一个Chrome插件

    2024-06-06 04:04:01       11 阅读

  11. 2024华为OD机试真题-全量和已占用字符集-C++(C卷D卷)

    2024-06-06 04:04:01       9 阅读

  13. SASS语法基础

    2024-06-06 04:04:01       9 阅读

  15. CentOS 7 64位 常用命令

    2024-06-06 04:04:01       6 阅读

  16. 03-3.1.1 栈的基本概念

    2024-06-06 04:04:01       9 阅读

  20. 日常工作笔记

    2024-06-06 04:04:01       10 阅读

  21. 带你认识ffmpeg

    2024-06-06 04:04:01       9 阅读

  22. python中使用缓存技术

    2024-06-06 04:04:01       10 阅读

  25. 苹果ios用户下载ipa文件内测签名的后的app应用下载安装到手机图标消失了是什么原因呢？

    2024-06-06 04:04:01       8 阅读

  27. rpc理解

    2024-06-06 04:04:01       9 阅读

  28. mybatis离谱bug乱转类型

    2024-06-06 04:04:01       9 阅读

  29. AcWing 841. 字符串哈希——算法基础课题解

    2024-06-06 04:04:01       8 阅读

  30. 基于学习的决策树

    2024-06-06 04:04:01       7 阅读