SCAU华南农业大学数据结构oj 实验六

Agt_von

已于 2025-05-27 16:23:47 修改

阅读量955

点赞数 19

分类专栏：北宇治拳皇的SCAU代码之旅文章标签：数据结构算法排序算法 c++

于 2025-05-24 22:27:24 首次发布

本文链接：https://blog.csdn.net/Agt_von/article/details/148193365

版权

北宇治拳皇的SCAU代码之旅专栏收录该内容

5 篇文章

订阅专栏

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

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=1;i<=n;i++)
    {
        cin>>man[i];
    }
    for(int i=2;i<=n;i++)
    {
        if(man[i]<man[i-1])
        {
            man[0]=man[i];
            man[i]=man[i-1];
            int j;
            for(j=i-2;man[0]<man[j];j--)
            {
                man[j+1]=man[j];
            }
            man[j+1]=man[0];

        }
        for(int k=1;k<=n;k++)
        {
            printf("%d ",man[k]);
        }
        printf("\n");
    }
    return 0;
}

解析：插入排序的思路就是从第二项开始与已经排序过的数据的最后一项对比，如果更小就往前插入到合适的位置。

那么如何寻找合适的位置，我们将数组的第0项作为哨兵，将需要插入的数据存入其中，然后把已经排序过的数据的最后一项往后移。

而已经排序过的数据的最后一项已经比对过了，所以我们从i-2项开始寻找，直到碰到比哨兵小的数据，此时我们就将哨兵插入，这样就完成了一趟排序。

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>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=1;i<=n;i++)
    {
        cin>>man[i];
    }
    for(int i=2;i<=n;i++)
    {
        if(man[i]<man[i-1])
        {
            man[0]=man[i];
            man[i]=man[i-1];
            int j;
            for(j=i-2;man[0]<man[j];j--)
            {
                man[j+1]=man[j];
            }
            man[j+1]=man[0];

        }
        for(int k=1;k<=n;k++)
        {
            printf("%d ",man[k]);
        }
        printf("\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

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=1;i<=n;i++)
    {
        cin>>man[i];
    }
    for(int d=n/2;d>=1;d/=2)
    {
    for(int i=1+d;i<=n;i++)
    {
        if(man[i]<man[i-d])
        {
            man[0]=man[i];
            int j;
            for(j=i-d;j>0&&man[j]>man[0];j-=d)
            {
                man[j+d]=man[j];
            }
            man[j+d]=man[0];
        }
    }
    for(int k=1;k<=n;k++)
    {
        cout<<man[k]<<" ";
    }
    cout<<endl;
    }
    return 0;
}

解析：希尔排序也同样是一种插入排序方法，是对直接插入排序的优化。在直接插入排序的基础上添加了增量序列d，代码中的增量序列 $d[k]=\tfrac{length}{2{}^{k}}$ ，每个增量d将数组分为d个分组，对每个分组执行插入排序，而对于插入排序，外层循环i从d+1开始，逐个处理每个分组的元素，内层循环j从i-d开始，以步长d向前比较并移动元素，直到找到插入位置。核心思想是“缩小增量”逐步逼近有序。所以会写直接插入就会写希尔排序。

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

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=1;i<=n;i++)
    {
        cin>>man[i];
    }
    int sig=1;
    for(int i=1;sig==1&&i<=n;i++)
    {
        sig=0;
        for(int j=2;j<=n-i+1;j++)
        {
            if(man[j-1]>man[j])
            {
                int temp=man[j-1];
                man[j-1]=man[j];
                man[j]=temp;
                sig=1;
            }
        }
        for(int k=1;k<=n;k++)
        {
            printf("%d ",man[k]);
        }
        printf("\n");
    }
    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

