目录
⬇点击下方即可跳转⬇
各个排序算法动态演示效果
一. 冒泡排序
冒泡排序（Bubble Sort）是一种简单的比较排序算法，其核心思想是通过多次遍历数组，相邻元素两两比较并交换，将较大的元素逐步“冒泡”到数组末尾。
核心思想：
1. 外层循环：控制排序的轮数（共需要n-1轮，n为数组长度）。
2. 内层循环：在每一轮中比较相邻的两个元素，如果前一个的元素比后一个元素大，则交换位置。
3. 优化：如果在某一轮内层循环中没有发生任何交换，则说明数组已有序，提前退出排序。
代码实现：
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
//冒泡排序
void BubbleSort(int* arr, int n)
{
for (int i = 0;i < n ;i++)
{
int flag = 0;
for (int j = 0;j < n -i - 1;j++)
{
if (arr[j]>arr[j+1])
{
flag = 1;
Swap(&arr[j], &arr[j + 1]);
}
}
if (flag == 0)
break;
}
}
动图演示：
特点分析：
- 时间复杂度：
最好情况（有序数组）：O(n)。
最坏情况（逆序数组）：O(n2)。
平均情况：O(n2)。- 空间复杂度：O(1)。
- 稳定性：稳定（相对顺序不变）。
二. 插入排序
插入排序（Insertion Sort）是一种简单直观的基于比较的排序算法，其核心思想是通过构建有序序列，逐步将未排序部分的元素插入到已排序部分的正确位置。
核心思想：
插入排序的工作方式就像许多人排序一手扑克牌：
1. 开始时，你左手是空的，所有牌都背面朝上放在桌上（未排序序列）。
2. 你从桌上拿起一张牌（当前要插入的元素，称为 Key），放到左手。
3. 之后，你从桌上拿起下一张牌，将它从右到左与左手中已有的每张牌进行比较，找到它正确的位置并插入。
4. 重复第3步，直到桌上的所有牌都被拿到左手。此时，左手中的牌就是有序的。
将待排序的元素逐个插入到一个已经排好序的序列中的正确位置，直到所有元素都插入完毕。
代码实现：
void InserSort(int* arr, int n)
{
for (int i = 0;i < n - 1;i++)
{
int end = i;
int key = arr[end + 1];
while (end >= 0 && arr[end] > key)
{
arr[end + 1] = arr[end];
end--;
}
arr[end + 1] = key;
}
}
动图演示：
特点分析：
- 时间复杂度：
最好情况：O(n)。
最坏情况：O(n2)。
平均情况：O(n2)。- 空间复杂度：O(1)。
- 稳定性：稳定（比较arr[end] > key时，使用的
>而不是>=,保证了相等元素的相对顺序不变）。
三. 希尔排序
希尔排序（Shell Sort），它是插入排序的一种高效改进版本。
核心思想
- 对元素进行分组插入排序，随着增量逐渐减小，整个数组也越来越接近有序状态，当增量为1时，就是标准的插入排序，但此时数组已经基本有序，所以效率很高。
- 希尔排序会先每隔几个位置比较一次，让数组大致有序，然后再用标准的插入排序来调整成有序数组。
代码实现：
void ShellSort(int* arr, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0;i < n - gap;i++)
{
int end = i;
int tmp = arr[end + gap];
while (end >= 0 && arr[end] > tmp)
{
arr[end + gap] = arr[end];
end -= gap;
}
arr[end + gap] = tmp;
}
}
}
动图演示：
特点分析：
- 时间复杂度：
最好情况：O(n1.3)。
最坏情况：O(n2)。
平均情况：O(n logn)~O(n2)。- 空间复杂度：O(1)。
- 稳定性：不稳定，在排序过程中相等元素的相对位置会被改变。
四. 选择排序
1. 选择排序（Selection Sort）
核心思想：
1. 每次从未排序部分选择最小（或最大）的元素放到已排序部分的末尾。
代码实现：
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
void SelectSort(int* arr, int n)
{
for (int i = 0;i < n;i++)
{
int key = i;
for (int j = i + 1;j < n;j++)
{
if (arr[j] < arr[key])
{
key= j;
}
}
Swap(&arr[key], &arr[i]);
}
}
动图演示：
特点分析：
- 时间复杂度：
最好情况：O(n2)。
最坏情况：O(n2)。
平均情况：O(n2)。- 空间复杂度：O(1)。
- 稳定性：不稳定。交换操作可能改变相等元素的相对顺序（[2 , 2 , 1]排序后第一个2会与1交换位置）。
2. 优化版选择排序（双向选择排序）
- 在选择排序上的优化，在每次遍历中同时找最大值和最小值，并将最小值放在数组的开头，最大值放在数组的末尾，从而减少遍历次数。
核心思想：
1. 定义begin 和 end 分别表示当前未排序部分的起始和结束位置。
2. 在[begin , end]范围内同时查找最小值（mini）和最大值（maxi）。
3. 将mini的值交换到begin,maxi的值交换到end。
4. begin++ 和 end–，缩小未排序范围，直到begin >= end，完成排序
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
void SelectSort2(int* arr, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = begin;
for (int i = begin + 1;i <= end;i++)
{
if (arr[i] < arr[mini])
{
mini = i;
}
if (arr[i] > arr[maxi])
{
maxi = i;
}
}
if (maxi == mini)
{
maxi = mini;
}
Swap(&arr[mini], &arr[begin]);
Swap(&arr[maxi], &arr[end]);
begin++;
end--;
}
}
优化效果：
- 双向选择排序的实际运行时间通常比传统选择排序快50%（因为每次遍历处理两个元素）。
- 但是时间复杂度仍是O(n2)。
- 仍然是不稳定排序。
五. 堆排序
堆排序（Heap Sort）是一种基于二叉树数据结构的比较排序算法，它结合了选择排序的思想和堆的高效操作。
核心思想：
1. 将一个无序数组调整成一个大顶堆（或小顶堆）。
2. 反复将对顶数据最大值（或最小值）与堆的最后一个元素交换，并缩小堆的范围。
3. 最终数组按升序（大顶堆）或降序（小顶堆）排列。
代码实现：
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
//向下建堆
void AdjustDown(int* arr,int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{
//找出左右子节点中较大的节点
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
void HeapSort(int* arr, int n)
{
for (int i = (n - 1 - 1) / 2;i >= 0;i--)
{
AdjustDown(arr, i, n);
}
int end = n - 1;
while (end > 0)
{
//交换堆顶和堆尾元素
Swap(&arr[0], &arr[end]);
AdjustDown(arr, 0, end);
end--;
}
}
代码详细步骤：
例：arr[] = {4 ,8 , 3 , 5 , 1}, n = 5;
- 构建大堆 调用向下建堆函数，调整索引1（值8）比左右子树都大。调整索引0（值4）比左子树小（值8），交换4和8，4比5小再交换4和5。数组变为arr[] = {8 , 5 , 3 , 4 , 1};
- 排序过程：
第一次循环：end = 4，交换堆顶和堆尾，通过向下建堆，数组变为arr[] = {5 , 4 , 3 , 1 , 8};
第二次循环：end = 3，交换堆顶和堆尾，通过向下建堆，数组变为arr[] = {4 , 1 , 3 , 5 , 8};
第三次循环：end = 2，交换堆顶和堆尾，通过向下建堆，数组变为arr[] = {3 , 1 , 4 , 5 , 8};
第四次循环：end = 1，交换堆顶和堆尾，通过向下建堆，数组变为arr[] = {1 , 3 , 4 , 5 , 8};
排序完成 arr[1 , 3 , 4 , 5 , 8};
特点分析：
- 时间复杂度：
最好情况：O(n logn)。
最坏情况：O(n logn)。
平均情况：O(n logn)。- 空间复杂度：O(1)。
- 稳定性：不稳定。交换操作可能改变相等元素的相对顺序（[5 , 5 , 2]排序后第一个5会与2交换位置）。
六. 快速排序
快速排序（Quick Sort）是一种基于分治策略的比较排序算法，它通过递归地将数组分成较小的子数组，并分别排序，最终实现整个数组的有序排列。
1. Hoare版本
算法步骤：
- 选择最左边元素作为基准
- 设置左右指针分别指向数组首尾
- 右指针向左找第一个小于基准的元素
- 左指针向右找第一个大于基准的元素
- 交换这两个元素
- 重复直到左右指针相遇
- 将基准与相遇点交换
代码实现：
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int _QuickSort1(int* arr, int left, int right)
{
int keyi = left;
left++;
while (left <= right)
{
//right:从右向左找比基准值要小的
while(arr[right] > arr[keyi])
{
--right;
}
//left:从左向右找比基准值要大的
while(arr[left] < arr[keyi])
{
left++;
}
//left和right交换
if(left<=right)
Swap(&arr[left++], &arr[right--]);
}
//基准值归位
Swap(&arr[keyi], &arr[right]);
return right;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _QuickSort1(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
动图演示：
2. 挖坑法版本
算法步骤：
- 选择基准，留下一个"坑"
- 右指针向左找小于基准的数填到左坑
- 左指针向右找大于基准的数填到右坑
- 重复直到指针相遇
- 将基准填入最后的坑
int _QuickSort2(int* arr, int left, int right)
{
int hole = left;
int key = arr[hole];
while (left < right)
{
while (left < right && arr[right] > key)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] < key)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = key;
return hole;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _QuickSort2(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
动图演示：
3. 双指针版本
算法步骤：
- 选择基准
- 使用两个指针：一个遍历指针，一个分界指针
- 分界指针左边都是小于基准的元素
- 遍历指针扫描整个数组，将小于基准的元素交换到分界指针左边
void Swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int _QuickSort3(int* arr, int left, int right)
{
int prev = left, cur = prev + 1;
int key = left;
while (cur <= right)
{
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[prev], &arr[cur]);
}
cur++;
}
Swap(&arr[prev], &arr[key]);
return prev;
}
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
//找基准值
int keyi = _QuickSort3(arr, left, right);
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
动图演示：
特点分析：
- 时间复杂度：
最好情况：O(n logn)。
最坏情况：O(n2)（每次选择基准值都是最大值和最小值）。
平均情况：O(n logn)。- 空间复杂度：O(logn)。
- 稳定性：三种版本都是不稳定排序。交换操作可能改变相等元素的相对顺序。
7. 归并排序
归并排序（Merge Sort）,采用分治策略的排序算法。
核心思想：
1. 将数组递归地分成两半，直到每个子数组中只有一个元素。
2. 将两个已排序的子数组合并成一个有序的数组。
算法步骤：
- 分解
例：原始数组: [8, 4, 5, 7, 1, 3, 6, 2]
第1次分: [8, 4, 5, 7] 和 [1, 3, 6, 2]
第2次分: [8, 4] [5, 7] 和 [1, 3] [6, 2]
第3次分: [8] [4] [5] [7] [1] [3] [6] [2] ← 单个元素- 第一层合并
[8] 和 [4] → [4, 8]
[5] 和 [7] → [5, 7]
[1] 和 [3] → [1, 3]
[6] 和 [2] → [2, 6]
第二层合并
[4, 8] 和 [5, 7] → [4, 5, 7, 8]
[1, 3] 和 [2, 6] → [1, 2, 3, 6]
第三层合并
[4, 5, 7, 8] 和 [1, 2, 3, 6] → [1, 2, 3, 4, 5, 6, 7, 8]
最终合并成有序的数组。
代码实现：
void _MergeSort(int* arr, int left, int right,int* tmp)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2;
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = left;
while (begin1 <= end1 && begin2 <= end2)
{
if (arr[begin1] < arr[begin2])
{
tmp[index++] = arr[begin1++];
}
else
{
tmp[index++] = arr[begin2++];
}
}
while (begin1 <= end1)
{
tmp[index++] = arr[begin1++];
}
while (begin2 <= end2)
{
tmp[index++] = arr[begin2++];
}
for (int i = left;i <= right;i++)
{
arr[i] = tmp[i];
}
}
void MergeSort(int* arr, int n)
{
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail");
exit(1);
}
_MergeSort(arr, 0, n - 1,tmp);
free(tmp);
tmp = NULL;
}
动图演示：
特点分析：
- 时间复杂度：
最好情况：O(n logn)。
最坏情况：O(n logn)。
平均情况：O(n logn)。- 空间复杂度：O(n)。
- 稳定性：稳定。保持相等元素的相对顺序。
总结
以上就是本篇文章的全部了。排序算法就像计算机科学的一面镜子，反射出算法设计的智慧、效率与美的追求。从最简单的两两比较到精巧的分治策略，每一种算法都告诉我们：复杂的问题往往有优雅的解决方案。愿你在编程的道路上，既能欣赏简单算法的朴素美，也能领悟复杂算法的精妙处。记住，最好的算法不是最复杂的那个，而是最适合当前问题的那一个。排序结束，但探索永不停止。 🎯最后感谢大家的点赞、评论、收藏和关注。
往期回顾
《数据结构》——二叉树从概念到代码的详解
《数据结构》——轻松掌握队列（Queue）
力扣（LeetCode) ——100. 相同的树（C语言）