轻松理解七大排序算法（C语言实现）

1. 冒泡排序

基本思想：

时间复杂度：

优化：

代码展示：

特性总结：

2. 直接插入排序

基本思想：

时间复杂度：

代码实现：

特性总结：

3. 简单选择排序

基本思想：

时间复杂度：

代码实现：

特性总结：

4. 希尔排序(缩小增量排序)

基本思想：

时间复杂度：

代码展示：

特性总结：

5. 堆排序

基本思想：

时间复杂度：

代码实现：

特性总结：

6. 快速排序

6.1 递归版

基本思想：

时间复杂度：

Hore法：

挖坑法：

双指针法：

6.2 非递归版

7. 归并排序

基本思想：

时间复杂度：

代码展示：

特性总结：

排序算法复杂度分析及稳定性分析：

通过动画可视化数据结构和算法<br> - VisuAlgo 这里先给大家推荐个网站，在这个网站上，你可以看到数据结构及算法各种实现的动图，方便你更好的学习。

为了更简单的描述和理解，我们都是用数组来实现八中算法。

1. 冒泡排序

基本思想：

两两比较相邻记录的关键字，如果反序就交换，知道没有反序的记录为止。简单理解就是，我们一次排序，都是将较大/小的数据往后移，直到数组末尾，就向可乐中的气泡一样，往上冒。

对于冒泡排序，我们也只是在学习过程中会用到，在实际应用中，我们很少会运用，因为它的效率是在太低了。

排序（冒泡排序，选择排序，插入排序，归并排序，快速排序，计数排序，基数排序） - VisuAlgo

时间复杂度：

最坏情况：O(N^2) 。如果数组是反序的，那么每次排序都需要执行N-1次，一共有N个数，所以这是一个等差数列相加，得出结果就是O(N^2)

平均情况：O(N^2)

最好情况：O(N) 。如果数组基本有序，那么每次排序只需要执行O(1)次，遍历一遍数组就能将数组排好序。这里的基本有序是指，小的数据元素基本放在前面，大的数据元素基本在后面，不大不小的基本在中间。

优化：

如果我们排完一趟之后，发现没有交换，说有数组已经有序了，就没必要往交换了，结束排序就可以了。

代码展示：

void BubbleSort(int* a, int size)
{
	for (int i = 0;i < size - 1;i++)
	{
		bool change = false;
		for (int j = 0;j < size - 1 - i;j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				change = true;
			}
		}
		if (change == false)
		{
			break;
		}
	}
}

特性总结：

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：稳定

2. 直接插入排序

基本思想：

将一个记录插入到已经排好序的有序表中，从而得到一个新的，记录增1的有序表。我们将第一个元素看做是一个排好序的有序表，将第1个与第2个进行比较，将两个元素组成一个新的升/降序有序表，以此类推...

时间复杂度：

最坏情况：O(N ^ 2) ，如果这个数组反序的，那么每一次都需将将有序表后一个元素，插入到最前面，这是一个等差数列相加，得出结果为 N^2.

平均情况：O(N ^ 2)

最好情况：O(N)，若果数组是基本有序的，那么每次排序只需要O(1),一共执行N次，得出结果为N

代码实现：

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

特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1) ，它是一种稳定的排序算法

4. 稳定性：稳定

3. 简单选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

时间复杂度：

最坏情况; O(N ^ 2)

平均情况：O(N ^ 2)

最好情况：O(N ^ 2) , 对于选择排序来说每一次排序就是从N个数中选择最小/大的数放在第一个位置，再选出第二小/大的数放在第一个位置，以此类推，总共执行N-1次。所以对于选择排序，不管什么情况都是 O(n ^ 2)

这里可能有人会觉得，简单选择排序不管什么情况都是N^2 ,所以它的时间复杂度是最高的，其实，在实际排序中，冒泡是最慢的，这里它们时间复杂度都是O(N ^2)只能说明它们属于同一个量级的，并不能直接代表孰优孰劣。

代码实现：

void SelectSort(int* a, int size)
{
	for (int i = 0;i < size-1;i++)
	{
		int mini = i;
 		for (int j = i + 1;j < size;j++)
		{
			if (a[mini] > a[j])
			{
				mini = j;
			}
		}
		Swap(&a[mini], &a[i]);
	}
}

//优化
void SelectSort(int* a, int size)
{
	int begin = 0;
	int end = size - 1;

	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin;i <= end;i++)
		{
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
			if (a[i] < a[mini])
			{
				mini = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		if (maxi == begin)
		{
			maxi = mini;
		}
		Swap(&a[end], &a[maxi]);

		begin++;
		end--;
	}
}

上述代码，我们将选择排序进行了优化，即一次排序过程中，我们既选出最大值，也选出最小值，将最大值放在后面，最小值放在前面。

特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用

2. 时间复杂度： O(N^2)

