【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解

温馨提示：这篇文章已超过469天没有更新，请注意相关的内容是否还可用！

摘要：本文详细介绍了数据结构中的排序算法，以C语言为编程基础。文章涵盖了各种排序方法，包括冒泡排序、选择排序、插入排序、快速排序等。本文不仅解释了每种排序算法的原理，还提供了相应的C语言实现代码。通过阅读本文，读者可以了解排序算法的基本概念和实现方法，为在实际编程中应用排序算法提供有力的支持。

文章目录

前言

一、排序的概念

1.1 排序的概念

1.2 常见的排序算法

二、插入排序

2.1 直接插入排序

2.1.1 基本思想

2.1.2 特性总结

2.1.3 代码实现

2.2 希尔排序

2.2.1 基本思想

2.2.2 特性总结

2.2.3 代码实现

三、选择排序

3.1 直接选择排序

3.1.1 基本思想

3.1.2 特性总结

3.1.3 代码实现

3.2 堆排序

3.2.1 基本思想

3.2.2 特性总结

3.2.3 代码实现

四、交换排序

4.1 冒泡排序

4.1.1 基本思想

4.1.2 特性总结

4.1.3 代码实现

4.2 快速排序

4.2.1 基本思想

4.2.2 特性总结

4.2.3 代码实现

五、归并排序

5.1 归并排序

5.1.1 基本思想

5.1.2 特征总结

5.1.3 代码实现

六、计数排序

6.1 计数排序

6.1.1 基本思想

6.1.2 特征总结

6.1.3 代码实现

七、排序比较

总结

前言

在当今信息爆炸的时代，数据量不断攀升，排序算法作为处理数据的核心技术，其在计算机科学、大数据、人工智能等领域的重要性不言而喻。本文旨在介绍各种排序算法，帮助读者掌握其原理、特点及适用场景，从而提高数据处理效率，提升系统性能。

本文将详细介绍常见的排序算法，包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等，并分析各种排序算法的时间复杂度、空间复杂度和稳定性，让你在实际应用中能够灵活选择合适的排序方法。

一、排序的概念

1.1 排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第1张

二、插入排序

2.1 直接插入排序

2.1.1 基本思想

直接插入排序（Insertion Sort）是一种简单直观的排序算法。它的基本思想是将待排序的序列分为已排序和未排序两部分，在每一趟排序中，从未排序的部分中选择一个元素，然后将其插入到已排序的部分中的正确位置，直到所有元素都被插入到已排序的部分中。

具体的步骤如下：

将序列的第一个元素看作已排序的部分，剩余部分看作未排序的部分。
从未排序的部分中选取一个元素，依次与已排序的部分中的元素进行比较，找到合适的位置插入。
插入元素时，需要将已排序的部分中比插入元素大的元素依次向后移动一个位置，给插入元素腾出位置。
重复步骤2和步骤3，直到所有元素都插入到已排序的部分中。

直接插入排序的时间复杂度为O(n^2)，其中n为待排序序列的长度。它是稳定的排序算法，适用于小规模的数据或基本有序的数据。在实际应用中，当待排序序列规模较小或已经基本有序时，直接插入排序是一个简单有效的选择。

【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第2张

2.1.2 特性总结

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

2.1.3 代码实现

