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

计算机基础知识——数据结构与算法(三)（山东省大数据职称考试）

news 来源：原创 2025/6/9 16:26:57

大数据分析应用-初级

第一部分基础知识

一、大数据法律法规、政策文件、相关标准

二、计算机基础知识

三、信息化基础知识

四、密码学

五、大数据安全

六、数据库系统

七、数据仓库.

第二部分专业知识

一、大数据技术与应用

二、大数据分析模型

三、数据科学

数据结构与算法

大数据分析应用-初级
前言
一、常用的排序方法与应用
练习题目

前言

数据结构与算法

3、掌握常用的排序方法与应用。

一、常用的排序方法与应用

冒泡排序（Bubble Sort）

概念：

它是一种比较简单的排序算法。通过反复比较相邻的元素，如果顺序不对则进行交换，每一轮比较都会将当前未排序部分的最大（或最小）元素 “浮” 到最后（或最前）。

描述方法：

从数组的第一个元素开始，依次比较相邻的两个元素。如果前面的元素大于后面的元素，就交换它们的位置。这样一轮比较下来，最大的元素就会 “冒泡” 到数组的末尾。然后对剩下的元素重复这个过程，直到整个数组都有序。

时间复杂度：

最好情况（数组已经有序）：时间复杂度为O(n)，此时只需要进行一轮比较，没有元素交换。

最坏情况（数组完全逆序）：时间复杂度为O(n^2)，因为需要进行轮比较，每轮比较的次数逐渐减少，总的比较次数接近n(n-1)/2。

平均情况：时间复杂度为O(n^2)。

空间复杂度：

空间复杂度为O(1)，因为只需要几个额外的变量来进行元素交换，是一种原地排序算法。

应用场景：

适用于数据量较小且基本有序的情况。例如，对一个小型班级学生的考试成绩进行初步排序，看看成绩的大致分布情况。

示例代码（Python）：
def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr
插入排序（Insertion Sort）

概念：

插入排序的基本思想是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

描述方法：

把数组分为已排序部分和未排序部分。初始时，已排序部分只有一个元素（通常是数组的第一个元素）。然后从第二个元素开始，将未排序元素逐个插入到已排序部分的合适位置，使得插入后已排序部分仍然有序。

时间复杂度：

最好情况（数组已经有序）：时间复杂度为O(n)，因为每个元素只需要比较一次就可以确定它的位置。

最坏情况（数组完全逆序）：时间复杂度为O(n^2)，因为每次插入一个元素都可能需要移动已排序部分的所有元素。

平均情况：时间复杂度为O(n^2)。

空间复杂度：

空间复杂度为O(1)，它也是一种原地排序算法。

应用场景：

适用于数据量较小，且对部分有序的数据排序效率较高。比如对一个基本有序的通讯录按照姓名排序，新添加了少量联系人后的重新排序。

示例代码（Python）：
def insertion_sort(arr):for i in range(1, len(arr)):current_value = arr[i]position = iwhile position > 0 and arr[position - 1] > current_value:arr[position] = arr[position - 1]position -= 1arr[position] = current_valuereturn arr
选择排序（Selection Sort）

概念：

选择排序的基本思想是在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

描述方法：

首先在未排序的数组中找到最小（或最大）的元素，将其与数组的第一个元素交换位置。然后在剩下的未排序元素中再找到最小（或最大）的元素，将其与数组的第二个元素交换位置，以此类推，直到整个数组都有序。

时间复杂度：

最好情况、最坏情况和平均情况的时间复杂度都是O(n^2)，因为无论数组初始状态如何，都需要进行n(n-1)/2次比较。

空间复杂度：

空间复杂度为O(1)，是原地排序算法。

应用场景：

简单直观，对数据量较小的情况比较适用。例如对一个小型活动的参与人员按照年龄从小到大排序，人数不多时可以快速完成排序。

示例代码（Python）：
def selection_sort(arr):for i in range(len(arr)):min_idx = ifor j in range(i + 1, len(arr)):if arr[j] < arr[min_idx]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr
快速排序（Quick Sort）

概念：

快速排序是一种分治的排序算法。它的基本思想是通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序。

描述方法：

选择一个基准元素（通常是数组的第一个元素），通过一趟排序将数组分为两部分，左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后递归地对左右两部分进行排序，直到整个数组都有序。

时间复杂度：

最好情况（每次划分都能将数组分为两个大小相近的子数组）：时间复杂度为O(nlogn)。

最坏情况（数组已经有序或逆序，每次划分得到的子数组一个为空，一个为 n - 1 个元素）：时间复杂度为O(n^2)。

