C语言的算法实现与复杂度分析
引言
•C语言是一种广泛应用于计算机科学领域的编程语言，具有灵活、高效的特点。
•算法是解决问题的步骤或方法，C语言提供了丰富的数据结构和算法库，可以方便地进行算法实现。
•本文将介绍C语言中常见算法的实现方式，并对其复杂度进行分析，以帮助读者更好地理解和应用这些算法。
一、排序算法
1. 冒泡排序（Bubble Sort）
1.1 算法描述
1.从第一个元素开始，比较相邻的两个元素，若第一个元素大于第二个元素，则交换这两个元素的位置。
2.继续对每一对相邻元素进行比较和交换，直到最后一个元素。
c语言的冒泡排序算法3.重复以上步骤，直至所有元素有序。
1.2 算法实现
#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]) {
                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("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
2. 快速排序（Quick Sort）
2.1 算法描述
4.选择一个基准元素（一般选择第一个元素）。
5.将比基准元素小的元素移到基准元素的左边，将比基准元素大的元素移到基准元素的右边。
6.对基准元素左右两边的子序列进行递归的快速排序。
2.2 算法实现
#include <stdio.h>
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int arr[], int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    while (1) {
        while (i <= j && arr[i] <= pivot) {
            i++;
        }
        while (i <= j && arr[j] > pivot) {
            j--;
        }
        if (i > j) {
            break;
        }
        swap(&arr[i], &arr[j]);
    }
    swap(&arr[low], &arr[j]);
    return j;
}
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("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    return 0;
}
3. 归并排序（Merge Sort）
3.1 算法描述
7.将待排序数组不断划分成两个子数组，直至划分成只含一个元素的子数组。
8.将两个子数组合并成一个有序数组，直至最终得到完整有序数组。
3.2 算法实现
#include <stdio.h>
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }
    int i = 0;
    int j = 0;
    int 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) {

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。