C语言数据结构——常见排序算法（一）

0.前言

1.走近排序

1.1排序的概念

1.2常见排序算法的分类

2.插入排序

2.1基本思想

2.2直接插入排序

2.2.1复杂度分析

2.2.2性能和特点

2.3希尔排序

2.3.1复杂度分析

2.3.2性能和特点

2.3.3增量序列的选择

2.3.4优缺点综述

3.选择排序

3.1基本思想

3.2直接选择排序

3.2.1复杂度分析

3.2.2性能和特点

3.3堆排序

3.3.1复杂度分析

3.3.2注意事项

4.小结

（图像由AI生成）

0.前言

排序是计算机科学中最基础也是最重要的算法之一。在数据处理过程中，将数据集按照一定的顺序重新排列的过程称为排序。排序算法的研究，不仅能够提高我们解决问题的效率，而且对于理解数据结构与算法的设计思想具有重要意义。

1.走近排序

排序算法是计算机科学中的基石之一，它关乎到如何高效地组织和处理数据。无论是数据库管理、文件排序、还是数据分析，排序都扮演着至关重要的角色。了解和掌握各种排序算法，不仅能提升我们解决实际问题的能力，还能深化我们对算法设计和优化的理解。

1.1排序的概念

排序，简单来说，就是将一组无序的数据按照某种特定的顺序（如升序或降序）重新排列的过程。排序的目的是使数据集更加有序，便于我们进一步的操作和分析。排序不仅限于数字，还可以是字母、单词或任何可以比较大小的数据。

在排序过程中，我们主要关注两个方面：排序算法的执行效率和算法的稳定性。执行效率通常通过算法的时间复杂度和空间复杂度来衡量，而算法的稳定性则指的是排序后相等数据之间的相对顺序是否发生改变。

1.2常见排序算法的分类

排序算法按照不同的标准可以分为多种类型，最主要的分类方式是根据是否进行元素间的比较：

比较排序: 这类算法通过比较决定元素间的相对顺序。由于它们的运作依赖于比较操作，所以理论上的最低时间复杂度为O(n log n)。常见的比较排序算法包括冒泡排序（Bubble Sort）、选择排序（Selection Sort）、插入排序（Insertion Sort）、希尔排序（Shell Sort）、快速排序（Quick Sort）、归并排序（Merge Sort）和堆排序（Heap Sort）。
非比较排序: 这类算法不通过比较来决定元素间的相对顺序，而是通过其他方法。非比较排序通常能在线性时间内完成，即O(n)。典型的非比较排序算法包括计数排序（Counting Sort）、桶排序（Bucket Sort）和基数排序（Radix Sort）。

比较排序算法的优点在于它们的通用性和稳定性，但在某些情况下，如数据量极大且数据范围有限时，非比较排序算法可能会更加高效。

2.插入排序

2.1基本思想

插入排序是一种简单直观的排序算法，其基本思想源于日常生活中的排序方式，如对扑克牌进行排序。算法的核心思想是将待排序的数组分为两个部分：一部分是已经排序好的，另一部分是未排序的。初始时，排序好的部分只包含数组的第一个元素，剩下的部分视为未排序。然后，算法逐个遍历未排序的元素，将每个遍历到的元素插入到已排序部分的适当位置，以保持已排序部分总是有序的。

在插入的过程中，为了找到每个元素应该插入的位置，算法会与已排序部分的元素进行比较。如果已排序的元素大于（或小于，根据排序顺序而定）待插入的元素，则已排序的元素会向后（或向前）移动，为新元素腾出空间。这个过程一直进行，直到找到合适的插入位置。一旦找到，就将当前元素插入此处。这个过程重复进行，直到所有的元素都被遍历并插入到适当的位置，最终得到一个有序的数组。

2.2直接插入排序

直接插入排序是插入排序算法的一种基本形式，它通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。这段C语言代码提供了直接插入排序的实现框架，下面我们将详细解释这个过程，并分析其复杂度。