void InsertSort(int* a, int n)
{
	for (int i = 0; i = 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

2.2 希尔排序

2.2.1 基本思想

希尔排序是一种排序算法，通过将待排序的数组分割成若干个子序列进行插入排序，从而达到整体有序的目的。它是插入排序的改进版，也被称为缩小增量排序。

希尔排序的基本思想是：对数组进行分组，按一定的间隔（增量）将元素分为若干个子序列，对每个子序列进行插入排序，然后减小增量再次分组并排序，直到增量为1时，进行最后的插入排序。

具体的步骤如下：

选择一个增量序列，通常初始增量为数组长度的一半，之后依次减半，直到增量为1。
对于每个增量，将数组分成若干个长度为增量的子序列。
对每个子序列进行插入排序。
缩小增量，重复步骤2和3，直到增量为1。
最后进行一次插入排序，完成排序。

希尔排序的时间复杂度和增量序列的选择有关，但最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^1.3)。相比于插入排序的O(n^2)时间复杂度，希尔排序有较好的性能。

希尔排序是一种原地排序算法，不需要额外的空间，因此它的空间复杂度为O(1)。但它不稳定，相同元素可能会被交换位置，因此对于有重复元素的数组，可能需要考虑其他的排序算法。

【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第3张

2.2.2 特性总结

1. 希尔排序是对直接插入排序的优化。

2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定：

【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第4张

因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照： $【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第5张$ 到 $【数据结构（C语言）】排序详解，数据结构（C语言）之排序算法详解第6张$ 来算。

4. 稳定性：不稳定

2.2.3 代码实现

//平均O(n^1.3)
void ShellSort(int* a, int n)
{
	int gap = n;
	// gap > 1时是预排序，目的让他接近有序
	// gap == 1是直接插入排序，目的是让他有序
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i = 0)
			{
				if (tmp  1)
	{
		gap = gap / 3 + 1;
		for (int j = 0; j = 0)
				{
					if (tmp  
 
三、选择排序 
3.1 直接选择排序 
3.1.1 基本思想 
选择排序是一种简单直观的排序算法，它的基本思想是每次从待排序的数组中选择最小（或最大）的元素，放到已排序部分的末尾，直到整个数组有序为止。 
具体的步骤如下： 
遍历数组，从第一个元素开始，将其标记为最小元素。
在剩下的待排序部分中，找到最小的元素，并将其与待排序部分的第一个元素交换位置。
指针向后移动一位，进入下一轮遍历，重复步骤2，直到遍历完整个数组。
选择排序的时间复杂度为O(n^2)，其中n为数组的长度。无论原始数组是否有序，每次都需要遍历剩余的待排序部分来找到最小元素，因此时间复杂度较高。 
选择排序是一种原地排序算法，它只需要常数级的额外空间来存储交换时的临时变量，因此空间复杂度为O(1)。 
选择排序是一种不稳定的排序算法，因为交换元素的位置可能会改变相同元素的相对顺序。例如，对于序列[5, 5, 2]，第一轮选择排序后，第一个5会与2交换位置，导致相同元素的顺序改变。 
尽管选择排序的性能不如快速排序、归并排序等高级排序算法，但它简单易懂，实现起来较为简单，适用于小规模的数据排序或作为其他高级排序算法的辅助排序步骤。 
 
3.1.2 特性总结 
直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定
3.1.3 代码实现 
void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//优化了一步，一次选两个，一个最大，一个最小
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;
	while(begin  
3.2 堆排序 
3.2.1 基本思想 
堆排序是一种基于完全二叉堆的排序算法。它的基本思想是通过将待排序的数组看作是一个完全二叉树，并将其转化为一个最大堆或最小堆。然后，每次将堆顶元素与堆的最后一个元素交换位置，然后调整堆，使得剩余元素满足堆的性质。重复这个过程，直到整个数组有序为止。 
具体的步骤如下： 
将待排序的数组构建成一个最大堆或最小堆。
交换堆顶元素与堆的最后一个元素，然后将剩余元素调整为一个新的堆。
重复步骤2，直到堆的大小为1，则整个数组有序。
堆排序的时间复杂度为O(nlogn)，其中n为数组的长度。构建堆的过程需要O(n)的时间复杂度，而每次调整堆的时间复杂度为O(logn)，总共需要进行n-1次交换和调整操作。 
堆排序是一种原地排序算法，它只需要常数级别的额外空间来存储交换时的临时变量，因此空间复杂度为O(1)。 
堆排序是一种不稳定的排序算法，因为交换堆顶元素与最后一个元素可能会改变相同元素的相对顺序。 
虽然堆排序的时间复杂度较低，但它的常数项较大，而且在实际应用中不如快速排序或归并排序常用，一般用于特定场景或作为其他排序算法的辅助排序步骤。 
 
3.2.2 特性总结 
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定
3.2.3 代码实现 
void Swap(int* p1, int* p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}
void AdjustDown(int* a, int size, int parent) //这里的size表示最后要建成的最终形态的堆的大小
{
	int child = parent * 2 + 1;
	while (child  a[child])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = n - 1; i > 0; i--)
	{
		Swap(&a[0], &a[i]);
		AdjustDown(a, i, 0);
	}
}
 四、交换排序
4.1 冒泡排序
4.1.1 基本思想
冒泡排序是一种简单的排序算法，它重复地遍历待排序数组，每次比较相邻的两个元素，并将较大（或较小）的元素交换到右侧。通过多次遍历，最大（或最小）的元素会逐渐移动到右侧，实现排序的目的。
具体的步骤如下：
从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素大于（或小于）后一个元素，则交换它们的位置。
继续遍历剩下的元素，进行相同的比较和交换操作，直到遍历完整个数组。
重复上述步骤，每次遍历都会将当前最大（或最小）的元素移动到右侧。
重复执行n-1次遍历，直到所有元素都有序排列。
冒泡排序的时间复杂度为O(n^2)，其中n为数组的长度。每次遍历需要比较n-1次，并且最多需要执行n-1次遍历。
冒泡排序是一种原地排序算法，它只需要常数级别的额外空间来存储交换时的临时变量，因此空间复杂度为O(1)。
冒泡排序是一种稳定的排序算法，因为在相邻元素比较时，只有前一个元素大于（或小于）后一个元素时才会交换它们的位置。
尽管冒泡排序的时间复杂度较高，但它的实现简单，适用于小规模的数据排序。在实际应用中，由于其性能较差，常常被其他高效的排序算法取代。

4.1.2 特性总结
冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定
4.1.3 代码实现
 void swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void BubbleSort(int* a, int n)
{
	for (int j = 0; j  a[i + 1])
			{
				swap(&a[i], &a[i + 1]);
				exchange = true;
			}
		}
		if (exchange == false)
		{
			break;
		}
	}
}
 4.2 快速排序
4.2.1 基本思想
快速排序是一种常用的排序算法，它采用分治的思想将数据分成较小和较大的两部分，然后递归地对两部分进行排序。
具体的步骤如下（hoare版本）：
选择一个基准元素（pivot），通常选择数组的第一个或最后一个元素。
将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。可以使用两个指针分别从数组的左右两端开始遍历，当左指针指向的元素大于基准元素，右指针指向的元素小于基准元素时，交换它们的位置。
递归地对左右两部分进行排序，直到每个部分只有一个元素或为空。
合并排序后的左右部分，即可得到完整的有序数组。
快速排序的时间复杂度平均为O(nlogn)，其中n为数组的长度。每次排序都会将数组分成大致等长的两部分，因此分治的次数为logn，而每次分治需要遍历n个元素，所以时间复杂度为nlogn。最坏情况下的时间复杂度为O(n^2)，当数组已经有序或近乎有序时，每次分治只能得到一个元素，导致分治次数为n，时间复杂度变为n的平方。
快速排序是一种原地排序算法，它只需要常数级别的额外空间来存储分治时的临时变量，因此空间复杂度为O(1)。
快速排序是一种不稳定的排序算法，因为在交换元素时可能改变相同元素的相对顺序。
快速排序是一种高效的排序算法，常被用于大规模数据的排序。它的实现相对较复杂，但其时间复杂度的平均性能优势使其成为了主流的排序算法之一。
 前后指针版本 4.2.2 特性总结
1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
4.2.3 代码实现
 void Swap(int* p1, int* p2)
{
	int t = *p1;
	*p1 = *p2;
	*p2 = t;
}
int GetMidi(int* a, int begin, int end)
{
	int midi = (begin + end) / 2;
	//begin midi end 三个数取中
	if (a[begin]  a[end])
			return begin;
		else
			return end;
	}
	else // a[begin] > a[midi]
	{
		if (a[midi] > a[end])
			return midi;
		else if (a[begin] = a[keyi])
		{
			right--;
		}
		while (left