浙江大学数据结构MOOC-课后习题-第九讲-排序2 Insert or Merge

本文主要是介绍浙江大学数据结构MOOC-课后习题-第九讲-排序2 Insert or Merge,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

在这里插入图片描述

测试点

在这里插入图片描述

思路分析

刚开始我打算想推出一个规律,来判断是否是归并排序,但实在太过于复杂,我很难去想出这样的规律…因此,参考了其他博主的思路——每做一次排序就和给定的序列比较一次,这样的话只需要在现有的插入和归并算法上稍作添加即可,具体可参考insertion_Sort()Merge_Sort()部分的代码

代码展示

/*
*	一遍遍执行插入排序或者归并排序
*   每次比较是否和给定的序列相同
*/
#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
typedef int ElementType;void print(int A[], int N)
{for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}
}
bool isSame(int A[], int input[], int N)
{for (int i = 0; i < N; i++){if (A[i] != input[i])return false;}return true;
}
bool insertion_Sort(int A[], int input[], int N)
{/* 算法 */int i, j, temp;bool flag = false;for (i = 1; i < N; i++){	temp = A[i];	/* 摸牌 */for (j = i; j > 0 && A[j - 1] > temp; j--)A[j] = A[j - 1];A[j] = temp;if (flag == true){print(A, N);return true;;}if (isSame(A, input, N)){std::cout << "Insertion Sort" << std::endl;flag = true;}}return false;
}void Merge(int A[], int tempA[], int L, int R, int rightEnd)
{int leftEnd = R - 1;int length = rightEnd - L + 1;int i = L;while (L <= leftEnd && R <= rightEnd){if (A[L] < A[R])tempA[i++] = A[L++];elsetempA[i++] = A[R++];}while (L <= leftEnd)tempA[i++] = A[L++];while (R <= rightEnd)tempA[i++] = A[R++];
}void Merge_pass(int A[], int tempA[], int N, int length)
{int i = 0;for (i = 0; i <= N - 2 * length; i += 2 * length)Merge(A, tempA, i, i + length, i + 2 * length - 1);if (i + length < N)Merge(A, tempA, i, i + length, N - 1);else{for (; i < N; i++)tempA[i] = A[i];}
}bool Merge_Sort(int A[], int input[], int N)
{/* 算法 */int* tempA = (int*)malloc(N * sizeof(int));int length = 1;if (tempA != NULL){while (length < N){Merge_pass(A, tempA, N, length);length *= 2;if (isSame(tempA, input, N)){std::cout << "Merge Sort" << std::endl;Merge_pass(tempA, A, N, length);print(A, N);return true;}Merge_pass(tempA, A, N, length);length *= 2;if (isSame(A, input, N)){std::cout << "Merge Sort" << std::endl;Merge_pass(A, tempA, N, length);print(tempA, N);return true;}}free(tempA);}else std::cout << "ERROR";return false;
}void check(int A[], int input[], int N)
{int copyA[MAXSIZE];for (int i = 0; i < N; i++)copyA[i] = A[i];if (Merge_Sort(copyA, input, N))return;else{for (int i = 0; i < N; i++)copyA[i] = A[i];insertion_Sort(copyA, input, N);return;}
}int main()
{int A[MAXSIZE];int input[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];for (int i = 0; i < N; i++)std::cin >> input[i];check(A, input, N);return 0;
}

心路历程

从12号开始的数据结构学习,本来给自己定的DDL是27号,但是到28号早上9:13,我只完成了28道习题,还差9道
实在是高估了自己的实力,也低估了题目的难度,重新定个DDL吧——在30号中午前完成所有题,平均每天3道题,加油加油加油,学完这个就去学操作系统啦

这篇关于浙江大学数据结构MOOC-课后习题-第九讲-排序2 Insert or Merge的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1013036

相关文章

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

鸡尾酒排序算法

目录 引言 一、概念 二、算法思想 三、图例解释 1.采用冒泡排序:   2.采用鸡尾酒排序:  3.对比总结 四、算法实现  1.代码实现  2.运行结果 3.代码解释   五、总结 引言 鸡尾酒排序(Cocktail Sort),也被称为双向冒泡排序,是一种改进的冒泡排序算法。它在冒泡排序的基础上进行了优化,通过双向遍历来减少排序时间。今天我们将学习如何在C