C语言排序算法详解-EW帮帮网

在C语言中，有多种排序算法可供选择，每种算法都有其独特的特点和适用场景。下面将详细介绍几种常见的排序算法，包括原理、代码实现和复杂度分析。

1. 冒泡排序（Bubble Sort）

原理

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

代码实现

#include <stdio.h>

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

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

复杂度分析

时间复杂度： $O(n^2)$ ，其中 $n$ 是数组的长度。这是因为需要进行两层嵌套循环。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。

2. 选择排序（Selection Sort）

原理

选择排序是一种简单直观的排序算法。它首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

代码实现

#include <stdio.h>

// 选择排序函数
void selectionSort(int arr[], int n) {
    int i, j, min_idx, temp;
    for (i = 0; i < n - 1; i++) {
        // 找到未排序部分的最小元素的索引
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        // 交换最小元素和当前元素
        temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

复杂度分析

时间复杂度： $O(n^2)$ ，同样需要两层嵌套循环。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。

3. 插入排序（Insertion Sort）

原理

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

代码实现

#include <stdio.h>

// 插入排序函数
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        // 将比 key 大的元素后移
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

复杂度分析

时间复杂度：平均和最坏情况下为 $O(n^2)$ ，最好情况下（数组已经有序）为 $O (n)$ 。
空间复杂度： $O (1)$ ，只需要常数级的额外空间。

4. 快速排序（Quick Sort）

原理

快速排序是一种分治算法。它选择一个基准值（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准值，右边部分的元素都大于等于基准值，然后分别对左右两部分递归地进行排序。

代码实现

#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);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("排序后的数组: \n");
    printArray(arr, n);
    return 0;
}

复杂度分析

时间复杂度：平均情况下为 $O (n l o g n)$ ，最坏情况下为 $O(n^2)$ （例如数组已经有序）。
空间复杂度：平均情况下为 $O (l o g n)$ ，最坏情况下为 $O (n)$ 。

5. 归并排序（Merge Sort）

原理

归并排序是一种分治算法。它将一个数组分成两个子数组，分别对这两个子数组进行排序，然后将排好序的子数组合并成一个最终的有序数组。

代码实现

#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];

    // 复制数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 归并临时数组到 arr[l..r]
    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++;
    }

    // 复制 L[] 的剩余元素
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 的剩余元素
    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);
    }
}

// 打印数组函数
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

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

    printf("给定的数组是 \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("\n排序后的数组是 \n");
    printArray(arr, arr_size);
    return 0;
}

复杂度分析

时间复杂度：始终为 $O (n l o g n)$ ，无论数组的初始状态如何。
空间复杂度： $O (n)$ ，需要额外的空间来合并子数组。

总结

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	稳定
选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	不稳定
插入排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	稳定
快速排序	$O (n l o g n)$	$O(n^2)$	$O (n l o g n)$	$O (l o g n)$	不稳定
归并排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (n)$	稳定

在实际应用中，需要根据数据规模、数据初始状态等因素选择合适的排序算法。

C语言排序算法详解

1. 冒泡排序（Bubble Sort）

原理

代码实现

复杂度分析

2. 选择排序（Selection Sort）

原理

代码实现

复杂度分析

3. 插入排序（Insertion Sort）

原理

代码实现

复杂度分析

4. 快速排序（Quick Sort）

原理

代码实现

复杂度分析

5. 归并排序（Merge Sort）

原理

代码实现

复杂度分析

总结

网站公告

今日签到

热门文章

最新发布