常见排序算法详解与C语言实现

目录

1. 冒泡排序(Bubble Sort)

2. 选择排序(Selection Sort)

3. 插入排序(Insertion Sort)

4. 希尔排序(Shell Sort)

5. 堆排序(Heap Sort)

6. 快速排序(Quick Sort)

7. 归并排序(Merge Sort)

总结

引言

排序算法是计算机科学中最基础也是最重要的算法之一。本文将详细介绍七种常见的排序算法，包括冒泡排序、选择排序、插入排序、希尔排序、堆排序、快速排序和归并排序，并给出每种算法的C语言实现代码。

1. 冒泡排序(Bubble Sort)

冒泡排序是最简单的排序算法之一，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到列表排序完成。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮：

• 比较5和3 → 交换 → [3,5,8,6,2]

• 比较5和8 → 不交换

• 比较8和6 → 交换 → [3,5,6,8,2]

• 比较8和2 → 交换 → [3,5,6,2,8] (8已到位)

第二轮：

• 比较3和5 → 不交换

• 比较5和6 → 不交换

• 比较6和2 → 交换 → [3,5,2,6,8] (6已到位)

第三轮：

• 比较3和5 → 不交换

• 比较5和2 → 交换 → [3,2,5,6,8] (5已到位)

第四轮：

• 比较3和2 → 交换 → [2,3,5,6,8] (排序完成)