平均情况：时间复杂度为O(nlogn)。

空间复杂度：

最好情况：空间复杂度为O(nlogn)，因为递归调用栈的深度为O(nlogn)。

最坏情况：空间复杂度为O(n)，当递归需要的栈空间达到最大值时。

应用场景：

是一种高效的排序算法，广泛应用于各种需要排序的场景，尤其是数据量较大的情况。例如对一个大型文件中的数据进行排序，或者对大量的数据库记录排序。

示例代码（Python）：
def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[0]left = [x for x in arr[1:] if x <= pivot]right = [x for x in arr[1:] if x > pivot]return quick_sort(left) + [pivot] + quick_sort(right)
归并排序（Merge Sort）

概念：

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide - and - Conquer）的一个非常典型的应用。

描述方法：

将数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。递归地进行划分和合并操作，直到整个数组都有序。

时间复杂度：

最好情况、最坏情况和平均情况的时间复杂度都是O(nlogn)，因为每次划分的时间复杂度为O(nlogn)，每次合并的时间复杂度为O(n)。

空间复杂度：

空间复杂度为O(n)，因为在合并过程中需要额外的空间来存储临时数组。

应用场景：

适用于对稳定性要求较高（相同元素的相对顺序在排序前后不变）且数据量较大的排序任务。例如在一些数据库系统中对数据进行排序，同时要保证数据的稳定性。

示例代码（Python）：
def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left = merge_sort(arr[:mid])right = merge_sort(arr[mid:])return merge(left, right)def merge(left, right):merged = []i = j = 0while i < len(left) and j < len(right):if left[i] <= right[j]:merged.append(left[i])i += 1else:merged.append(right[j])j += 1merged.extend(left[i:])merged.extend(right[j:])return merged
堆排序（Heap Sort）

概念：

堆排序是利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，分为大顶堆（每个节点的值都大于或等于其子节点的值）和小顶堆（每个节点的值都小于或等于其子节点的值）。

描述方法：

首先将数组构建成一个堆（大顶堆或小顶堆），然后将堆顶元素与堆的最后一个元素交换位置，此时最大（或最小）元素就放到了正确的位置。接着对剩下的元素重新调整为堆，重复这个过程，直到整个数组都有序。

时间复杂度：

时间复杂度为O(nlogn)，无论是最好情况、最坏情况还是平均情况。

空间复杂度：

空间复杂度为O(1)，是一种原地排序算法。

应用场景：

适合在对空间复杂度要求比较严格，且需要稳定排序性能的场景。例如在一些嵌入式系统或者对内存使用比较敏感的环境中进行排序。

示例代码（Python）：
def heap_sort(arr):n = len(arr)# 构建最大堆for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)# 逐个提取元素for i in range(n - 1, 0, -1):arr[0], arr[i] = arr[i], arr[0]heapify(arr, i, 0)return arrdef heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest!= i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)

练习题目

单选题

（1）下列排序算法中，时间复杂度在平均情况下为O(n^2)的是（）
A. 快速排序
B. 插入排序
C. 归并排序
D. 堆排序

答案：B

解析：插入排序的平均时间复杂度是O(n^2)。快速排序平均时间复杂度是O(nlogn)；归并排序时间复杂度是O(nlogn)；堆排序时间复杂度是O(nlogn)。

（2）以下哪种排序算法是稳定的排序算法（）
A. 快速排序
B. 选择排序
C. 归并排序
D. 堆排序

答案：C

解析：归并排序是稳定的排序算法，它在合并过程中，如果两个元素相等，会按照原来的顺序将它们放入合并后的数组中。快速排序、选择排序和堆排序都是不稳定的排序算法。

（3）在最好情况下，时间复杂度为O(n)的排序算法是（）
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 快速排序

答案：B

解析：插入排序在最好情况下（数组已经有序），每次只需要比较一次就可以确定元素位置，时间复杂度为O(n)。冒泡排序最好情况时间复杂度是O(n)，但需要一轮比较；选择排序最好情况时间复杂度是O(n^2)；快速排序最好情况时间复杂度是O(nlogn)。

（4）下列排序算法中，空间复杂度为O(1)的是（）
A. 归并排序
B. 快速排序（最好情况）
C. 插入排序
D. 堆排序

答案：C

解析：插入排序空间复杂度为O(1)，是原地排序算法。归并排序空间复杂度为O(n)；快速排序最好情况空间复杂度为O(logn)，最坏情况是O(n)；堆排序空间复杂度为O(1)。

