上篇：《排序算法的奇妙世界：如何让数据井然有序？》

个人主页：strive-debug

排序算法精讲：从理论到实践

 一、排序概念及应用

 1.1 基本概念  

**排序**：将一组记录按照特定关键字（如数值大小）进行递增或递减排列的操作。

 1.2 常见排序算法分类

 
- **简单低效型**：直接插入排序、冒泡排序、选择排序  
- **高效优化型**：希尔排序、快速排序、归并排序、堆排序  

---

二、基础排序算法实现

 2.1 插入排序家族

 2.1.1 直接插入排序

核心思想：将待排元素逐个插入已有序序列中。  

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

我的理解（如图所示）：

**特性分析**：  
 **接近有序时效率高**  
 时间复杂度：O(N^2)
 空间复杂度：O(1)

 2.1.2 希尔排序（优化版插入排序）

**优化策略**：通过分组增量（gap）预排序逐步逼近全局有序。  

void ShellSort(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//推荐写法：除3
		gap = gap / 3 + 1;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if(arr[end] > tmp)
				{ 
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;
		}
	}
}

我的理解（如图所示）：

**特性分析**：  
 **突破O(N^2)的时间瓶颈**  
 时间复杂度：约 O(N^{1.3}) 
 空间复杂度：O(1)

---

2.2 选择排序

直接选择排序
**核心思想**：每轮选取最小/最大值固定到序列两端。  

void SelectSort(int* arr, int n)
{
	int begin = 0, end = n - 1;
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		for (int i = begin; i <= end; i++)//end=n-1,不是n
		{
			if (arr[i] > arr[maxi])
			{
				maxi = i;//不是arr[i]
			}
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
		}
		//要先判断如果maxi在开头的话，就是发生来回替换的情况
		if (maxi == begin)
		{
			maxi = mini;
		}
		//循序不能乱
		Swap(&arr[mini], &arr[begin]);
		Swap(&arr[maxi], &arr[end]);
		//不要忘记让end和begin，这是一个while循环
		end--;
		begin++;
	}
}

我的理解（如图所示）：

---

 2.3 交换排序

冒泡排序
经典实现+提前终止优化：  
 

void BubbleSort(int* arr, int n)
{
	int exchange = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				exchange = 1;
				Swap(&arr[j], &arr[j + 1]);
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}

**适用场景**：  
 **教学演示为主，实际工程较少使用**  
 时间复杂度：O(N^2)  

---

三、算法对比总结

| 算法         | 时间复杂度       | 空间复杂度 | 稳定性 | 适用场景             |
|--------------|------------------|------------|--------|------------------------|
| 直接插入排序 |O(N^2)      | O(1)   | ✔️      | 小规模或接近有序数据   |
| 希尔排序        |O(N^{1.3}) |O(1)    | ✖️      | 中等规模数据                 |
| 选择排序        |O(N^2)      | O(1)   | ✖️      | 教学演示                         |
| 冒泡排序        |O(N^2)      | O(1)   | ✔️      | 理解交换思想                 |

---

 **四、下篇预告**
**《高阶排序算法：分治思想与性能突破》**  
-  **快速排序的三种分区策略**  
-  **归并排序的递归与非递归实现**  
-  **堆排序与优先队列的深度关联**

---