冒泡排序 希尔排序 归并排序

一、冒泡排序 Bubble Sort

1. 前提条件

冒泡排序是最基础的交换排序。

它的思想是：相邻两个数比较

如果顺序错了，就交换

一轮下来，最大值会被“冒泡”到最后

例如升序排序：小的在前，大的在后

2. 核心概念

数组：[5, 3, 8, 2]

第一轮：

5 和 3 比，交换 → [3,5,8,2]

5 和 8 比，不换 → [3,5,8,2]

8 和 2 比，交换 → [3,5,2,8]

这一轮结束后：8 已经到最后

所以每一轮都会确定一个最大值的位置。

3. 固定模板
   void bubbleSort(int arr[], int n)
   {
   for(int i = 0; i < n - 1; i++)
   {
   for(int j = 0; j < n - 1 - i; j++)
   {
   if(arr[j] > arr[j + 1])
   {
   int temp = arr[j];
   arr[j] = arr[j + 1];
   arr[j + 1] = temp;
   }
   }
   }
   }
   其实就是每次换两个之后确定最后一个最大值的位置，然后这样每次从头开始两两比较交换
4. 优化就是：如果某一轮没有发生交换，说明已经有序，可以提前结束。

void bubbleSort(int arr[], int n)
{
for(int i = 0; i < n - 1; i++)
{
int swapped = 0;

    for(int j = 0; j < n - 1 - i; j++)
    {
        if(arr[j] > arr[j + 1])
        {
            int temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;

            swapped = 1;
        }
    }

    if(swapped == 0)
    {
        break;
    }
}

}

5. 复杂度
   最好：O(n)
   平均：O(n²)
   最坏：O(n²)
   空间：O(1)
   稳定性：稳定

稳定的意思是：相等元素的相对顺序不变

因为冒泡只在：

arr[j] > arr[j + 1]

时交换，相等不交换。

二、希尔排序 Shell Sort

1. 前提条件

希尔排序是插入排序的改进版。

普通插入排序每次只能让元素移动一步。

希尔排序先让元素“大步移动”，再逐渐缩小步长。

2. 核心概念

希尔排序有一个关键词：gap 间隔

例如：

arr = [8, 9, 1, 7, 2, 3, 5, 4, 6, 0]

如果：

gap = 5

分组就是：

下标 0,5
下标 1,6
下标 2,7
下标 3,8
下标 4,9

每组内部做插入排序。

然后：gap = gap / 2

继续。直到：gap = 1

最后就是普通插入排序，但这时数组已经基本有序，所以会快很多。

3. 固定模板
   void shellSort(int arr[], int n)
   {
   for(int gap = n / 2; gap > 0; gap = gap / 2)
   {
   for(int i = gap; i < n; i++)
   {
   int temp = arr[i];
   int j = i;

        while(j >= gap && arr[j - gap] > temp)
        {
            arr[j] = arr[j - gap];
            j = j - gap;
        }
   
        arr[j] = temp;
    }
   

   }
   }
   希尔排序其实按照我的理解是，先分组大排序，这时候排序的次数少，步幅比较大，一个gap里面的循环对应每个j只交换一次，就是先提前保留下来，如果大于就交换，小于就保留，后面等到gap变小的时候，循环次数就变多了，比如说gap等于2，等到j加到比如说4的时候，他就要换两次，是步幅减短，增多小间隔的交换次数，逐渐使数组有序。

4. 代码理解

这段：for(int gap = n / 2; gap > 0; gap = gap / 2)

表示：

先大间隔排序

再小间隔排序

最后 gap = 1
这段：for(int i = gap; i < n; i++)

表示：从每组的第二个元素开始做插入排序

这段：

while(j >= gap && arr[j - gap] > temp)
{
arr[j] = arr[j - gap];
j = j - gap;
}

表示：如果前面同组元素比 temp 大

就往后挪

直到找到 temp 应该插入的位置

5. 例子
   arr = [9, 8, 3, 7, 5, 6, 4, 1]
   n = 8

第一轮：gap = 4

分组：

下标 0,4 → 9,5
下标 1,5 → 8,6
下标 2,6 → 3,4
下标 3,7 → 7,1

组内排序后大概变成：

[5,6,3,1,9,8,4,7]

第二轮：gap = 2

继续让元素更接近正确位置。

最后：gap = 1

普通插入排序收尾。

6. 复杂度

时间复杂度：和 gap 序列有关
常见简单写法：大概介于 O(nlogn) 和 O(n²) 之间
最坏可到 O(n²)
空间：O(1)
稳定性：不稳定
因为相同元素可能在不同 gap 分组中跨越移动，导致相对顺序改变。

三、归并排序 Merge Sort

1. 前提条件

归并排序是典型的：分治算法