void InsertSort(int* a, int n)
{
	assert(a);
	int i = 0;
	for (i = 1; i < n; i++)
	{
		int end = i - 1;
		int tmp = a[i];
		while (end >= 0 && a[end] > tmp)
		{
			a[end + 1] = a[end];
			end--;
		}
		a[end + 1] = tmp;
	}
}

首先，该函数InsertSort接收一个整数数组a和数组的长度n作为参数。
函数中用assert(a);确保传入的数组指针有效。
排序过程从数组的第二个元素开始（即i = 1），因为单个元素（数组的第一个元素）默认已经是排序好的。
对于每个i从1到n-1的元素，将其临时保存在变量tmp中，并与其前面的元素（即索引i-1）进行比较。
如果前面的元素（a[end]）大于临时保存的元素（tmp），则将前面的元素后移一位（a[end + 1] = a[end]），直到找到tmp应该插入的位置。
最后，将tmp插入到找到的位置上。

流程示意图如下：（来自1.3 插入排序 | 菜鸟教程 (runoob.com)）

2.2.1复杂度分析

时间复杂度：
- 最好情况：如果数组已经是排序好的，那么每次比较时a[end] > tmp这个条件都不成立，内层循环不执行，此时的时间复杂度为O(n)。
- 最坏情况：如果数组是逆序的，每次插入的元素都需要比较并移动所有的已排序元素，这时时间复杂度为O(n^2)。
- 平均情况：考虑到平均情况下元素需要移动的次数，时间复杂度也是O(n^2)。
空间复杂度：直接插入排序是原地排序算法，除了固定的几个辅助变量外，不需要额外的存储空间，因此空间复杂度为O(1)。

2.2.2性能和特点

稳定性：直接插入排序是一种稳定的排序方法，相等的元素在排序后会保持它们原有的顺序。
适用场景：直接插入排序特别适合于小规模数据的排序，或者数据基本有序的情况。对于大规模且完全无序的数据集合，直接插入排序的效率较低。

2.3希尔排序

希尔排序（Shell Sort）是由Donald Shell于1959年提出的一种排序算法，它是直接插入排序的一种高效改进版本。希尔排序通过引入“增量gap”来允许交换距离较远的元素，从而能够对多个子列表进行部分排序，最终逐步减小“增量gap”直至1，完成整体排序。这种方法大大提高了数组排序的速度。

void ShellSort(int* a, int n)
{
	assert(a); // 确保数组a非空
	int gap = n; // 初始增量gap设置为数组长度n
	while (gap > 1) // 循环，直到gap=1
	{
		gap = gap / 3 + 1; // 动态减小gap值，最优的增量序列之一
		for (int i = 0; i < n - gap; i++) // 遍历数组
		{
			int end = i;
			int tmp = a[end + gap]; // 以gap为间隔进行插入排序
			while (end >= 0 && a[end] > tmp) // 插入排序的比较和移动
			{
				a[end + gap] = a[end]; // 元素后移
				end -= gap; // 向前移动gap个位置
			}
			a[end + gap] = tmp; // 插入元素
		}
	}
}

初始化：函数首先确认数组非空。
增量gap的选择：初始gap值设置为数组长度，随后在每次迭代中通过gap = gap / 3 + 1来减小gap的大小。这个增量的选择基于经验和数学分析，旨在平衡效率和简单性。
部分排序：通过外层循环逐步缩小gap，内层循环则负责以当前gap值为间隔执行插入排序。通过这种方式，算法初期能够快速减小“逆序对”的数量，即使是距离很远的元素也可以进行比较和交换。

流程示意图如下：（来自1.4 希尔排序 | 菜鸟教程 (runoob.com)）

2.3.1复杂度分析

希尔排序的时间复杂度与增量序列的选择有很大关系。对于上述代码中的增量序列（gap = gap / 3 + 1）：

