当前位置： 首页 > article >正文

十种基础排序算法(C语言实现，带源码)(有具体排序例子，适合学习理解)

article 2025/1/8 15:27:43

学习了十种常见的排序方法，此文章针对所学的排序方法进行整理（通过C语言完成排序）。
参考内容：
https://blog.csdn.net/mwj327720862/article/details/80498455
https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单的排序算法，属于交换排序的一种。通过重复遍历待排序的列表，依次比较相邻的两个元素并根据大小进行交换。

  1. 从左到右依次比较相邻的两个元素，如果前面的元素大于后面的元素，就交换它们的位置。
  2. 重复此过程，将最大（或最小）的元素移动到当前未排序部分的末尾。
  3. 对未排序部分重复上述步骤，直到所有元素都排好序。

时间复杂度（平均）： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

在这里插入图片描述

如图中数组排序，用了5轮成功排好序，但实际运行了8轮（不判断数组已经有序的情况下），以下是排序实现代码。

#include <stdio.h>

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

void printArr(int arr[], int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%-5d",arr[i]);
    }
    printf("\n");
}


int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    bubbleSort(arr,size);
    printArr(arr,size);

    return 0;
}

2. 选择排序（Selection Sort）

选择排序是一种简单排序算法，它的基本思想是通过多次选择，将没排序部分中的最小（或最大）元素找到，将其放在已排序部分的末尾（或开头）。

  1. 从未排序部分中找到最小（或最大）的元素。
  2. 将该元素与未排序部分的第一个元素交换，完成一轮排序。
  3. 将剩余未排序部分重复上述步骤，直到所有元素都排序完成。

时间复杂度（平均）： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)

在这里插入图片描述

#include <stdio.h>

int selectSort(int arr[],int size)
{
    int i,j,k;
    for(i = 0; i < size - 1; i++)
    {
        k = i;
        for(j = i + 1; j < size; j++)
        {
            if(arr[k] > arr[j])
                k = j;
        }
        int temp = arr[k];
        arr[k] = arr[i];
        arr[i] = temp;
    }
}

int printArr(int arr[],int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%-5d",arr[i]);
    }
    printf("\n");
}

int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    selectSort(arr,size);
    printArr(arr,size);
    return 0;
}

3. 插入排序（Insert Sort）

插入排序是一种简单的排序算法，它的基本思想是：将待排序的数组划分为已排序部分和未排序部分，每次从未排序部分取出一个元素，插入到已排序部分的合适位置，直到整个数组变得有序。

  1. 从第二个元素开始，依次将未排序部分的元素插入到已排序部分的合适位置，使已排序部分始终有序。
  2. 重复上述步骤，直到所有元素都排好序。

时间复杂度（平均）： O ( n 2 ) O(n^2) O(n2)

空间复杂度： O ( 1 ) O(1) O(1)
在这里插入图片描述

#include <stdio.h>

int insertSort(int arr[],int size)
{
    int i,j;
    for( i = 1; i < size; i++)
    {
        int temp = arr[i];
        for(j = i; j > 0 && arr[j - 1] > temp; j--)
        {
            arr[j] = arr[j - 1]; 
        }
        arr[j] = temp;

    }
}

void printArr(int arr[], int size)
{
    for(int i = 0; i < size; i++)
        printf("%-5d",arr[i]);
    printf("\n");
}


int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    insertSort(arr,size);
    printArr(arr,size);
    return 0;
}

4. 希尔排序（Shell Sort）

希尔排序是一种基于插入排序的高级排序算法，它的基本思想是通过逐步减少数据的间隔（gap），将数据分组并排序，从而逐步逼近整体有序；它的核心思想是分组插入排序，通过对数据进行预排序以减少逆序对，从而优化了插入排序的效率。

  1. 将数组分成多个间隔为gap的子序列（每隔gap个元素视为一个分组）。
  2. 对每个子序列进行插入排序，使子序列内局部有序。
  3. 减小gap值，重复步骤 1 和 2，直到gap=1，此时对整个数组进行最后一次插入排序。
  4. 最终数组完全有序

时间复杂度（平均）：介于 O ( n l o g n ) O(nlog n) O(nlogn)和 O ( n 2 ) O(n^2) O(n2)之间

