当前位置： 首页 > news >正文

数据结构复习4

news 2025/7/2 5:07:34

第八章 排序

30. 介绍一下各种排序算法的性能？★★★★★★

不稳定的排序算法有：希尔排序、选择排序、堆排序、快速排序。

排序算法平均时间复杂度最坏时间复杂度最好时间复杂度空间复杂度稳定性 
冒泡排序O(n2)O(n2)O(n)O(1)稳定
选择排序O(n2)O(n2)O(n2)O(1)不稳定
插入排序O(n2)O(n2)O(n)O(1) 稳定
折半插入排序O(n2)O(n2)O(nlog⁡n)O(1)稳定
希尔排序O(n1.3)O(n2)O(n)O(1)不稳定
归并排序O(nlog⁡n)O(nlog⁡n)O(nlog⁡n)O(n)稳定
快速排序O(nlog⁡n)O(n2)O(nlog⁡n)O(log⁡n)~O(n)（递归栈）不稳定
堆排序O(nlog⁡n)O(nlog⁡n)O(nlog⁡n)O(1)不稳定
计数排序O(n+k)O(n+k)O(n+k)O(n+k)稳定
桶排序O(n+k)O(n2)O(n)O(n+k)稳定
基数排序O(d⋅n)O(d⋅n)O(d⋅n)O(n+k)稳定

31. 介绍一下插入排序？★★★★ 

 插入排序的工作原理类似于整理扑克牌。

       该算法将待排序的元素分为已排序区和未排序区，每次从未排序区中取出一个元素，插入到已排序区的适当位置，直到所有元素都被插入完毕。

------------------------------------------------------------------------------------------------------------------------

       插入排序的平均时间复杂度是O(n²)，最坏时间复杂度是O(n²)，空间复杂度是O(1)，是一种稳定排序。

32. 介绍一下选择排序？★★★ 

将数组分为已排序区和未排序区。初始时，已排序区为空，而未排序区包含所有元素。

从未排序区中找到最小的元素，并记录其索引。

将最小元素与未排序区的第一个元素交换位置，将其放入已排序区的末尾。

重复步骤2和步骤3，直到未排序区的元素全部交换完毕，得到最终的有序数组。

-------------------------------------------------------------------------------------------------------------------------

选择排序的平均时间复杂度是O(n²)，最坏时间复杂度是O(n²)，空间复杂度是O(1)，是一种不稳定排序。

------------------------------------------------------------------------------------------------------------------------

代码：

