行业资讯

C语言数据结构经典10大排序算法实例分析

发布时间：2022-02-28 09:29:45 作者：iii
来源：亿速云 阅读：142

C语言数据结构经典10大排序算法实例分析

目录

  1. 引言
  2. 排序算法概述
  3. 冒泡排序
  4. 选择排序
  5. 插入排序
  6. 希尔排序
  7. 归并排序
  8. 快速排序
  9. 堆排序
  10. 计数排序
  11. 桶排序
  12. 基数排序
  13. 总结

引言

排序算法是计算机科学中最基本、最重要的算法之一。无论是在数据处理、数据库管理、图像处理还是人工智能等领域，排序算法都扮演着至关重要的角色。本文将详细介绍C语言中经典的10大排序算法，并通过实例分析其实现原理、时间复杂度、空间复杂度以及适用场景。

排序算法概述

排序算法可以分为两大类：比较排序和非比较排序。比较排序通过比较元素的大小来决定它们的顺序，而非比较排序则不依赖于元素之间的比较。常见的比较排序算法包括冒泡排序、选择排序、插入排序、归并排序、快速排序和堆排序。非比较排序算法包括计数排序、桶排序和基数排序。

冒泡排序

算法原理

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素并交换它们的位置，直到列表有序为止。冒泡排序的名字来源于较小的元素会像气泡一样逐渐“浮”到列表的顶端。

代码实现

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // 交换 arr[j] 和 arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

冒泡排序适用于小规模数据的排序，或者当数据已经基本有序时。

选择排序

算法原理

选择排序是一种简单直观的排序算法。它的工作原理是每次从未排序的部分中选择最小（或最大）的元素，放到已排序部分的末尾。

代码实现

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 交换 arr[i] 和 arr[min_idx]
        int temp = arr[i];
        arr[i] = arr[min_idx];
        arr[min_idx] = temp;
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

选择排序适用于小规模数据的排序，或者当内存空间有限时。

插入排序

算法原理

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

代码实现

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    insertionSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

插入排序适用于小规模数据的排序，或者当数据已经基本有序时。

希尔排序

算法原理

希尔排序是插入排序的一种改进版本，也称为缩小增量排序。它通过将列表分成若干子列表来进行排序，每个子列表使用插入排序。随着增量逐渐减小，整个列表逐渐变得有序。

代码实现

#include <stdio.h>

void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i];
            int j;
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp;
        }
    }
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    shellSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

希尔排序适用于中等规模数据的排序，或者当数据分布较为均匀时。

归并排序

算法原理

归并排序是一种分治算法。它将列表分成两个子列表，分别对子列表进行排序，然后将两个有序子列表合并成一个有序列表。

代码实现

#include <stdio.h>
#include <stdlib.h>

void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

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

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < arr_size; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

归并排序适用于大规模数据的排序，尤其是当数据无法全部加载到内存时。

快速排序

算法原理

快速排序是一种分治算法。它通过选择一个“基准”元素，将列表分成两部分，一部分小于基准，另一部分大于基准，然后递归地对这两部分进行排序。

代码实现

#include <stdio.h>

void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr)/sizeof(arr[0]);
    quickSort(arr, 0, n-1);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

快速排序适用于大规模数据的排序，尤其是当数据分布较为均匀时。

堆排序

算法原理

堆排序是一种基于二叉堆的排序算法。它首先将列表构建成一个最大堆（或最小堆），然后依次将堆顶元素与堆的最后一个元素交换，并调整堆，直到堆为空。

代码实现

#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;

        heapify(arr, n, largest);
    }
}

void heapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

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

        heapify(arr, i, 0);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

堆排序适用于大规模数据的排序，尤其是当数据分布较为均匀时。

计数排序

算法原理

计数排序是一种非比较排序算法。它通过统计每个元素的出现次数，然后根据统计结果将元素放回原列表中的正确位置。

代码实现

#include <stdio.h>
#include <stdlib.h>

void countingSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int* count = (int*)calloc(max + 1, sizeof(int));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    free(count);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    countingSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

计数排序适用于数据范围较小且数据分布较为均匀的情况。

桶排序

算法原理

桶排序是一种非比较排序算法。它将列表分成若干个桶，每个桶内的元素进行排序，然后将所有桶中的元素依次取出，得到有序列表。

代码实现

#include <stdio.h>
#include <stdlib.h>

void bucketSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    int* count = (int*)calloc(max + 1, sizeof(int));

    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }

    int index = 0;
    for (int i = 0; i <= max; i++) {
        while (count[i] > 0) {
            arr[index++] = i;
            count[i]--;
        }
    }

    free(count);
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    bucketSort(arr, n);
    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}

时间复杂度

空间复杂度

适用场景

桶排序适用于数据分布较为均匀且数据范围较小的情况。

基数排序

算法原理

基数排序是一种非比较排序算法。它通过将整数按位数切割成不同的数字，然后按每个位数分别进行排序。

代码实现

”`c #include #include

int getMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i < n; i++) { if (arr[i] > max) { max = arr[i]; } } return max; }

void countingSort(int arr[], int n, int exp) { int output[n]; int count[10] = {0};

for (int i = 0; i < n; i++) {
    count[(arr[i] / exp) % 10]++;
}

for (int i = 1; i < 10; i++) {
    count[i] += count[i - 1];
}

for (int i = n - 1; i >= 0; i--) {
    output[count[(arr[i] / exp) % 10] - 1] = arr[i];
    count[(arr[i] / exp) % 10]--;
}

for (int i = 0; i < n; i++) {
    arr[i] = output[i];
}

}

void radixSort(int arr[], int n) { int max = getMax(arr, n);

for (int exp = 1; max / exp > 0; exp *= 10) {
    countingSort(arr, n, exp);
}

}

int main() { int arr[] = {170, 45, 75, 90, 802, 24, 2

推荐阅读：
  1. 经典排序算法之快速排序(C语言版)
  2. 数据结构（十二）——排序算法

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c语言

上一篇：C++中Queue队列类模版的示例分析

下一篇：IDEA导入Spring-kafka项目Gradle编译失败的原因是什么

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号