空间复杂度： O ( 1 ) O(1) O(1)

在这里插入图片描述

#include <stdio.h>

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

void printArr(int arr[],int size)
{
    for(int i = 0; i < size; i++)
        printf("%-5d",arr[i]);
    printf("\n");
    
}

int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    shellSort(arr,size);
    printArr(arr,size);

    return 0;
}

5. 归并排序（Merge Sort）

归并排序是一种分治算法，它通过将数组不断拆分成更小的子数组进行排序，并将排序后的子数组合并成一个有序的数组。它的主要思想是分而治之：

  1. 分解：将数组递归地分成两半，直到每个子数组只有一个元素或为空。
  2. 合并：将两个有序的子数组合并成一个更大的有序数组。
  1. 将数组从中间拆分成两个子数组。
  2. 递归地对左右两个子数组进行归并排序。
  3. 合并两个有序子数组，使整个数组有序。

时间复杂度（平均）： O ( n l o g n ) O(nlogn) O(nlogn)

空间复杂度： O ( n ) O(n) O(n)（需要额外数组存储合并结果）

在这里插入图片描述

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

void merge(int arr[], int left, int mid, int right)
{
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));

    for(int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for(int i = 0; i < n2; i++)
        R[i] = arr[mid +i + 1];
    int i = 0, j = 0, k = left;
    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++;
    }
    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);
    }
}

void printArr(int arr[],int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%-5d",arr[i]);
    }
    printf("\n");
}


int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    mergeSort(arr,0,size - 1);
    printArr(arr,size);
    return 0;
}

6. 快速排序（Quick Sort）

快速排序是一种基于分治思想的高效排序算法。它通过选择一个基准值，将数组划分为两个部分：小于基准值的元素和大于基准值的元素，然后递归地对这两部分进行排序。

  1. 选择基准值：从数组中选择一个基准值（通常是第一个元素、最后一个元素或者任意元素）
  2. 分区：将数组重新排序，使所有小于基准值的元素位于基准值左侧，大于基准值的元素位于右侧
  3. 递归排序：对基准值两侧的子数组继续递归快速排序
  4. 重复上述步骤，直到有序

时间复杂度（平均）： O ( n l o g n ) O(nlogn) O(nlogn)

空间复杂度： O ( l o g n ) O(logn) O(logn)（递归栈空间）

在这里插入图片描述

#include <stdio.h>

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

    for(int j = low; j < high; j++)
    {
        if(arr[j] <= pivot)
        {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    
    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);
    }
}

void printArr(int arr[],int size)
{
    for(int i = 0; i < size; i++)
        printf("%-5d",arr[i]);
    printf("\n");
}


int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    quickSort(arr,0,size-1);
    printArr(arr,size);

    return 0;
}

7. 堆排序（Heap Sort）

堆排序是一种基于堆结构的比较排序算法。堆是一颗完全二叉树，并且满足堆性质：

  • 大顶堆：每个节点的值都大于或等于其左右子节点的值。
  • 小顶堆：每个节点的值都小于或等于其左右子节点的值。

堆排序利用大顶堆的特性来实现升序排序（或小顶堆实现降序排序）（此处实现升序排序）

  1. 构建初始堆：将数组是为完全二叉树，并调整其为大顶堆。
  2. 交换堆顶和堆尾：堆顶元素是最大值，与最后一个元素交换，将最大值移到最终位置。
  3. 调整堆：交换后，重新调整为大顶堆。
  4. 重复步骤2、3。直到堆中只有一个元素

时间复杂度（平均）： O ( n l o g n ) O(nlogn) O(nlogn)

空间复杂度： O ( 1 ) O(1) O(1)

在这里插入图片描述

#include <stdio.h>

void heapify(int arr[],int n,int i)
{
    int lastest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if(left < n && arr[left] > arr[lastest])
    {
        lastest = left;
    }
    if(right < n && arr[right] > arr[lastest])
    {
        lastest = right;
    }

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

        heapify(arr,n,lastest);
    }
}

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;)
    {
        int temp = arr[i];
        arr[i] = arr[0];
        arr[0] = temp;
        
        i--;
        heapify(arr,i,0);
    }
}

void printArr(int arr[],int size)
{
    for(int i = 0; i < size; i++)
    {
        printf("%-5d",arr[i]);
    }
    printf("\n");
}