#include <iostream>
#include <vector>
using namespace std;
void q(vector<int> &man,int low,int high)
{
    if(low>=high) return;
    int a=low;
    int b=high;
    int zhou=man[low];
    while(a<b)
    {
        while(a<b&&man[b]>=zhou) b--;
        if(a<b) swap(man[a++],man[b]);
        while(a<b&&man[a]<=zhou) a++;
        if(a<b) swap(man[a],man[b--]);
    }
    for(int i=0;i<man.size();i++)
    {
        cout<<man[i]<<" ";
    }
    cout<<endl;
    q(man,low,a-1);
    q(man,a+1,high);
}
int main()
{
    int n;
    cin>>n;
    vector<int> man(n);
    for(int i=0;i<n;i++)
    {
        cin>>man[i];
    }
    q(man,0,n-1);
    return 0;
}

解析：快速排序的原理就是找到一个枢轴元素让所有元素与其比较，小的放它左边，大的放他右边。

while(a<b)
    {
        while(a<b&&man[b]>=zhou) b--;
        if(a<b) swap(man[a++],man[b]);
        while(a<b&&man[a]<=zhou) a++;
        if(a<b) swap(man[a],man[b--]);
    }

这是快速排序算法的核心，从数组两端开始扫描，右指针b向左移动，直到找到小于基准值的元素,左指针a向右移动，直到找到大于基准值的元素，交换这两个元素，使左边的元素小于等于基准值，右边的元素大于等于基准值重复这个过程直到a和b相遇。

    q(man,low,a-1);
    q(man,a+1,high);

