C语言实现的几种常用排序算法

简介

排序是算法中最基本的任务之一，其目的是将一系列元素按照一定的顺序进行排列。在实际开发中，排序算法被广泛应用，如数据分析、数据库查找等场景。在C语言中，有多种常用的排序算法，本文将详细介绍几种排序算法的实现方法。

冒泡排序（Bubble Sort）

冒泡排序是一种基本的排序算法，其原理是通过多次比较和交换来实现排序。其实现过程如下：

void bubble_sort(int array[], int size) {
    int i, j;
    for (i = 0; i < size - 1; i++) {           
        for (j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {     
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

示例说明：

#include <stdio.h>

void bubble_sort(int array[], int size) {
    int i, j;
    for (i = 0; i < size - 1; i++) {           
        for (j = 0; j < size - i - 1; j++) {
            if (array[j] > array[j + 1]) {     
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
            }
        }
    }
}

int main() {
    int array[] = { 5, 3, 4, 8, 10, 2, 1 };
    int i, size;
    size = sizeof(array) / sizeof(int);
    bubble_sort(array, size);
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

运行结果为：

1 2 3 4 5 8 10

快速排序（Quick Sort）

快速排序是一种高效的排序算法，其基本思想是通过一趟排序将待排序序列分割成两个子序列，其中左子序列的所有元素均小于右子序列的所有元素，然后再分别对左子序列和右子序列进行排序。其实现过程如下：

void quick_sort(int array[], int low, int high) {
    if (low < high) {                               
        int i = low, j = high, x = array[low];
        while (i < j) {
            while (i < j && array[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if (i < j)
                array[i++] = array[j];
            while (i < j && array[i] < x) // 从左向右找第一个大于等于x的数
                i++;
            if (i < j)
                array[j--] = array[i];
        }       
        array[i] = x;
        quick_sort(array, low, i - 1);            
        quick_sort(array, i + 1, high);           
    }
}

示例说明：

#include <stdio.h>

void quick_sort(int array[], int low, int high) {
    if (low < high) {                               
        int i = low, j = high, x = array[low];
        while (i < j) {
            while (i < j && array[j] >= x) // 从右向左找第一个小于x的数
                j--;
            if (i < j)
                array[i++] = array[j];
            while (i < j && array[i] < x) // 从左向右找第一个大于等于x的数
                i++;
            if (i < j)
                array[j--] = array[i];
        }       
        array[i] = x;
        quick_sort(array, low, i - 1);            
        quick_sort(array, i + 1, high);           
    }
}

int main() {
    int array[] = { 5, 3, 4, 8, 10, 2, 1 };
    int i, size;
    size = sizeof(array) / sizeof(int);
    quick_sort(array, 0, size - 1);
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

运行结果为：

1 2 3 4 5 8 10

归并排序（Merge Sort）

归并排序是一种分治思想的排序算法，其基本思想是将一组待排序序列分成两个子序列，对它们分别进行排序，然后将它们合并成一个较大的已排序序列。其实现过程如下：

void merge_sort(int array[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(array, start, mid);
        merge_sort(array, mid + 1, end);
        merge(array, start, mid, end);
    }
}

void merge(int array[], int start, int mid, int end) {
    int left_array[100], right_array[100];
    int i, j, k;
    for (i = start; i <= mid; i++)
        left_array[i - start] = array[i];
    left_array[i - start] = INT_MAX;
    for (j = mid + 1; j <= end; j++)
        right_array[j - mid - 1] = array[j];
    right_array[j - mid - 1] = INT_MAX;
    i = j = 0;
    for (k = start; k <= end; k++) {
        if (left_array[i] < right_array[j])
            array[k] = left_array[i++];
        else
            array[k] = right_array[j++];
    }
}

示例说明：

#include <stdio.h>
#include <limits.h>

void merge_sort(int array[], int start, int end) {
    if (start < end) {
        int mid = (start + end) / 2;
        merge_sort(array, start, mid);
        merge_sort(array, mid + 1, end);
        merge(array, start, mid, end);
    }
}

void merge(int array[], int start, int mid, int end) {
    int left_array[100], right_array[100];
    int i, j, k;
    for (i = start; i <= mid; i++)
        left_array[i - start] = array[i];
    left_array[i - start] = INT_MAX;
    for (j = mid + 1; j <= end; j++)
        right_array[j - mid - 1] = array[j];
    right_array[j - mid - 1] = INT_MAX;
    i = j = 0;
    for (k = start; k <= end; k++) {
        if (left_array[i] < right_array[j])
            array[k] = left_array[i++];
        else
            array[k] = right_array[j++];
    }
}

int main() {
    int array[] = { 5, 3, 4, 8, 10, 2, 1 };
    int i, size;
    size = sizeof(array) / sizeof(int);
    merge_sort(array, 0, size - 1);
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

运行结果为：

1 2 3 4 5 8 10

结论

以上就是三种常用的排序算法的完整攻略，在实际开发中需要根据具体情况进行选择。冒泡排序是较为简单的一种排序算法，但对于大规模的数据处理效率很低；快速排序是一种高效的排序算法，但在对于处理极端数据情况下效率会相对较低；归并排序则相比其他两种排序算法稍微复杂一些，但具有稳定性和较高的效率。