public static void insertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {  // 从第二个元素开始（i=1）int key = arr[i];  // 当前待插入的元素int j = i - 1;     // 已排序部分的最后一个索引// 从后往前扫描已排序部分，找到插入位置while (j >= 0 && arr[j] > key) {arr[j + 1] = arr[j]; // 元素后移j--;}arr[j + 1] = key; // 插入到正确位置}}

33. 介绍一下冒泡排序？★★★ 

  它重复地遍历待排序数组，依次比较相邻的元素，并将较大的元素交换到右侧，从而逐步将最大的元素沉到数组的末尾。

       相邻元素比较，如果前面元素比后面更大，则交换位置。第一轮把最大的元素放到末尾，第二轮把第二大的元素放到倒数第2个的位置，直到所有都排好序。

--------------------------------------------------------------------------------------------------------------------------

       冒泡排序的平均时间复杂度是O(n²)，最坏时间复杂度是O(n²)，空间复杂度是O(1)，是一种稳定排序。

--------------------------------------------------------------------------------------------------------------------------

代码：

public static void bubbleSort(int[] arr) {int n = arr.length;boolean swapped; // 用于优化，检查是否发生交换for (int i = 0; i < n - 1; i++) { // 外层循环控制轮数swapped = false;for (int j = 0; j < n - 1 - i; j++) { // 内层循环控制比较范围if (arr[j] > arr[j + 1]) {// 交换相邻元素int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;swapped = true;}}// 如果某一轮没有发生交换，说明数组已经有序，提前结束if (!swapped) {break;}}}

34. 介绍一下快速排序？★★★★★★

       快速排序采用了分治的思想。快速排序的核心思想是选择一个基准元素，通过将数组中的元素按照基准元素进行划分，使得左侧的元素都小于基准元素，右侧的元素都大于基准元素。然后对左右两个子数组分别进行递归排序，直到整个数组有序。

       具体来说，选一个pivot。例如选取最左边的元素记作pivot。定义i和j两个指针，一开始分别指向l和r，j用来寻找比pivot小的元素，i用来寻找比pivot大的元素，若i和j都找到而且i<j那么a[i]和a[j]交换，从而保证了左边的小于pivot，右边的大于pivot。若最后i==j，那么将pivot移动到该位置。

------------------------------------------------------------------------------------------------------------------------

       快速排序的平均时间复杂度是O(nlogn)，最坏时间复杂度是O(n²)，空间复杂度是O(1)，是一种不稳定排序。

--------------------------------------------------------------------------------------------------------------------------

代码：

public static void quickSort(int[] arr, int low, int high) {if (low < high) {// 找到分区点，arr[pi] 现在在正确的位置int pi = partition(arr, low, high);// 递归排序左半部分quickSort(arr, low, pi - 1);// 递归排序右半部分quickSort(arr, pi + 1, high);}}// 分区函数private static int partition(int[] arr, int low, int high) {int pivot = arr[high]; // 选择最后一个元素作为基准int i = low - 1;       // i 是小于基准的元素的边界for (int j = low; j < high; j++) {// 如果当前元素小于基准if (arr[j] < pivot) {i++;// 交换 arr[i] 和 arr[j]swap(arr, i, j);}}// 将基准放到正确的位置（i+1）swap(arr, i + 1, high);return i + 1;}// 交换数组中的两个元素private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

35. 为什么快速排序最坏情况会退化成O(n²)？★★★★★★ 

        最坏情况发生在待排序的序列已经有序或近乎有序的情况下。在这种情况下，如果每次选择的基准元素都是当前子数组的最大或最小值，那么快速排序的分割过程将会非常不平衡，导致递归树的高度接近于n。

       在这种情况下，每次划分只能将序列分成一个空的子数组和一个包含n-1个元素的子数组，而不是将序列均匀地分成两个大小相等的子数组。

36. 介绍一下归并排序？★★★★★★ 

       归并排序采用了分治的思想。归并排序的核心思想是将待排序数组逐步分割成单个元素，然后将这些单个元素合并成有序的数组。它通过不断地将两个有序的子数组合并成一个更大的有序数组，最终得到整个数组有序。

--------------------------------------------------------------------------------------------------------------------------

       归并排序的平均时间复杂度是O(nlogn)，最坏时间复杂度是O(nlogn)，空间复杂度是O(n)，是一种稳定排序。

--------------------------------------------------------------------------------------------------------------------------

代码：

public class MergeSort {// 主方法：对数组 arr 进行归并排序public static void mergeSort(int[] arr) {if (arr == null || arr.length <= 1) {return; // 边界条件：数组为空或长度为1时直接返回}int[] temp = new int[arr.length]; // 临时数组用于合并mergeSort(arr, 0, arr.length - 1, temp);}// 递归排序private static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = left + (right - left) / 2; // 防止溢出mergeSort(arr, left, mid, temp);     // 排序左半部分mergeSort(arr, mid + 1, right, temp); // 排序右半部分merge(arr, left, mid, right, temp);   // 合并左右两部分}}// 合并两个有序子数组private static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left;    // 左子数组起始索引int j = mid + 1; // 右子数组起始索引int k = left;    // 临时数组的起始索引// 比较左右子数组的元素，按顺序放入 tempwhile (i <= mid && j <= right) {if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}// 将左子数组剩余元素拷贝到 tempwhile (i <= mid) {temp[k++] = arr[i++];}// 将右子数组剩余元素拷贝到 tempwhile (j <= right) {temp[k++] = arr[j++];}// 将 temp 中的数据拷贝回原数组for (int p = left; p <= right; p++) {arr[p] = temp[p];}}

37. 简述一下快速排序和归并排序的优缺点（从平均最坏时间复杂度、空间复杂度、稳定性的角度）。★★★★★★ 

（1）快速排序

       优点：

       ①平均时间复杂度较低：快速排序的平均时间复杂度为O(nlogn)，在大多数情况下都能够达到较好的排序效果。

       ②空间复杂度较低：快速排序通常只需要使用很少的额外空间，只需对原数组进行原地操作。

       缺点：

       ①最坏情况下的性能：在最坏情况下，即待排序序列已经有序或近乎有序时，快速排序的时间复杂度会退化到O(n²)，导致性能下降。

       ②不稳定性：快速排序是一种不稳定的排序算法，在交换元素的过程中可能改变相同关键字元素的相对顺序。

（2） 归并排序
       优点：

       ①稳定性：归并排序是一种稳定的排序算法，它能够保持相同关键字元素的相对顺序不变。

       ②适用于外部排序：归并排序的特点使其非常适用于外部排序，即当排序的数据量太大无法完全加载到内存时，可以通过分阶段地读取和写入数据进行排序。

       ③性能稳定：归并排序的时间复杂度始终保持在O(nlogn)，无论是最佳、最坏还是平均情况下。

       缺点：

       需要额外的空间：归并排序需要额外的空间来存储临时数组，因此它的空间复杂度相对较高。

39. 为什么排序需要稳定？★★★★ 

       排序算法的稳定性意味着对于具有相同关键字的元素，排序后它们的相对顺序保持不变。在很多实际应用中，我们需要保持数据中相等元素的顺序关系。

--------------------------------------------------------------------------------------------------------------------------

       例如，在排序员工工资的数据时，如果有多名员工拥有相同的工资水平，我们可能希望按照他们的入职时间来排序，以维持他们在公司内部的先后顺序。如果使用不稳定排序，就可能打乱他们的相对顺序。

40. 归并排序的最坏时间复杂度优于快排，为什么我们还是选择快排？★★★★★★ 

       快速排序通常比归并排序更快。尽管快速排序在最坏情况下的性能可能较差，但在大多数情况下，它的平均时间复杂度要比归并排序低。
       快速排序是原地排序算法。原地排序算法是指排序过程中不需要额外的存储空间，只利用原始输入数组进行排序。
       快速排序的实现相对简单。相比于归并排序，快速排序的实现更为简洁，代码量更少。
       总结：由于快速排序在平均情况下表现更好、占用更少的空间并且更易于实现。

41. 介绍一下堆排序？★★★★★★ 

堆排序可以分为两个主要步骤：建堆和排序。

       建堆的步骤如下：

  1. 若数组有n个元素，从第n/2个元素（非叶节点）开始一直到第1个元素，进行堆的调整。
  2. 对于每个非叶子节点，进行一次下沉操作，将当前节点与其子节点进行比较，如果不满足堆的性质，则交换位置。
  3. 重复步骤2，直到整个数组被构建成一个堆，即满足父节点大于等于子节点（大顶堆）或父节点小于等于子节点（小顶堆）的性质。

       排序的步骤如下：

  1. 首先，将建好的堆中的根节点与最后一个元素交换位置。
  2. 然后，将堆的大小减1，并对新的根节点进行一次下沉操作，以找到新的最大值。
  3. 重复步骤1和步骤2，直到堆的大小为1，即所有元素都排好序。

       补充：

       堆的插入的步骤如下：

  1. 把插入的元素放在数组的末尾，数组的长度+1。
  2. 首先，该节点将其与其父节点进行比较，如果该节点的值大于父节点的值，则交换位置。
  3. 继续将该节点与其新的父节点进行比较，重复上述步骤，直到节点上浮到正确的位置或者达到根节点。（实际上是堆的上浮）

       堆的下沉（堆的调整）：

  1. 用于将一个节点下沉到合适的位置以满足堆的性质。
  2. 从待调整节点开始，将其与其左右子节点中较大的节点进行比较，如果该节点的值小于某个子节点的值，则交换位置。
  3. 继续将该节点与其新的子节点进行比较，重复上述步骤，直到节点下沉到正确的位置或者达到叶子节点。

--------------------------------------------------------------------------------------------------------------------------

代码：

public static void heapSort(int[] arr) {int n = arr.length;// 1. 构建大顶堆（从最后一个非叶子节点开始调整）for (int i = n / 2 - 1; i >= 0; i--) {heapify(arr, n, i);}// 2. 逐个提取堆顶元素（最大值）并调整堆for (int i = n - 1; i > 0; i--) {// 交换堆顶和当前末尾元素swap(arr, 0, i);// 调整剩余堆（范围缩小到 i）heapify(arr, i, 0);}}// 调整以节点 i 为根的子树为大顶堆private static void heapify(int[] arr, int n, int i) {int largest = i;    // 初始化最大值为当前节点int left = 2 * i + 1;  // 左子节点int right = 2 * i + 2; // 右子节点// 如果左子节点比当前最大值大if (left < n && arr[left] > arr[largest]) {largest = left;}// 如果右子节点比当前最大值大if (right < n && arr[right] > arr[largest]) {largest = right;}// 如果最大值不是当前节点，交换并递归调整if (largest != i) {swap(arr, i, largest);heapify(arr, n, largest);}}// 交换数组中的两个元素private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

8.1 解释一下3种插入排序的基本思路： 

直接插入排序：排序区看成左右两部分，左边有序、右边无序，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入

希尔排序：通过将原序列分割成若干个子序列分别进行插入排序。随着排序过程的推进，子序列的规模逐渐减小，直到最后进行一次常规的插入排序（增量为1），此时整个序列已经接近有序

--------------------------------------------------------------------------------------------------------------------------

代码：

 public static void shellSort(int[] arr) {int n = arr.length;// 1. 初始化增量（gap）为 n/2，逐步缩小到 1for (int gap = n / 2; gap > 0; gap /= 2) {// 2. 对每个子序列进行插入排序for (int i = gap; i < n; i++) {int temp = arr[i]; // 当前待插入元素int j;// 在子序列中向前比较并插入for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {arr[j] = arr[j - gap]; // 元素后移}arr[j] = temp; // 插入到正确位置}}}

折半插入排序：相比于直接插入排序，在插入未排序元素时，通过二分查找法找到插入位置，从而减少比较操作的次数。尽管比较次数减少了，但移动元素的次数并没有改变。所以时间复杂度和直接插入排序一致。

--------------------------------------------------------------------------------------------------------------------------

代码：

public static void binaryInsertionSort(int[] arr) {int n = arr.length;for (int i = 1; i < n; i++) {int key = arr[i]; // 当前待插入元素int left = 0;     // 已排序部分的左边界int right = i - 1; // 已排序部分的右边界// 1. 二分查找插入位置while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] > key) {right = mid - 1; // 在左半部分继续查找} else {left = mid + 1;  // 在右半部分继续查找}}// 2. 移动元素（从 left 到 i-1 的元素后移）for (int j = i - 1; j >= left; j--) {arr[j + 1] = arr[j];}// 3. 插入元素arr[left] = key;}}

8.2 解释一下2种交换排序的基本思路： 

冒泡排序：多次遍历待排序序列，每次遍历时比较相邻的元素，如果顺序不对就交换它们的位置，直到整个序列排序完成。

快速排序：每次排序前先找到一个枢纽值，然后通过一次排序将待排序序列分成两个子序列，其中一个子序列的所有元素都小于（或等于）另一个子序列的所有元素，然后递归地对这两个子序列进行快速排序。

8.3 解释一下2种选择排序的基本思路： 

简单选择排序：每次从未排序部分中选择最小（或最大）的元素，将其放在已排序部分的末尾，直到整个序列排序完成。

堆排序：将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点，将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便能得到一个有序序列了。

8.4 解释一下归并排序的基本思路： 

分解：

归并排序开始于将待排序的数组不断地“一分为二”，直到每个子数组只包含一个元素。这个过程是递归进行的，即每个子数组也会继续被分解成更小的子数组，直到每个子数组只包含一个元素。
递归排序与合并：

  1. 在分解过程完成后，递归地开始合并这些子数组。合并时，会取出两个相邻的子数组，并将它们合并成一个有序的新数组。
  2. 合并过程中，会比较两个子数组中的元素，并按照大小顺序依次放入新数组中，直到两个子数组中的所有元素都被考虑完毕。
  3. 这个合并过程是递归进行的，每次合并两个子数组，生成的新有序数组又会被视为新的子数组，继续参与后续的合并过程。

8.5 解释一下基数排序的基本思路：   

  1. 基数排序的思想是把位数相同的一组数组依次从后往前比较其每一位上的大小，经过几轮比较使得数据达到有序的做法。比较的次数跟数据的位数有关系。比如要比较一组手机号码从小到大排列，可以比较手机号每一位大小，然后比较11次，手机号达到有序。
  2. 注意：基数排序每次位的比较可以使用线性排序的方式，比如桶排序或者计数排序，因为它们的时间复杂度为O(n)，而且每轮的比较需要保证每次比较数据的稳定性，不然基数排序就无法完成。

--------------------------------------------------------------------------------------------------------------------------

代码：

public static void radixSort(int[] arr) {if (arr == null || arr.length == 0) return;// 1. 找到数组中的最大值（确定最大位数）int max = Arrays.stream(arr).max().getAsInt();// 2. 从最低位到最高位依次排序for (int exp = 1; max / exp > 0; exp *= 10) {countingSortByDigit(arr, exp);}}// 按某一位进行计数排序private static void countingSortByDigit(int[] arr, int exp) {int n = arr.length;int[] output = new int[n];    // 输出数组int[] count = new int[10];    // 计数数组（0~9）// 统计当前位上每个数字的出现次数for (int num : arr) {int digit = (num / exp) % 10;count[digit]++;}// 计算累计次数（确定每个数字的最终位置）for (int i = 1; i < 10; i++) {count[i] += count[i - 1];}// 从后向前遍历原数组，保证稳定性for (int i = n - 1; i >= 0; i--) {int digit = (arr[i] / exp) % 10;output[count[digit] - 1] = arr[i];count[digit]--;}// 将排序结果拷贝回原数组System.arraycopy(output, 0, arr, 0, n);}

8.9 堆的应用有哪些？ 

  1. 堆排序
  2. 优先队列
  3. 快速找最值

8.10 简述内部排序与外部排序的区别 

内部排序是在内存中进行排序

外部排序是由于信息庞大，无法将整个文件放在内存中进行排序，需要将待排序的记录存储在外存上，排序时候再把数据一部分一部分调用内存进行排序。

来源 

计算机保研/考研面试题——数据结构与算法篇_计算机保研面试 csdn-CSDN博客

面试考点——数据结构篇_数据结构保研面试重点-CSDN博客

http://www.xdnf.cn/news/1076059.html

相关文章：

  • 前端计算机视觉：使用 OpenCV.js 在浏览器中实现图像处理
  • Oracle 常用函数
  • 38.docker启动python解释器，pycharm通过SSH服务直连
  • 【软考高项论文】论信息系统项目的进度管理
  • Zookeeper安装使用教程
  • SQL规范
  • IDEA相关配置记录
  • 【中文核心期刊推荐】《计算机应用与软件》
  • Windows CMD命令分类大全
  • 前端开发面试题总结-原生小程序部分
  • 衡石科技使用手册-企业即时通讯工具数据问答机器人用户手册
  • STM32要学到什么程度才算合格？
  • 华为云Flexus+DeepSeek征文｜基于 Dify-LLM 构建网站智能客服助手的实践探索
  • Go语言安装使用教程
  • C++ 快速回顾（五）
  • Python 数据分析与机器学习入门 (二)：NumPy 核心教程，玩转多维数组
  • 湖北理元理律师事务所债务解法：从法律技术到生活重建
  • 长短期记忆网络（LSTM）：让神经网络拥有 “持久记忆力” 的神奇魔法
  • 安装bcolz包报错Cython.Compiler.Errors.CompileError: bcolz/carray_ext.pyx的解决方法
  • JavaScript异步编程的五种方式
  • 反射，枚举和lambda表达式
  • 七天学会SpringCloud分布式微服务——06——Sentinel
  • springboot中多个定时任务(@Scheduled)如何互不影响
  • 如何用废弃电脑变成服务器搭建web网站（公网访问零成本）
  • OpenCV CUDA模块设备层----- 正切（tangent）运算函数tan()
  • CSDN博客大搬家（本地下载markdown合适和图片本地化）
  • 关于 java：8. Java 内存模型与 JVM 基础
  • 基础算法合集-图论
  • 字节跳动 C++ QT PC客户端面试
  • Bessel位势方程求解步骤