最好情况：如果数组已经是部分有序的，希尔排序可以接近线性时间复杂度，即O(n)。
最坏情况：对于特定的序列和不同的增量选择，最坏情况的时间复杂度可能高达O(n^2)。但在实际应用中，希尔排序的时间复杂度通常被认为介于O(n)和O(n^2)之间，一些研究表明可以达到O(n^1.3)左右。
平均情况：由于希尔排序的复杂性，平均时间复杂度不容易准确计算，但经验表明它远远快于O(n^2)的直接插入排序。

2.3.2性能和特点

空间复杂度：由于希尔排序是基于插入排序的，它也是一种原地排序算法，空间复杂度为O(1)。
稳定性：希尔排序不是一个稳定的排序算法。由于在排序过程中会比较并交换距离较远的元素，因此可能会改变相同元素之间的相对位置。
适用场景：希尔排序特别适合处理大规模的数据集合。由于它对数据的初期（即未排序或部分排序的数据）可以快速减少“逆序对”的数量，因此在对大量数据进行排序时，它能够显示出较好的性能，尤其是数据初始状态较为无序的情况下。

希尔排序的一个重要特点是它通过减小增量gap来逐步细化数组的局部有序状态，直至整个数组有序。这种从宏观到微观的排序策略使得希尔排序在多数情况下都比传统的插入排序有更高的效率。

2.3.3增量序列的选择

希尔排序性能的一个关键因素在于增量序列的选择。虽然最初的提议是每次将增量减半，但后续的研究表明，更复杂的增量序列可以提供更好的性能。例如，使用Hibbard增量序列的希尔排序的最坏情况时间复杂度可以降低到O(n^(3/2))，而使用Sedgewick增量序列则可能进一步提升效率。

2.3.4优缺点综述

优点：
- 对于中等大小的数组，它提供了不错的性能，尤其是在数组部分有序的情况下效果更佳。
- 实现相对简单，且不需要额外的存储空间（原地排序）。
- 在数组完全随机或部分有序时，通常优于传统的O(n^2)排序算法（如冒泡排序、直接插入排序）。
缺点：
- 它是一种不稳定的排序算法，可能会改变相等元素之间的初始顺序。
- 时间复杂度不只依赖于数据规模，还受增量序列的选择影响，预测性不强。
- 对于非常大的数据集，希尔排序的性能可能不如O(n log n)的排序算法，如快速排序、堆排序或归并排序。

3.选择排序

3.1基本思想

选择排序是一种简单直观的排序算法，其基本思想是分为已排序区间和未排序区间，通过不断地选择未排序区间中的最小（或最大）元素，然后将其移动到已排序区间的末尾，从而达到整个数据集合的排序目的。

这个过程包括以下几个步骤：

初始化：假设最开始时，已排序区间为空，而整个数组为未排序区间。
选择最小（或最大）元素：从未排序区间中遍历寻找最小（或最大）的元素。
交换元素：将找到的最小（或最大）元素与未排序区间的第一个元素交换位置。此时，该元素即被加入到已排序区间的末尾，而原未排序区间的第一个元素被移动到了该元素原来的位置。
重复过程：重复步骤2和3，直至未排序区间的元素个数为0。

选择排序的关键在于它每次都能确定未排序区间中的一个最小（或最大）元素，然后通过交换使之成为已排序区间的一部分。这个过程不依赖于数据的原始排列方式，即使数据已经是部分排序的状态，算法的执行步骤和找到的最小（或最大）元素的顺序也不会有变化。

3.2直接选择排序

直接选择排序是选择排序算法的一种实现方式。其基本思想是通过不断选择未排序区间中的最小元素，并将其放置到已排序区间的末尾，从而实现数组的逐步排序。