3. 空间复杂度： O(1)

4. 稳定性：不稳定

4. 希尔排序(缩小增量排序)

void ShellSort(int* a, int size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0;i < size - gap;i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}

基本思想：

先选定一个整数，把待排序数组中所有记录分成组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后， 重复上述分组和排序的工 作。当到达N =1 时，所有记录在统一组内排好序 。

时间复杂度：

希尔排序的时间复杂度并不好计算，因为gap的取值目前并没有得出最优结果，许多业内大佬也没有计算出，因为我们的gap是由Knuth踢出的方式取值的，而且Knuth进行了大量的实验统计，所以本文就咱是按照：O(N ^ 1.25) 到 O(1.6 * N^ 1.25)来计算。

代码展示：

void ShellSort(int* a, int size)
{
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0;i < size - gap;i++)
		{
			int end = i;
			int temp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > temp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = temp;
		}
	}
}

特性总结：

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

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

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

4. 稳定性：不稳定

5. 堆排序

二叉树——堆（C语言，配图，例题详解，TopK问题+堆排序）-CSDN博客

堆排序是基于数据结构中堆的概念来实现的，如果你对堆不太熟悉，可以从这篇文章中学习了解什么是堆。

简单来说，堆就是上图所示的二叉树（每个节点最多有两个孩子节点），其父节点总是大于/小于孩子节点。

根据堆的概念，我们可以得出，第一层节点（根节点）总是最大的，我们只需要将根节点与最后一个节点交换，调整根节点至合适位置，这就是调堆的过程，再将堆的大小-1，直到堆中没有节点。

基本思想：

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

时间复杂度：

最坏情况：O(N*logN)

平均情况：O(N*logN)

最好情况：O(N*logN) ，堆排序就是一个建堆，并不断调堆的过程，即便对有重复数据的序列排序时，依然具有不错的效率。

代码实现：

void HeapSort(int* a, int size)
{
	//建堆
	for (int i = (size - 2) / 2;i >= 0;i--)
	{
		AdjustDown(a, i, size);
	}

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

特性总结：

1. 堆排序使用堆来

2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(1)

4. 稳定性：不稳定

6. 快速排序

6.1 递归版

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。它的方法就是，每次选出来一个数，都将这个数放在排完序后应该在的位置。

例如：6 3 9 7进行排序，我们选择6，进行一次排序后，序列为， 3 , 6 , 9 , 7，此时6所在的位置就是排完序后应该在的位置。

基本思想：

通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别堆这两部分记录继续进行排序，以达到整个序列有序的目的。

即每次选出一个数据，以它为中介 key，小于key的数据放在左面，大于key的放在右面，在分别对两边进行快速排序，以做到整体有序。

时间复杂度：

最坏情况：O(N^2)，对于整个序列基本有序，每次分割只比上一次少一个，仍要执行N-1次，所以时间复杂度达到N^2, 所以快速排序不适合对于有重复项的序列进行排。

平均情况：O(N * log N)

最好情况：O(N * logN)，对于最好情况，我们每次选出来的key都是中位数，即左右两边的数据个数相等，一共有logN层，每层我们都简单认为是N个数，所以时间复杂度是 N * logN。这也是快速排序的一种优化，即选择中位数。

void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int key = _PartSort(a,begin,end);

	QuickSort(a, begin, key - 1);
	QuickSort(a, key + 1, end);
}

这里_PartSort函数的意思是进行一趟排序，返回中位数的小标，在对中位数的两边进行递归，进行排序，知道只有1个数或者没有数据时，结束递归。

这里_Partsort函数有三种实现方法，首先我们来看一下创作者Hore的原始方法。

Hore法：

int _PartSort1(int* a, int left, int right)
{
	//三位数取中位数
	int mid = GetMiddle(a, left, right);
	Swap(&a[left], &a[mid]);
	int keyi = left;

	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[left], &a[keyi]);
	keyi = left;
	return keyi;
}

对于Hore法，原理是，先从左边right开始，找出比key位置数据小的元素，再从左边left开始，找出比key位置数据大的元素，交换right 和 left 下标位置的元素。

当left >= right的时候结束循环，此时left 和 right 相遇，相遇点就是key位置数据应该在的位置。交换left下标和left下标位置的数据，此时key左边的元素都比key下标的位置元素小，右边都比它大。

这里有个你是否有个疑问？为什么要从右边开始：

这里先说个结论，如果使用Hore法，并且选择的数是在左边，一定要先从右边开始。如果你选择的数在右边，一定要在左边开始。

以第一种方法为例，选择的数在左边，从右边开始，会有两种情况：

1. right 遇到 left ，这里能保证left之后的数都是大于key下标的数据。

2. right 遇到 key，结束循环。

如果先从左边开始，当left遇到right时，如果交换key 和 left下标位置数据，则将大于key下标位置数据的元素放在序列之前。