对基准元素左、右边的部分进行递归排序。

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

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=0;i<n;i++)
    {
        cin>>man[i];
    }
    for(int i=0;i<n-1;i++)
    {
        int mind=i;
        for(int j=i+1;j<n;j++)
        {
            if(man[j]<man[mind])
            {
                mind=j;
            }
        }
        swap(man[i],man[mind]);
        for(int k=0;k<n;k++)
        {
            cout<<man[k]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

解析：选择排序的原理就是每次从未排序部分选择最小元素，并逐步扩大已排序部分，将找到的最小元素与当前位置i的元素交换.

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

#include <iostream>

using namespace std;

void maintain(int man[],int n,int i)
{
    int kobe=i;
    int l=2*i+1;
    int r=2*i+2;
    if(l<n&&man[l]>man[kobe])
    {
        kobe=l;
    }
    if(r<n&&man[r]>man[kobe])
    {
        kobe=r;
    }
    if(kobe!=i)
    {
        swap(man[kobe],man[i]);
        maintain(man,n,kobe);
    }
}
void build(int man[],int n)
{
    for(int i=n/2-1;i>=0;i--)
    {
        maintain(man,n,i);
    }
}
int main()
{
    int n;
    cin>>n;
    int man[100];
    for(int i=0;i<n;i++)
    {
        cin>>man[i];
    }
    build(man,n);
    for(int k=0;k<n;k++)
    {
        cout<<man[k]<<" ";
    }
    cout<<endl;
    for(int i=n-1;i>0;i--)
    {
        swap(man[i],man[0]);
        maintain(man,i,0);
        for(int k=0;k<n;k++)
        {
            cout<<man[k]<<" ";
        }
        cout<<endl;
    }
    return 0;
}

解析：堆排序算法核心就是先构建大顶堆，然后不断地把堆顶移到末尾，然后把剩下的再构成一个大顶堆。

先看堆调整函数：

void maintain(int man[],int n,int i)
{
    int kobe=i;
    int l=2*i+1;
    int r=2*i+2;
    if(l<n&&man[l]>man[kobe])
    {
        kobe=l;
    }
    if(r<n&&man[r]>man[kobe])
    {
        kobe=r;
    }
    if(kobe!=i)
    {
        swap(man[kobe],man[i]);
        maintain(man,n,kobe);
    }
}

完成堆排序，我们必须知道完全二叉树的数组表示

对于索引为i的节点：

父节点：(i-1)/2
左子节点：2*i+1
右子节点：2*i+2

而大顶堆是每个节点的值都大于或等于其子节点的值

参数：man[]（调整对象数组），n（调整范围），i（调整对象）

假设当前节点i是最大值，比较当前节点与左子节点、右子节点，如果子节点更大，则交换递归调整被交换的子节点。递归调用保证仍然满足堆的性质。

再看建堆函数：

void build(int man[],int n)
{
    for(int i=n/2-1;i>=0;i--)
    {
        maintain(man,n,i);
    }
}

为什么从n/2-1开始？

完全二叉树中，最后一个非叶子节点的索引就是n/2-1，而叶子节点本身已经满足堆性质，无需调整

再看排序阶段：

for(int i=n-1;i>0;i--)
    {
        swap(man[i],man[0]);
        maintain(man,i,0);
        for(int k=0;k<n;k++)
        {
            cout<<man[k]<<" ";
        }
        cout<<endl;
    }

将堆顶元素(当前最大值)与当前末尾元素交换
堆大小减1
调整剩余元素为最大堆
重复上述过程直到堆大小为1

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void merg(vector<int> &man)
{
    int n=man.size();
    vector<int> temp(n);
    int siz=1;
    while(siz<n){
    temp=man;
    for(int left=0;left<n;left=left+2*siz)
    {
        int mid=min(left+siz,n);
        int right=min(left+2*siz,n);
        int i=left;
        int j=mid;
        int k=left;
        while(i<mid&&j<right)
        {
            if(temp[i]<=temp[j])
            {
                man[k++]=temp[i++];
            }
            else
            {
                man[k++]=temp[j++];
            }
        }
        while (i<mid) man[k++]=temp[i++];
        while (j<right) man[k++]=temp[j++];
    }
    for(int i=0;i<man.size();i++)
    {
        cout<<man[i]<<" ";
    }
    cout<<endl;
    siz*=2;
    }
}
int main()
{
    int n;
    cin>>n;
    vector<int> man(n);
    for(int i=0;i<n;i++)
    {
        cin>>man[i];
    }
    merg(man);
    return 0;
}

解析：

归并排序是一种基于"分治法"的排序算法，其核心为：

分：将待排序的数组分成两个子数组，每个子数组继续递归地进行分割，直到子数组的长度为1
治：将两个已经有序的子数组合并成一个有序的数组

核心算法：

for(int left=0;left<n;left=left+2*siz)
    {
        int mid=min(left+siz,n);
        int right=min(left+2*siz,n);
        int i=left;
        int j=mid;
        int k=left;
        while(i<mid&&j<right)
        {
            if(temp[i]<=temp[j])
            {
                man[k++]=temp[i++];
            }
            else
            {
                man[k++]=temp[j++];
            }
        }
        while (i<mid) man[k++]=temp[i++];
        while (j<right) man[k++]=temp[j++];
    }

确定边界：
- left：当前处理的子数组对的起始位置
- mid：第一个子数组的结束位置（也是第二个子数组的起始位置）
- right：第二个子数组的结束位置
三指针技术：
- i：指向第一个子数组的当前元素
- j：指向第二个子数组的当前元素
- k：指向原数组中待写入的位置
合并逻辑：
- 比较temp[i]和temp[j]，将较小的放入arr[k]
- 移动相应的指针
- 当任一子数组遍历完后，将另一子数组剩余元素直接复制

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }
    int max_val = *max_element(arr.begin(), arr.end());
    int d = 1;
    int temp = max_val;
    while (temp >= 10) {
        temp /= 10;
        d++;
    }    
    int exp = 1;
    for (int i = 0; i < d; ++i) {
        vector<vector<int>> buckets(10);
        for (int num : arr) {
            int digit = (num / exp) % 10;
            buckets[digit].push_back(num);
        }
        int idx = 0;
        for (int j = 0; j < 10; ++j) {
            for (int num : buckets[j]) {
                arr[idx++] = num;
            }
        }
        for (int num : arr) {
            printf("%0*d ", d, num);
        }
        cout << endl;
        exp *= 10;
    }
    
    return 0;
}