C语言数组排序算法详解：从冒泡到归并

C语言数组排序算法详解：从冒泡到归并

C语言对数组排序的方法有很多，包括冒泡排序、选择排序、插入排序、快速排序和归并排序等，每种方法都有其独特的优点和适用场景。在这篇文章中，我们将详细介绍几种常见的排序算法，并提供具体的代码示例和性能分析。特别地，我们将深入探讨快速排序这一高级排序算法，因为它在多数情况下表现出色。

一、冒泡排序

冒泡排序是最简单的一种排序算法，它的基本思想是通过多次比较和交换，将数组中的元素逐渐移动到正确的位置。尽管它的时间复杂度较高，但适用于数据量较小的情况。

原理介绍

冒泡排序通过重复地走访要排序的数组，一次比较两个元素，如果它们的顺序错误就交换它们的位置。这个过程被重复进行，直到没有再需要交换的元素为止，表示排序完成。

代码示例

#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("Sorted array: \n");  
    for (int i=0; i < n; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
    return 0;  
}  

性能分析

冒泡排序的时间复杂度是O(n^2)，其中n是数组的元素个数。尽管它的实现简单，但对于大数组来说，性能较差。

二、选择排序

选择排序也是一种简单的排序算法，它的基本思想是每次从未排序的部分中选出最小（或最大）的元素，放到已排序部分的末尾。

原理介绍

选择排序从数组中找到最小元素，将它与数组的第一个元素交换，然后在剩下的未排序部分中继续这个过程，直到数组排序完成。

代码示例

#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;  
        }  
        int temp = arr[min_idx];  
        arr[min_idx] = arr[i];  
        arr[i] = 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]);  
    printf("\n");  
    return 0;  
}  

性能分析

选择排序的时间复杂度也是O(n^2)，它与冒泡排序的区别在于交换的次数较少，但总体性能依旧不佳。

三、插入排序

插入排序的基本思想是将数组分成已排序和未排序两部分，每次从未排序部分中取一个元素，插入到已排序部分的适当位置。

原理介绍

插入排序类似于打扑克牌时整理手牌的过程，每次将一张新牌插入到已有序的牌组中。通过比较和移动数据，最终完成排序。

代码示例

#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]);  
    printf("\n");  
    return 0;  
}  

性能分析

插入排序的时间复杂度也是O(n^2)，但在大多数情况下，它的性能优于冒泡排序和选择排序，尤其是当数组已经部分排序时。

四、快速排序

快速排序是一种高效的排序算法，它的基本思想是通过一个分区操作，将数组分成两部分，然后递归地对这两部分进行排序。

原理介绍

快速排序通过选择一个“基准”元素，将数组分为两部分：一部分小于基准，另一部分大于基准。然后对这两部分分别递归进行排序。

代码示例

#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]);  
    printf("\n");  
    return 0;  
}  

性能分析

快速排序的平均时间复杂度是O(n log n)，在多数情况下，它是最有效的排序算法之一。然而，在最坏情况下（例如，选择的基准每次都是数组的最大或最小值），它的时间复杂度会退化为O(n^2)。通过随机化选择基准或采用“三数取中”的方法，可以有效避免最坏情况。

五、归并排序

归并排序是一种基于分治思想的排序算法，它将数组分成若干子数组，分别排序后再将它们合并成一个有序数组。

原理介绍

归并排序通过递归地将数组分成两半，直到每个子数组只有一个元素，然后将这些子数组逐步合并成有序数组。

代码示例

#include <stdio.h>

void merge(int arr[], int l, int m, int r) {  
    int n1 = m - l + 1;  
    int n2 = r - m;  
    int L[n1], R[n2];  
    for (int i = 0; i < n1; i++)  
        L[i] = arr[l + i];  
    for (int j = 0; j < n2; j++)  
        R[j] = arr[m + 1 + j];  
    int 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]);  
    printf("\n");  
    return 0;  
}  

性能分析

归并排序的时间复杂度是O(n log n)，它的性能稳定，适用于大数组的排序。与快速排序不同的是，归并排序的最坏情况和平均情况的时间复杂度都是O(n log n)。

六、总结

通过本文的介绍，我们了解了C语言中几种常见的数组排序方法，包括冒泡排序、选择排序、插入排序、快速排序和归并排序。每种排序算法都有其独特的特点和适用场景：

1. 冒泡排序：简单但效率低，适用于小数据集。
2. 选择排序：实现简单，交换次数较少，但总体效率不高。
3. 插入排序：对部分有序数组表现优异，适用于小数据集。
4. 快速排序：高效，适用于大多数情况，但最坏情况效率低，可以通过改进选择基准来优化。
5. 归并排序：性能稳定，适用于大数据集。

选择合适的排序算法不仅可以提高程序的效率，还能在实际应用中解决不同类型的数据排序问题。希望本文能够帮助你更好地理解和应用这些排序算法。