void bob(int *a, int size)
{
    // 外层循环控制排序轮数
    for (int i = 0; i < size; i++)
    {
        // 内层循环控制每轮比较次数
        for (int j = i + 1; j < size; j++)
        {
            // 如果前一个元素大于后一个元素，则交换
            if (a[i] > a[j])
            {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
}

时间复杂度：

• 最好情况：O(n)（已经排序的情况）

• 平均和最坏情况：O(n²)

空间复杂度：O(1)

2. 选择排序(Selection Sort)

选择排序每次从未排序的部分选择最小（或最大）的元素，放到已排序部分的末尾。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮：

• 找到最小值2 → 与5交换 → [2,3,8,6,5] (2已到位)

第二轮：

• 在[3,8,6,5]中找到最小值3 → 已在位置 → [2,3,8,6,5]

第三轮：

• 在[8,6,5]中找到最小值5 → 与8交换 → [2,3,5,6,8] (5已到位)

第四轮：

• 在[6,8]中找到最小值6 → 已在位置 → [2,3,5,6,8] (排序完成)

void sel(int *a, int size)
{
    // 外层循环控制已排序部分的末尾
    for (int i = 0; i < size; i++)
    {
        int min_index = i;  // 假设当前元素是最小的
        
        // 内层循环查找未排序部分的最小元素
        for (int j = i + 1; j < size; j++)
        {
            // 如果找到更小的元素，更新最小元素索引
            if (a[min_index] > a[j])
            {
                min_index = j;
            }
        }
        
        // 如果最小元素不是当前元素，则交换
        if (min_index != i)
        {
            swap(&a[i], &a[min_index]);
        }
    }
}

时间复杂度：始终为O(n²)

空间复杂度：O(1)

3. 插入排序(Insertion Sort)

插入排序通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

演示：
初始数组：[5, 3, 8, 6, 2]

第一步：

• 已排序[5], 未排序[3,8,6,2]

• 插入3 → 3<5 → [3,5,8,6,2]

第二步：

• 已排序[3,5], 未排序[8,6,2]

• 插入8 → 8>5 → [3,5,8,6,2]

第三步：

• 已排序[3,5,8], 未排序[6,2]

• 插入6 → 6<8 → [3,5,6,8,2]

第四步：

• 已排序[3,5,6,8], 未排序[2]

• 插入2 → 2<8 → 2<6 → 2<5 → 2<3 → [2,3,5,6,8] (排序完成)

void insert(int *a, int size)
{
    // 从第二个元素开始（第一个元素视为已排序）
    for (int i = 1; i < size; i++)
    {
        int k = a[i];   // 当前要插入的元素
        int j = i - 1;  // 已排序部分的最后一个元素索引

        // 将大于当前元素的已排序元素后移
        while (j >= 0 && a[j] > k)
        {
            a[j + 1] = a[j];
            j--;
        }
        
        // 将当前元素插入到正确位置
        a[j + 1] = k;
    }
}

时间复杂度：

• 最好情况：O(n)（已经排序的情况）

• 平均和最坏情况：O(n²)

空间复杂度：O(1)

4. 希尔排序(Shell Sort)

希尔排序是插入排序的改进版本，通过将原始列表分成多个子列表来提高插入排序的性能。

演示：
初始数组：[5, 3, 8, 6, 2, 9, 1, 7, 4]

第一轮(间隔=4)：

• 子序列1：[5,2,4] → 排序后[2,4,5]

• 子序列2：[3,9] → 排序后[3,9]

• 子序列3：[8,1] → 排序后[1,8]

• 子序列4：[6,7] → 排序后[6,7]

• 数组变为：[2,3,1,6,4,9,8,7,5]

第二轮(间隔=2)：

• 子序列1：[2,1,4,8,5] → 排序后[1,2,4,5,8]

• 子序列2：[3,6,9,7] → 排序后[3,6,7,9]

• 数组变为：[1,3,2,6,4,7,5,9,8]

第三轮(间隔=1)：

• 标准插入排序 → [1,2,3,4,5,6,7,8,9]

void shell(int *a, int size)
{
    // 初始间隔为数组长度的一半，逐步缩小间隔
    for (int gap = size / 2; gap > 0; gap /= 2)
    {
        // 对每个间隔分组进行插入排序
        for (int i = gap; i < size; i++)
        {
            int temp = a[i];  // 当前要插入的元素
            int j;
            
            // 组内插入排序
            for (j = i; j >= gap && a[j - gap] > temp; j -= gap)
            {
                a[j] = a[j - gap];
            }
            
            a[j] = temp;  // 插入元素到正确位置
        }
    }
}

时间复杂度：取决于间隔序列，最好可达O(n log²n)

空间复杂度：O(1)

5. 堆排序(Heap Sort)

堆排序利用堆这种数据结构所设计的一种排序算法，是一种选择排序。

演示：
初始数组：[5, 3, 8, 6, 2]

构建最大堆：

1. 从最后一个非叶子节点(6)开始调整：

   • 6>2 → 不交换

2. 调整节点3：

   • 3<8 → 交换 → [5,8,3,6,2]

   • 3无子节点 → 停止

3. 调整节点5：

   • 5<8 → 交换 → [8,5,3,6,2]

   • 5>2 → 不交换

堆排序过程：

1. 交换堆顶8和末尾2 → [2,5,3,6,8] (8已排序)

2. 调整堆：

   • 2<5 → 交换 → [5,2,3,6,8]

   • 2<3 → 交换 → [5,3,2,6,8]

3. 交换堆顶5和末尾2 → [2,3,5,6,8] (5,6,8已排序)

4. 调整堆：

   • 2<3 → 交换 → [3,2,5,6,8]

5. 交换堆顶3和末尾2 → [2,3,5,6,8] (排序完成)

void heapify(int *a, int size, int i)
{
    int largest = i;         // 初始化最大元素为当前节点
    int left = i * 2 + 1;    // 左子节点索引
    int right = i * 2 + 2;   // 右子节点索引

    // 如果左子节点存在且大于当前最大节点
    if (left < size && a[left] > a[largest])
    {
        largest = left;
    }

    // 如果右子节点存在且大于当前最大节点
    if (right < size && a[right] > a[largest])
    {
        largest = right;
    }

    // 如果最大节点不是当前节点，交换并继续调整
    if (largest != i)
    {
        swap(&a[i], &a[largest]);
        heapify(a, size, largest);
    }
}

void heapsort(int *a, int size)
{
    // 构建最大堆（从最后一个非叶子节点开始）
    for (int i = size / 2 - 1; i >= 0; i--)
    {
        heapify(a, size, i);
    }

    // 逐个提取堆顶元素（最大值）并调整堆
    for (int i = size - 1; i >= 0; i--)
    {
        // 将堆顶元素（最大值）与当前末尾元素交换
        swap(&a[0], &a[i]);
        
        // 调整剩余元素使其保持堆性质
        heapify(a, i, 0);
    }
}

时间复杂度：O(n logn)

空间复杂度：O(1)

6. 快速排序(Quick Sort)

快速排序是一种分治算法，它选择一个"基准"元素，将数组分为两部分，一部分小于基准，一部分大于基准，然后递归地对这两部分进行排序。

演示：
初始数组：[5, 3, 8, 6, 2]

第一轮(基准=2)：

• 2是最小值 → 分区后：[2,5,3,8,6]

• 左子数组空，右子数组[5,3,8,6]

第二轮(基准=6)：

• 分区过程：

  • 5<6 → i=0 → [5,3,8,6]

  • 3<6 → i=1 → [5,3,8,6]

  • 8>6 → 不移动

• 交换a[i+1]和基准 → [5,3,6,8]

• 左子数组[5,3], 右子数组[8]

第三轮(左子数组基准=3)：

• 分区后：[3,5]

• 排序完成

最终结果：[2,3,5,6,8]

void quicksort(int *a, int left, int right)
{
    if (left < right)
    {
        // 选择最后一个元素作为基准值
        int pivot = a[right];
        int i = left - 1;  // 小于基准值的元素分界点

        // 分区过程：将所有小于等于基准的元素移到左边
        for (int j = left; j < right; j++)
        {
            if (a[j] <= pivot)
            {
                i++;
                swap(&a[i], &a[j]);
            }
        }
        
        // 将基准值放到正确位置
        swap(&a[i + 1], &a[right]);
        int pivot_index = i + 1;

        // 递归排序左右两部分
        quicksort(a, left, pivot_index - 1);
        quicksort(a, pivot_index + 1, right);
    }
}

时间复杂度：

• 最好和平均情况：O(n logn)

• 最坏情况：O(n²)（当数组已经排序或逆序时）

空间复杂度：O(logn)（递归调用栈）

7. 归并排序(Merge Sort)

归并排序是一种分治算法，它将数组分成两半，递归地对每一半进行排序，然后将两个有序的半部分合并成一个有序的整体。

演示：
初始数组：[5, 3, 8, 6, 2]

拆分过程：
[5,3,8,6,2] → [5,3,8]和[6,2]
[5,3,8] → [5,3]和[8]
[5,3] → [5]和[3]
[6,2] → [6]和[2]

合并过程：

1. 合并[5]和[3] → [3,5]

2. 合并[3,5]和[8] → [3,5,8]

3. 合并[6]和[2] → [2,6]

4. 合并[3,5,8]和[2,6]：

   • 比较3和2 → 取2 → [2]

   • 比较3和6 → 取3 → [2,3]

   • 比较5和6 → 取5 → [2,3,5]

   • 比较8和6 → 取6 → [2,3,5,6]

   • 剩余8 → [2,3,5,6,8]

void merge(int *a, int l, int m, int r)
{
    int n1 = m - l + 1;  // 左子数组长度
    int n2 = r - m;       // 右子数组长度
    int i, j, k;

    // 分配临时数组存储左右子数组
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    // 拷贝数据到临时数组
    for (i = 0; i < n1; i++)
    {
        L[i] = a[l + i];
    }
    for (j = 0; j < n2; j++)
    {
        R[j] = a[m + 1 + j];
    }

    // 合并两个有序子数组
    i = 0;     // 左子数组索引
    j = 0;     // 右子数组索引
    k = l;     // 合并后数组索引

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            a[k] = L[i];
            i++;
        }
        else
        {
            a[k] = R[j];
            j++;
        }
        k++;
    }

    // 拷贝左子数组剩余元素
    while (i < n1)
    {
        a[k] = L[i];
        i++;
        k++;
    }

    // 拷贝右子数组剩余元素
    while (j < n2)
    {
        a[k] = R[j];
        j++;
        k++;
    }

    // 释放临时数组内存
    free(L);
    free(R);
}


void mergeSort(int arr[], int left, int right)
{
    if (left < right)
    {
        // 计算中间索引（防止整数溢出）
        int mid = left + (right - left) / 2;

        // 递归排序左半部分
        mergeSort(arr, left, mid);

        // 递归排序右半部分
        mergeSort(arr, mid + 1, right);

        // 合并两个已排序的子数组
        merge(arr, left, mid, right);
    }
}

时间复杂度：始终为O(n logn)

空间复杂度：O(n)（需要额外的存储空间）

总结

在实际应用中，快速排序通常是最快的通用排序算法，而归并排序由于其稳定性和始终如一的O(n logn)性能，也是常用的选择。对于小规模数据，插入排序可能更高效，因为它有较低的常数因子。