void SelectSort(int* a, int n)
{
    assert(a); // 确保数组指针有效
    int begin = 0; // 已排序区间的起始位置
    int end = n - 1; // 已排序区间的结束位置

    // 当begin小于end时，说明还有未排序的元素
    while (begin < end)
    {
        int min = begin; // 假设最小值位置为当前开始位置
        int max = begin; // 假设最大值位置也为当前开始位置
        // 遍历未排序的区间，寻找最小和最大值的位置
        for (int i = begin; i <= end; i++)
        {
            if (a[i] < a[min])
            {
                min = i; // 更新最小值的位置
            }
            if (a[i] > a[max])
            {
                max = i; // 更新最大值的位置
            }
        }

        // 将找到的最小值移动到已排序区间的起始位置
        Swap(&a[begin], &a[min]);

        // 如果最大值的位置是begin（即最小值原位置），由于min和begin已经交换，max应更新为min的位置
        if (max == begin)
        {
            max = min;
        }

        // 将找到的最大值移动到已排序区间的末尾位置
        Swap(&a[end], &a[max]);

        // 缩小未排序区间的范围
        begin++;
        end--;
    }
}

这段代码的核心思想是在每一轮循环中同时找到未排序区间中的最小值和最大值，并将它们分别放置到已排序区间的两端。这种方式实际上在每一轮处理中将未排序区间缩小了两个元素，而不是一个，提高了排序的效率。

Swap函数：Swap(&a[begin], &a[min])和Swap(&a[end], &a[max])分别用于交换最小值和最大值与其应放置的位置。这里假设Swap函数是用来交换两个整数值的辅助函数。
特殊情况处理：在交换最小值后，如果最大值的位置是开始位置begin，这意味着最小值和开始位置已经交换，因此最大值现在应该在min指示的位置，所以max更新为min的位置，以确保最大值能正确交换到end位置。

流程示意图如下（来自1.2 选择排序 | 菜鸟教程 (runoob.com)）

注意：下图中所示意的流程每趟遍历仅找最小值，找到后再向前面已排序数组末尾插入，效率不如上面代码中同时找max和min的操作，但避免了上面“特殊情况处理”的过程。

3.2.1复杂度分析

直接选择排序算法的时间复杂度和空间复杂度分析如下：

时间复杂度：
- 最佳情况：O(n²)，即使数组已经是有序的，算法仍然执行外层和内层的循环，寻找每个位置的最小（或最大）元素。
- 最坏情况：O(n²)，无论数组的初始状态如何，选择排序都需要比较所有未排序的元素来找到最小（或最大）的元素，并执行相应的交换操作。
- 平均情况：O(n²)，对于一个随机排列的数组，选择排序的平均表现和最坏情况相同，因为它总是执行一个完整的比较和交换过程，与数组的初始排序无关。
空间复杂度：O(1)，选择排序是一种原地排序算法。它不需要额外的存储空间，仅使用有限的几个变量来存储索引和临时数据。

3.2.2性能和特点

直接选择排序算法具有以下几个性能特点：

不稳定排序：选择排序是一种不稳定的排序算法。在选择最小（或最大）元素并将其与另一个元素交换位置时，可能会改变相等元素之间的原始相对顺序。
原地排序：由于选择排序不依赖额外的存储空间，它是一种原地排序算法，这意味着它对内存的使用非常高效。
性能限制：尽管选择排序的空间效率很高，但其时间效率较低，特别是对于大规模数据集。它的时间复杂度在所有情况下都是O(n²)，这使得它不适用于数据量大的情况。
简单直观：选择排序的实现相对简单直观，易于理解和编码，这使得它成为教学和学习排序算法时的一个好选择。

3.3堆排序

堆排序是一种基于比较的排序算法，利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

