801 排序的基本概念

排序的基本概念

排序的基本概念

排序（Sorting）就是重新安排一组数据的过程，使得这组数据按照特定的顺序排列。

• 目的：将一组任意顺序的数据元素重新排列成有序序列。
• 对象：数据元素（通常是记录，包含一个或多个关键字）。
• 关键字：用于排序的数据项，可以是数值型、字符型等，决定了排序的依据。
• 有序序列：数据元素按照关键字递增或递减的顺序排列。

算法稳定性

稳定性：指在排序过程中，如果待排序序列中存在多个具有相同关键字的元素，经过排序后，这些相同关键字元素的相对次序保持不变。

• 定义：设待排序序列为 $R_1,R_2,...,R_n$，其对应的关键字序列为 $K_1,K_2,...,K_n$。如果存在两个记录 $R_i$ 和 $R_j$，$1\le i<j\le n$，使得 $K_i=K_j$，且在排序后的序列中 $R_i$ 仍然在 $R_j$ 之前，则称该排序算法是稳定的。
• 重要性：对于只以一个关键字排序的情况，稳定性不重要；但如果同时以多个关键字排序，或需要保持原有的相对次序，则稳定性很重要。
• 例子：
  • 稳定排序算法：冒泡排序、插入排序、归并排序、计数排序、基数排序。
  • 不稳定排序算法：选择排序、快速排序、希尔排序、堆排序。

算法稳定性与算法优劣 无关

排序算法的分类

排序算法可以根据不同的标准进行分类：

1. 根据数据存储位置：

   • 内部排序：所有待排序的数据都存储在计算机内存中进行排序。适用于数据量不大的情况。806 内部排序算法的比较和应用
   • 外部排序：待排序的数据量很大，不能一次性全部装入内存，需要借助外部存储设备（如磁盘）进行排序。通常采用“归并”的方法。807 外部排序

2. 根据排序过程中比较和移动操作的特点：

   • 插入排序：通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
     • 直接插入排序
     • 折半插入排序
     • 希尔排序
   • 交换排序：通过比较相邻元素并交换位置，使得无序序列逐渐有序。
     • 冒泡排序
     • 快速排序
   • 选择排序：每次从未排序部分选择最小（或最大）的元素放到已排序部分的末尾。
     • 简单选择排序
     • 堆排序
   • 归并排序：将两个或两个以上的有序子序列合并成一个新的有序序列。
   • 基数排序：不基于比较和交换，而是通过对数据位进行分配和收集来实现排序。
   • 计数排序：不基于比较和交换，通过统计每个元素出现的次数，然后根据统计结果将元素放回正确的位置。

3. 根据时间复杂度：

   • O(n^2) 级别：冒泡排序、插入排序、选择排序。
   • O(n log n) 级别：快速排序、归并排序、堆排序、希尔排序。
   • O(n) 级别：计数排序、基数排序（在特定条件下）。

• 每趟都能确定⼀个元素在其最终位置的有冒泡排序、简单选择排序、堆排序、快速排序，其中前三者能形成全局有序的⼦序列

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
快速排序	$O(n\log n)$	$O(n^2)$	$O(\log n)$	不稳定
归并排序	$O(n\log n)$	$O(n\log n)$	$O(n)$	稳定
堆排序	$O(n\log n)$	$O(n\log n)$	$O(1)$	不稳定
希尔排序	$O(n^{1.3}-n^2)$	$O(n^2)$	$O(1)$	不稳定
计数排序	$O(n+k)$	$O(n+k)$	$O(k)$	稳定
基数排序	$O(d(n+k))$	$O(d(n+k))$	$O(n+k)$	稳定