C语言：冒泡排序，选择排序，插入排序，希尔排序，堆排序，快速排序，归并排序，计数排序

本文链接：https://blog.csdn.net/Lvision2/article/details/137001135

本文详细介绍了八种常见的排序算法：冒泡排序、选择排序、插入排序、希尔排序、堆排序（包括小顶堆和大顶堆）、快速排序（Hoare版本、挖坑法、非递归法）、归并排序以及计数排序，分析了它们的时间复杂度、稳定性，并提供了相应的示例代码。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

文章目录

1. 冒泡排序

请添加图片描述

分析：如果左边小于右边，就会执行一次交换。遍历n(数组长度)次数组，每次遍历n - -个数（第一次遍历 0~n-1，第二次遍历 0 ~ n-2 ,直到遍历 0~0），每一次遍历数组造成的效果都会把遍历范围的最大值交换至范围的最后

最好情况： O(n)

最坏情况 : O(n^2)

稳定性：稳定

示例代码：

void BubbleSort(int* arr, int n)
{
   
	int end = n - 1;
	while (end)
	{
   
		int flag = 1;
		for (int i = 1; i <= end; i++)
		{
   
			if (arr[i] < arr[i - 1])
			{
   
				int tmp = arr[i];
				arr[i] = arr[i - 1];
				arr[i - 1] = tmp;
				flag = 0;
			}
		}
		if (flag) break;
		end--;
	}
}

2. 选择排序

请添加图片描述
分析：以 i 下标为开始，选择其后数中最小的数，在 i 处与选择的最小数坐标进行交换。

最好情况： O(n ^2)

最坏情况： O(n ^2)

稳定性：不稳定
例如 3 3 1 1 能保证 1 的稳定性，但是无法保证 3 的稳定性，会跨数的交换会破坏稳定性

示例代码：
(与图示不同，是双指针法，在 begin ~ end 的范围内，选择最大数下标与end交换，最小数下标与 begin交换。)

void SelectSort(int* arr, int n)
{
   
	int end = n - 1;
	while (end)
	{
   
		int maxi = 0;
		for (int i = 0; i <= end; i++)
		{
   
			if (arr[maxi] < arr[i]) maxi = i;
		}
		Swap(&arr[maxi], &arr[end]);
		end--;
	}
}

3. 插入排序

请添加图片描述
分析：在 0 ~ i-1 的范围内，设 end = i ,记录 key = arr [ i ] 并且向前遍历，如果 arr[end] > arr[ i ] 则令 arr[end+1] = arr[end] (即令其 end 下表的数覆盖至 end+1 下标的数)，否则停止遍历，并且令此时的arr[end] = key

最好情况： O(n) – 此时待排序列为逆序，或者说接近逆序

最坏情况 : O(n^2) – 此时待排序列为升序，或者说接近升序

稳定性：稳定

示例代码：

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