int main(int argc,char *argv[])
{
    int arr[] = {1,3,7,5,4,6,2,9,8};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);

    heapSort(arr,size);
    printArr(arr,size);

    return 0;
}

8. 计数排序（Counting Sort）

计数排序是一种非比较排序算法，适用于对整数或范围有限的离散数据进行排序。它通过统计每个元素出现的次数来确定元素在排序后的位置。它的核心思想是：

  1. 统计每个元素的出现次数
  2. 利用这些计数信息计算元素的位置索引
  3. 根据索引将元素放入正确的位置，从而完成排序

  1. 计算频率：

  2. 找到数组中最大值和最小值，确定数值范围

  3. 创建一个计数数组，记录每个值在原数组中出现次数

  4. 累积计数：

将计数数组转换为累积计数数组，表示每个值在排序后的位置范围

  1. 填充结果：

倒叙遍历原数组，根据累积计数数组将元素放到结果数组中，并更新计数数组

时间复杂度： O ( n + k ) O(n+k) O(n+k)：n是数组大小，k是数据范围

空间复杂度： O ( n + k ) O(n+k) O(n+k)：需要额外计数数组和结果数组

在这里插入图片描述

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

void countSort(int arr[],int size)
{
    int max = arr[0],min = arr[0];
    for(int i = 0; i < size; i++)
    {
        if(arr[i] > max)
            max = arr[i];
        if(arr[i] < min)
            min = arr[i];
    }
    int len = max - min + 1;
    int *count = (int *)calloc(len,sizeof(int));
    for(int i = 0; i < size; i++)
    {
        count[arr[i]-min]++;
    }
	
    for(int i = 1; i < len; i++)
    {
        count[i] += count[i-1];
    }
	
    int *output = (int *)calloc(size,sizeof(int));
    for(int i = size - 1; i >= 0; i--)
    {
        output[count[arr[i]-min]-1] = arr[i];
    }
	for(int i = 0; i < size; i++)
	{
		arr[i] = output[i];
	}
	
    free(count);
    free(output);
}

void printArr(int arr[],int size)
{
    for(int i = 0;i < size; i++)
        printf("%-5d",arr[i]);
    printf("\n");
}



int main(int argc,char *argv[])
{
    int arr[] = {57, 31, 67, 89, 4, 12, 5, 54, 32, 63};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr,size);
    countSort(arr,size);
    printArr(arr,size);
    return 0;
}

9. 桶排序（Bucket Sort）

桶排序是一种基于分布的排序算法，它通过将数据分配到多个桶中，然后分别对每个桶中的数据进行排序，最后合并所有桶中的数据来完成排序。适用于输入数据分布均匀的情况，特别是当数据范围有限且可以被分成多个区间时，效率较高。

  1. 分桶：根据数据范围，将数据分配到多个桶中，每个桶对应一个区间
  2. 桶内排序：对每个桶中的数据分别进行排序（推荐插入排序）
  3. 合并桶：依次合并每个桶中的数据

时间复杂度（平均）： O ( n + k + n l o g ( n / k ) ) O(n+k+nlog(n/k)) O(n+k+nlog(n/k))

空间复杂度： O ( n + k ) O(n+k) O(n+k)

在这里插入图片描述

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

// 链表节点
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 创建新节点
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 在链表中插入节点并保持排序顺序
void sortedInsert(Node** head, int data) {
    Node* newNode = createNode(data);
    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* current = *head;
        while (current->next != NULL && current->next->data < data) {
            current = current->next;
        }
        newNode->next = current->next;
        current->next = newNode;
    }
}

// 桶排序函数
void bucketSort(int arr[], int size) {
    if (size <= 0) return;

    // 找到数组中的最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) max = arr[i];
        if (arr[i] < min) min = arr[i];
    }

    int bucketCount = 5; // 假设有5个桶
    int range = (max - min + bucketCount) / bucketCount; // 每个桶存储的整数范围
    Node** buckets = (Node**)malloc(bucketCount * sizeof(Node*));
    for (int i = 0; i < bucketCount; i++) {
        buckets[i] = NULL;
    }

    // 将元素分配到对应的桶
    for (int i = 0; i < size; i++) {
        int bucketIndex = (arr[i] - min) / range;
        sortedInsert(&buckets[bucketIndex], arr[i]);
    }

    // 将桶内的元素合并回原数组
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        Node* current = buckets[i];
        while (current != NULL) {
            arr[index++] = current->data;
            Node* temp = current;
            current = current->next;
            free(temp); // 释放链表节点
        }
    }

    free(buckets); // 释放桶数组
}