（5）如果要对一个基本有序的数组进行排序，哪种排序算法效率最高（）
A. 冒泡排序
B. 选择排序
C. 插入排序
D. 快速排序

答案：C

解析：插入排序对于基本有序的数组效率最高，因为它只需要少量的比较和移动操作。冒泡排序也比较适合基本有序数组，但效率不如插入排序；选择排序效率不受数组初始顺序影响，效率较低；快速排序在基本有序数组上可能退化为O(n^2)复杂度。

多选题

（1）以下哪些排序算法的时间复杂度在最坏情况下是（）
A. 冒泡排序
B. 插入排序
C. 选择排序
D. 快速排序

答案：ABCD

解析：冒泡排序、插入排序、选择排序最坏情况时间复杂度本身就是O(n^2)；快速排序在最坏情况（如数组已经有序或逆序）下时间复杂度也会退化为O(n^2)。

（2）属于不稳定排序算法的有（）
A. 快速排序
B. 选择排序
C. 堆排序
D. 希尔排序（一种改进的插入排序）

答案：ABCD

解析：快速排序在划分过程中可能会改变相同元素的相对顺序；选择排序每次选择最小（大）元素与前面元素交换，可能会打乱相同元素顺序；堆排序在调整堆的过程中会改变相同元素顺序；希尔排序由于分组插入排序的方式也可能导致相同元素顺序改变。

（3）以下排序算法中，是基于比较的排序算法有（）
A. 冒泡排序
B. 计数排序
C. 快速排序
D. 归并排序

答案：ACD

解析：冒泡排序、快速排序和归并排序都是通过比较元素的大小来进行排序的。计数排序不属于基于比较的排序算法，它是一种非比较排序算法，是利用元素的值作为数组的下标来统计元素出现的次数，从而实现排序。

（4）在数据量较大的情况下，通常可以选择以下哪些排序算法来提高效率（）
A. 快速排序
B. 归并排序
C. 堆排序
D. 插入排序

答案：ABC

解析：快速排序、归并排序和堆排序在数据量较大时，平均时间复杂度为O(nlogn)，效率较高。插入排序时间复杂度为O(n^2)，在数据量较大时效率较低。

（5）下列关于排序算法空间复杂度的说法正确的是（）
A. 原地排序算法空间复杂度为O(1)
B. 归并排序空间复杂度与数组长度有关
C. 快速排序空间复杂度在最好情况下为O(logn)
D. 堆排序是原地排序算法，空间复杂度为O(1)

答案：ABCD

解析：原地排序算法是指在排序过程中只需要常数级别的额外空间，空间复杂度为O(1)。归并排序在合并过程中需要额外的数组来存储临时数据，空间复杂度为O(n)，与数组长度有关。快速排序在最好情况下，递归调用栈的深度为O(logn)，空间复杂度为O(logn)。堆排序是原地排序算法，空间复杂度为O(1)。

判断题

（1）快速排序一定比冒泡排序快。（）

答案：错误

解析：快速排序的平均时间复杂度是O(nlogn)，冒泡排序平均时间复杂度是O(n^2)，但在最坏情况下（如数组已经有序），快速排序时间复杂度会退化为O(n^2)，而冒泡排序最好情况时间复杂度是O(n)，所以不能绝对地说快速排序一定比冒泡排序快。

（2）所有时间复杂度为O(nlogn)的排序算法都是稳定的。（）

答案：错误

解析：例如堆排序时间复杂度是O(nlogn)，但它是不稳定的排序算法，而归并排序时间复杂度也是O(nlogn)，它是稳定的排序算法，所以不是所有时间复杂度为的排序算法都是稳定的。

（3）插入排序在任何情况下都比选择排序效率高。（）

答案：错误

解析：插入排序在数组基本有序的情况下效率较高，时间复杂度接近O(n)，但在数组完全无序的情况下，插入排序和选择排序的时间复杂度都是O(n^2)，所以不能说插入排序在任何情况下都比选择排序效率高。

（4）归并排序的空间复杂度是O(logn)。（）

答案：错误

解析：归并排序的空间复杂度是O(n)，因为在合并过程中需要额外的空间来存储临时数组。

（5）堆排序是一种基于比较的排序算法。（）

答案：正确

解析：堆排序在构建堆和调整堆的过程中，需要比较节点与其子节点（或父节点）的大小关系，所以它是一种基于比较的排序算法。

大数据分析应用-初级

数据结构与算法

前言

数据结构与算法

一、常用的排序方法与应用

练习题目

相关文章：