C语言实现排序介绍

C语言学习都会学到排序算法，下面实现两个排序算法：

#include 

// 冒泡排序
void bubble_sort(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;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

小结

冒泡排序和快速排序。其中，冒泡排序通过多次遍历数组，将相邻元素进行比较和交换，使得较大的元素逐渐沉底，较小的元素逐渐浮出。

// 快速排序
void quick_sort(int arr[], int left, int right) {
    if (left >= right) {
        return;
    }
    int pivot = arr[left];
    int i = left + 1;
    int j = right;
    while (i <= j) {
        if (arr[i] < pivot && arr[j] > pivot) {
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        } else if (arr[i] >= pivot) {
            i++;
        } else if (arr[j] <= pivot) {
            j--;
        }
    }
    int temp = arr[j];
    arr[j] = arr[left];
    arr[left] = temp;
    quick_sort(arr, left, j - 1);
    quick_sort(arr, j + 1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

小结

快速排序则通过选定一个基准元素，将数组分成两部分，使得一部分的元素都小于基准元素，另一部分的元素都大于基准元素，然后对这两部分分别进行递归排序。

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

    bubble_sort(arr, n);
    printf("Bubble sort result: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quick_sort(arr, 0, n - 1);
    printf("Quick sort result: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

总结

冒泡排序和快速排序在性能上有一些显著的差异。下面是它们之间的一些比较：

1. 时间复杂度：这是两种排序算法最主要的区别。冒泡排序的时间复杂度是O(n^2)，这意味着随着输入数据量的增加，所需时间将呈二次方增长。而快速排序的时间复杂度在理想情况下是O(nlogn)，这使得它在处理大量数
   据时比冒泡排序更高效。
2. 空间复杂度：这是另一个重要的考虑因素。冒泡排序的空间复杂度是O(1)，因为它只需要常量级别的额外空间。而快速排序由于递归和辅助栈的使用，其空间复杂度是O(logn)，在处理大量数据时可能会占用较多的内
   存。
3. 稳定性：冒泡排序是稳定的，这意味着相等的元素将保持其原始顺序。而快速排序是不稳定的，因为它在某些情况下可能会导致原始顺序的改变。
4. 实际性能：在实际应用中，两种算法的性能取决于具体的数据和实现。例如，当数据量较小时，冒泡排序可能会比快速排序更快，因为它的简单性。而在处理大量数据时，快速排序则可能更优，因为它利用了分而治之的
   原则，将大问题分解为更小的问题来解决。

总的来说，选择哪种排序算法取决于你的具体需求，包括数据量的大小、内存限制、稳定性需求等因素。