算法 排序3 Insertion or Heap Sort

2024-04-07 20:48

本文主要是介绍算法 排序3 Insertion or Heap Sort,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案

题目:According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element and moving that to the sorted region. it involves the use of a heap data structure rather than a linear-time search to find the maximum.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either "Insertion Sort" or "Heap Sort" to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resulting sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

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

Sample Output 1:

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

Sample Input 2:

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

Sample Output 2:

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

解答:

其实和上个题没什么区别。解答方案一样,这里就不再赘述了,直接上代码:

#include <iostream>
using namespace std;#define MaxVertexNum 105   //最大100个数据,多留出5个空白
typedef int ElementType;
ElementType myArray[MaxVertexNum];//存原数据,插入排序用
ElementType myArray_1[MaxVertexNum];//存原数据,归并排序用
ElementType myArray2[MaxVertexNum];//存第二行数据int isInsertFlag = 0;
bool isSame(ElementType A[], ElementType B[], int N) {for (int i = 0;i < N;i++) {if (A[i] != B[i])return false;}return true;
}void InsertionSort(ElementType A[], int N)
{ // 插入排序 int P, i;ElementType Tmp;int flag = 0;for (P = 1; P<N; P++) {Tmp = A[P]; // 取出未排序序列中的第一个元素for (i = P; i>0 && A[i - 1]>Tmp; i--)A[i] = A[i - 1]; //依次与已排序序列中元素比较并右移A[i] = Tmp; // 放进合适的位置 if (flag == 1)break;if (isSame(A, myArray2, N)) {flag = 1;isInsertFlag = 1;cout << "Insertion Sort"<<endl;}}
}void Swap(ElementType *a, ElementType *b)
{ElementType t = *a; *a = *b; *b = t;
}void PercDown(ElementType A[], int p, int N)
{ // 改编代码4.24的PercDown( MaxHeap H, int p )    // 将N个元素的数组中以A[p]为根的子堆调整为最大堆 int Parent, Child;ElementType X;X = A[p]; // 取出根结点存放的值 for (Parent = p; (Parent * 2 + 1)<N; Parent = Child) {Child = Parent * 2 + 1;if ((Child != N - 1) && (A[Child]<A[Child + 1]))Child++;  // Child指向左右子结点的较大者 if (X >= A[Child]) break; // 找到了合适位置 else  // 下滤X A[Parent] = A[Child];}A[Parent] = X;
}void HeapSort(ElementType A[], int N)
{ // 堆排序 int i;int flag = 0;for (i = N / 2 - 1; i >= 0; i--)// 建立最大堆 PercDown(A, i, N);for (i = N - 1; i>0; i--) {// 删除最大堆顶 Swap(&A[0], &A[i]);PercDown(A, 0, i);if (flag == 1)break;if (isSame(A, myArray2, N)) {flag = 1;}}
}int main(void) {int N;cin >> N;for (int i = 0;i < N;i++) {cin >> myArray[i];myArray_1[i] = myArray[i];}for (int i = 0;i < N;i++)cin >> myArray2[i];InsertionSort(myArray, N);//插入排序if (isInsertFlag) {	for (int i = 0;i < N - 1;i++)cout << myArray[i] << " ";cout << myArray[N - 1];}	else if (!isInsertFlag) {cout << "Heap Sort" << endl;HeapSort(myArray_1, N);for (int i = 0;i < N - 1;i++)cout << myArray_1[i] << " ";cout << myArray_1[N - 1];}system("pause");return 0;
}

测试结果:

这篇关于算法 排序3 Insertion or Heap Sort的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

C++ Sort函数使用场景分析

《C++Sort函数使用场景分析》sort函数是algorithm库下的一个函数,sort函数是不稳定的,即大小相同的元素在排序后相对顺序可能发生改变,如果某些场景需要保持相同元素间的相对顺序,可使... 目录C++ Sort函数详解一、sort函数调用的两种方式二、sort函数使用场景三、sort函数排序

idea maven编译报错Java heap space的解决方法

《ideamaven编译报错Javaheapspace的解决方法》这篇文章主要为大家详细介绍了ideamaven编译报错Javaheapspace的相关解决方法,文中的示例代码讲解详细,感兴趣的... 目录1.增加 Maven 编译的堆内存2. 增加 IntelliJ IDEA 的堆内存3. 优化 Mave

springboot+dubbo实现时间轮算法

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

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

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

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

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

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

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

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

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

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

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

golang字符串匹配算法解读

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