void printArr(int arr[], int size) {
    for (int i = 0; i < size; i++) 
        printf("%-5d", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {21, 33, 17, 5, 44, 26, 32, 19, 38};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, size);

    bucketSort(arr, size);
    printArr(arr, size);

    return 0;
}

10.基数排序（Radix Sort）

基数排序是一种非比较排序算法，通过按位对数据进行多轮排序来实现。它是一种稳定的排序算法，适用于整数或字符串等离散数据的排序。基数排序的核心思想是将数据拆分为多个位，按照位的优先级（从低位到高位或从高位到低位）依次进行排序。

  1. 确定最大位数：找到数组中元素的最大数，决定排序的轮数

  2. 按位排序：

  3. 从最低为开始，对每一位进行排序

  4. 使用稳定的排序算法（如计数排序）对当前位上的数字进行排序

  5. 完成排序：

重复2，直到最高位

时间复杂度： O ( d ∗ ( n + k ) ) O(d*(n+k)) O(d∗(n+k))，其中d是位数，n是数据大小，k是基数

空间复杂度： O ( n + k ) O(n+k) O(n+k)

在这里插入图片描述

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

// 使用计数排序对数组的某一位进行排序
void countSort(int arr[], int size, int exp) {
    int output[size]; // 输出数组
    int count[10] = {0}; // 计数数组

    // 统计当前位数字的频率
    for (int i = 0; i < size; i++) {
        int digit = (arr[i] / exp) % 10;
        count[digit]++;
    }

    // 计算累积频率
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    // 按当前位数字将元素放入输出数组
    for (int i = size - 1; i >= 0; i--) {
        int digit = (arr[i] / exp) % 10;
        output[count[digit] - 1] = arr[i];
        count[digit]--;
    }

    // 将排序结果复制回原数组
    for (int i = 0; i < size; i++) {
        arr[i] = output[i];
    }
}

// 基数排序主函数
void radixSort(int arr[], int size) {
    // 找到最大值，确定最高位
    int max = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }

    // 从个位开始，对每一位进行排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, size, exp);
    }
}

void printArr(int arr[], int size) {
    for (int i = 0; i < size; i++) 
        printf("%-5d", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {1705, 43, 76, 90, 802, 24, 2, 66, 635};
    int size = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, size);

    radixSort(arr, size);
    printArr(arr, size);

    return 0;
}

http://www.kler.cn/a/470112.html

相关文章：

  • 怎么管理电脑usb接口，分享四种USB端口管理方法
  • unity学习13：gameobject的组件component以及tag, layer 归类
  • 行为模式10.职责链模式
  • ollama安装及本地部署开源大模型
  • python学习笔记—13—while和for循环
  • 【学习笔记】数据结构（十）
  • 动手学深度学习-深度学习计算-6GPU
  • 记一次k8s下容器启动失败，容器无日志问题排查
  • 日志记录：追踪你的Java行动轨迹
  • 微软 2024 最新技术全景洞察
  • NO.1 《机器学习期末复习篇》以题（问答题）促习（人学习），满满干huo，大胆学大胆补！
  • sql server cdc重启监控新加表字段
  • asp.net core mvc的 ViewBag ， ViewData ， Module ，TempData
  • JS数组转字符串（3种方法）
  • 字母异位分组力扣--49
  • 福建省乡镇界面数据arcgis格式shp乡镇名称和编码无偏移坐标内容测评
  • 什么是Spring Boot？深度解析其核心概念与优势
  • 从MySQL迁移到PostgreSQL的完整指南
  • Golang设计模式目录
  • CSS语言的软件开发工具
  • Easysearch Java SDK 2.0.x 使用指南（三）
  • 【微服务】5、服务保护 Sentinel
  • AWS Auto Scaling基础知识
  • 【AI日记】25.01.06
  • Ruby语言的语法
  • SVN简单使用教程