type
status
date
slug
summary
tags
category
icon
password
前言：
算法与数据结构第六次作业
目录：
一、什么是就地排序？什么是稳定的排序方法？内部排序方法有哪些？
1. 就地排序：指在排序过程中，只需要占用常数的辅助空间的排序方法，即不需要额外的存储空间来进行排序，直接在原数组或列表上进行操作。常见的有冒泡排序、选择排序、插入排序等。
2. 稳定的排序方法：假设 （ 1 i n， 1 j n， i j）且在排序前的序列中 R_i 领先 （即 i < j）。若在排序后的序列中 R_i 仍领先 ，则称所用的排序方法是稳定的。否则，若可能使排序后的序列中 领先于 ，则称所用的排序方法是不稳定的。
3. 内部排序方法：内部排序包括插入排序（直接插入排序、折半插入排序、希尔排序）、交换排序（冒泡排序、快速排序）、选择排序（简单选择排序、树形选择排序（堆排序））、归并排序（2-路归并排序）、基数排序（多关键字排序、链式基数排序）。
如果按内部排序过程中所需的工作量来区分，可分为：
- 简单排序，其时间复杂度为
- 先进的排序方法，其时间复杂度为
- 基数排序，其时间复杂度为
二、写出直接插入排序算法。写出起泡排序算法。写出快速排序算法。写出简单选择排序算法。
直接插入算法：
主函数调用， InsertSort(R, n);
冒泡排序算法：
主函数调用，BubbleSort(R, n); // R 为待排序数组，n 为元素个数
快速排序算法：
主函数调用，QuickSort(R, 0, n - 1);
简单选择排序算法：
主函数调用，SelectSort(R, n);
<ins/>
三、什么是堆？堆排序的思想是什么？下面序列是否为堆，如果不是，调整为堆。{12, 36, 30, 85, 47, 53, 24, 90}。
1. 什么是堆？
堆（Heap）是一种基于完全二叉树的数据结构，满足以下堆属性：
最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值。根节点（堆顶）是最大值。
最小堆（Min Heap）：每个父节点的值都小于或等于其子节点的值。根节点（堆顶）是最小值。
2. 堆排序的思想是什么？
堆排序（Heap Sort）是一种基于堆的原地排序算法，时间复杂度为 ，适用于大规模数据排序。其思想分为建堆和排序两个主要步骤。
3.该序列是否为堆？
不是堆，调整为
四、Give the English of the following terminologies.
排序，插入排序，选择排序，起泡排序，快速排序堆，堆排序。
排序: Sort
插入排序: Insertion Sort
选择排序: Selection Sort
起泡排序: Bubble Sort
快速排序: Quick Sort
堆: Heap
堆排序: Heap Sort
五、对关键字序列（85,92,61,33,99,18,10,48）进行堆排序，使之按关键字递减次序排列（小顶堆），请写出排序过程中得到的初始堆。
初始堆：10,33,18,48,99,85,61,92
六、给出归并排序算法
<ins/>
- 作者:EageYren
- 链接:https://eageyren.edu.deal/learning/algorithm6
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