//堆排序
void AdjustDown(int* a, int n, int root)
{
	assert(a);
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	assert(a);
	//建堆
	int i = 0;
	for (i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//排序
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

以下是堆排序算法的步骤解析：

1. 建立堆

初始时，将整个序列看作是一棵完全二叉树的顺序存储结构。建立堆的过程，就是将这棵完全二叉树调整为堆结构。这里以建立大顶堆为例：

从最后一个非叶子节点开始（即最后一个节点的父节点），对每一个非叶子节点进行下沉操作（AdjustDown），确保每个非叶子节点都遵循大顶堆的性质（父节点的值大于子节点的值）。
递归地对每个非叶子节点执行这一过程，直到调整到根节点。

for (i = (n - 2) / 2; i >= 0; i--)
{
    AdjustDown(a, n, i);
}

2. 排序过程

将堆顶元素（即当前最大值）与堆的最后一个元素交换位置，此时最大元素已经放到了它最终的位置。
然后，将剩下的n-1个元素重新调整为大顶堆。
重复这个过程，直到所有元素都排好序。

int end = n - 1;
while (end > 0)
{
    Swap(&a[0], &a[end]);
    AdjustDown(a, end, 0);
    end--;
}

AdjustDown函数

此函数负责调整指定节点及其子树，使之满足大顶堆的性质。
如果子节点的值大于父节点的值，则交换这两个节点的值，并继续向下调整。

int parent = root;
int child = parent * 2 + 1; // 左子节点的位置
while (child < n)
{
    // 选出两个子节点中较大的一个
    if (child + 1 < n && a[child + 1] > a[child])
    {
        child++;
    }
    // 如果子节点大于父节点，进行交换，并继续向下调整
    if (a[child] > a[parent])
    {
        Swap(&a[child], &a[parent]);
        parent = child;
        child = parent * 2 + 1;
    }
    else
    {
        break;
    }
}

3.3.1复杂度分析

堆排序的效率和复杂度分析是算法评价的重要指标。堆排序的时间复杂度主要分为两个部分：建堆的过程和排序过程。

建堆复杂度

建堆过程是从最后一个非叶子节点开始，对每个非叶子节点执行下沉操作（AdjustDown）。每次AdjustDown的时间复杂度是O(log n)，因为需要从当前节点下沉到叶子节点，最坏情况下与树的高度相同。由于完全二叉树的高度约为log n，建堆过程的总时间复杂度为O(n)。这个看起来有些违反直觉，原因是树的层级越低，节点数越多，但下沉的深度越浅；而树的层级越高，节点数越少，下沉的深度虽然可能达到最大，但节点总数较少，综合下来整个建堆过程的复杂度是线性的。

排序复杂度

在完成堆的构建后，堆排序算法不断移除堆顶元素，将其与最后一个元素交换，并重新调整堆的结构。每次调整堆的复杂度是O(log n)，总共需要进行n-1次调整。因此，排序过程的时间复杂度是O(n log n)。

综合以上两个部分，堆排序的总体时间复杂度为O(n log n)。

空间复杂度

堆排序是一种原地排序算法，除了输入数组外，它只需要固定的额外空间（用于交换元素），因此空间复杂度为O(1)。

3.3.2注意事项

建堆与排序顺序的关系

大顶堆与升序排序：在大顶堆中，根节点是所有节点中的最大值。当使用大顶堆进行排序时，通过将根节点（最大值）与数组的末尾元素交换，然后重新调整剩余元素为大顶堆，可以实现升序排序。这是因为每次都将当前最大的元素放到了其最终位置。
小顶堆与降序排序：相反地，小顶堆中根节点是所有节点中的最小值。使用小顶堆进行排序并以相同的方式交换根节点和数组末尾元素，则可以实现降序排序，每次都将当前最小的元素移至其最终位置。

注意事项

非稳定性：堆排序是一种非稳定排序算法。在排序过程中，等值的元素可能会改变其原始相对顺序。
内存访问模式：堆排序的内存访问模式可能不如其他排序算法（如快速排序和归并排序）连续，这可能对缓存性能产生一定的影响，特别是在处理大数据集时。
原地排序：尽管堆排序是原地排序，但其不稳定的特性意味着它可能不适合需要稳定排序的应用场景。

4.小结

本篇文章介绍了排序算法的基础知识，包括插入排序、选择排序及其变种，如直接插入排序和希尔排序，以及直接选择排序和堆排序。我们讨论了每种算法的原理、性能和适用场景，为理解它们提供了坚实的基础。接下来，在C语言数据结构——常见排序算法（二）中，我们将继续探索其他高效的排序技术，如交换排序、归并排序和非比较排序等等，以全面掌握排序算法在数据处理中的应用。