挖坑法：

如果你自己写了一遍Hore法的快速排序的话，你一定会发现，是在有太多要注意的了，例如为什么要先从左边或者右边开始等等。所以就有人想了个更好的解释方法，对Hore法进行改进，使得逻辑看起来更加合理，当然不管哪种方法，时间复杂度都是一样的，并没有什么本质的区别。

int _PartSort2(int* a, int left, int right)
{
	//三位数取中位数
	int mid = GetMiddle(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = a[left];
	int hore = left;
	while (left < right)
	{
		while (left < right && a[right] >= key)
		{
			right--;
		}
		Swap(&a[hore], &a[right]);
		hore = right;
		while (left < right && a[left] <= key)
		{
			left++;
		}
		Swap(&a[hore], &a[left]);
		hore = left;
	}
	a[hore] = key;
	return hore;
}

挖坑法就是值，取出第一个位置的值key，挖个坑，从右边开始，找到比key小的，放在坑里面，再将坑放在后面；再从左边开始，找到比key大的，放在坑里面。以此类推，知道left和right相遇。

双指针法：

双指针法，是我们平常使用最多的一种方法。当然如果你熟练掌握这三种方法，这对你来收并没有什么。

int _PartSort3(int* a, int left, int right)
{
	//三位数取中位数
	int mid = GetMiddle(a, left, right);
	Swap(&a[left], &a[mid]);
	int key = left;
	int prev = key;
	int cur = prev + 1;
	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev <= right)
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	Swap(&a[prev], &a[key]);
	key = prev;
	return key;
}

cur下标从prev+1开始，找到比key下标位置数据大的就+1,比它小的就和prev+1位置的数据相互交换。知道cur找完序列，再将key下标位置的数据和prev数据交换，此时key下标数据找到最终位置。

6.2 非递归版

对于递归的实现，我们通常有另外两种方法：

1. 迭代

2. 数据结构中的 ——栈

因为栈的原理和递归原理相同，所以我们通常会用数据结构中的栈来模拟实现递归，如果你对栈没有详细的了解，可以参考下面这篇文章。

数据结构入门————栈和队列（C语言/零基础/小白/新手+模拟实现+例题讲解）-CSDN博客

因为篇幅的限制，所以下面代码涉及的栈的实现，初始化等操作都并没有展示，如果感兴趣，可以阅读上面这篇文章。

void QuickSortNonR(int* a, int begin,int end)
{
	ST stack;
	//初始化
	StackInit(&stack);

	StackPush(&stack, end);
	StackPush(&stack, begin);

	//栈 不为 空
	while (!StackEmpty(&stack))
	{
		int left = StackTop(&stack);
		StackPop(&stack);
		int right = StackTop(&stack);
		StackPop(&stack);

		int key = _PartSort3(a, left, right);
		

		if (left < key - 1)
		{
			StackPush(&stack, key - 1);
			StackPush(&stack, left);
		}

		if (key + 1 < right)
		{
			StackPush(&stack, right);
			StackPush(&stack, key + 1);
		}
	}

	//销毁
	StackDestroy(&stack);
}

这里我们先将区间入栈，每次排序都将区间出栈，如果满足条件就将区间入栈，知道栈为空。

例如：3 , 5 , 6 , 1 , 2 、

1）. 第一次，将 5 和 0 入栈，注意这里是下标，即区间，然后排序，得出序列 2，1 , 3 , 6 , 5，得到中位数。

2）. 以此可以划分区间【0,1】和【3,4】。再次出栈，取出区间进行排序。

3）. 如果两端还能继续划分满足条件，就入栈，这里不满足条件。栈中剩下3 和 4 ，再次出栈，进行排序，直至栈为空。

7. 归并排序

基本思想：

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

时间复杂度：

最坏情况：O(N * logN)

平均情况：O(N * logN)

最坏情况：O(N * logN)

对于归并排序，每次都需要递归值logN层，每层总共有N个节点，所以时间复杂度为N * logN

代码展示：

void _MergeSort(int* a, int begin, int end,int* temp)
{
	if (begin >= end)
	{
		return;
	}

	//分割
	int mid = begin + (end - begin) / 2;
	_MergeSort(a, begin, mid,temp);
	_MergeSort(a, mid + 1, end,temp);

	//合并
	int i = begin;
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] < a[begin2])
		{
			temp[i++] = a[begin1++];
		}
		else
		{
			temp[i++] = a[begin2++];
		}
	}

	while (begin1 <= end1)
	{
		temp[i++] = a[begin1++];
	}

	while (begin2 <= end2)
	{
		temp[i++] = a[begin2++];
	}

	memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));
	
}

void MergeSort(int* a, int size)
{
	//创建辅助空间
	int* temp = (int*)malloc(sizeof(int) * size);

	//排序
	_MergeSort(a, 0, size - 1, temp);

	free(temp);
}