分治就是：

把大问题拆成小问题
小问题解决后再合并

2. 核心概念

归并排序分两步：

1. 分：把数组不断分成两半
2. 合：把两个有序数组合并成一个有序数组

例如：[5, 2, 8, 1]

先分：[5,2] 和 [8,1]

继续分：[5] [2] [8] [1]

单个元素天然有序。

然后合并：

[5] + [2] → [2,5]

[8] + [1] → [1,8]

[2,5] + [1,8] → [1,2,5,8]

3. 固定模板

#include <stdlib.h>

void merge(int arr[], int temp[], int left, int mid, int right)
{
//这里是把一个数组从mid割开成两部分排序之后合并，奇数偶数的情况不需要考虑长度不同也可以排序
int i = left;
int j = mid + 1;
int k = left;

while(i <= mid && j <= right)
{
    if(arr[i] <= arr[j])
    {
        temp[k] = arr[i];
        i++;
    }
    else
    {
        temp[k] = arr[j];
        j++;
    }
//这里是弄了一个暂时数组存放比较i和j的结果之后选择小的放进left的位置里面，从left的位置开始，往后排序
//本质上是数组的两部分，比如说 1 3 4 | 2 5 6 排序，然后mid对应数值2，1和2比较1小，把1放进去，之后不断移位循环，3比2大，把2放进去，之后移位
    k++;
}
while(i <= mid)
{
    temp[k] = arr[i];
    i++;
    k++;
}
//这里是排序了就是右边的部分已经到了尽头，左边还有部分，所以就是把左边直接拉进temp来
while(j <= right)
{
    temp[k] = arr[j];
    j++;
    k++;
}
//这里是排序了左边的部分已经到了尽头，右边还有一部分，把右边的拉进temp来
for(int p = left; p <= right; p++)
{
    arr[p] = temp[p];
}

}

void mergeSortHelper(int arr[], int temp[], int left, int right)
{
if(left >= right)
{
return;
}

int mid = left + (right - left) / 2;

mergeSortHelper(arr, temp, left, mid);

mergeSortHelper(arr, temp, mid + 1, right);

merge(arr, temp, left, mid, right);

}

这个函数是逐渐分拆数组，直到分拆数组left=right之后返回，左右各自分拆，最后左右合并排序
理解还是和之前一样先写出口之后逐渐递归回拆排序，

void mergeSort(int arr[], int n)
{
int* temp = malloc(n * sizeof(int));

mergeSortHelper(arr, temp, 0, n - 1);

free(temp);

}
这里是分配空间之后，进行排序

4. 代码理解

递归出口：

if(left >= right)
{
return;
}

表示：区间里只有 0 个或 1 个元素天然有序

递归拆分：

mergeSortHelper(arr, temp, left, mid);
mergeSortHelper(arr, temp, mid + 1, right);

表示：

左半边排序
右半边排序

最后合并：

merge(arr, temp, left, mid, right);

表示：两个有序区间合并成一个有序区间

5. merge 函数怎么理解

假设：

左边：[2,5,8]
右边：[1,3,7]

三个指针：

i 指向左边
j 指向右边
k 指向 temp

比较：

2 和 1 → 放 1
2 和 3 → 放 2
5 和 3 → 放 3
5 和 7 → 放 5
8 和 7 → 放 7
左边剩 8 → 放 8

结果：[1,2,3,5,7,8]

6. 为什么归并稳定？

代码里：

if(arr[i] <= arr[j])

相等时先取左边。

所以相等元素的相对顺序不变。

因此归并排序是稳定排序。

7. 复杂度
   时间复杂度：O(nlogn)
   空间复杂度：O(n)
   稳定性：稳定

为什么是 O(nlogn)？

每一层合并总共 O(n)

一共有 logn 层
所以 O(nlogn)

四、三种排序对比总结
排序 思想 时间复杂度 空间 稳定性
冒泡排序 相邻交换 O(n²) O(1) 稳定
希尔排序 分组插入 和 gap 有关，最坏 O(n²) O(1) 不稳定
归并排序 分治合并 O(nlogn) O(n) 稳定
五、总结
冒泡排序：

相邻元素比较
顺序错就交换
每一轮确定一个最大值

核心：
arr[j] > arr[j+1] 就交换

特点：
简单
稳定
O(n²)

---

希尔排序：

插入排序的改进版

核心：
gap 分组
每组做插入排序
gap 不断变小
最后 gap = 1

特点：
比普通插入快
不稳定
O(1)空间

---

归并排序：

分治算法

核心：
先分成两半
左边排好
右边排好
再合并

特点：
O(nlogn)
稳定
需要 O(n) 辅助数组

冒泡靠交换，希尔靠分组插入，归并靠分治合并。