C 排序算法学习笔记

排序算法是计算机科学中的一个非常重要的领域。它涉及到对数据集合进行排序或者搜索的算法设计和优化。C 语言是一种广泛使用的高级编程语言，本文将着重介绍基于 C 语言实现的几个常用排序算法。

1. 冒泡排序

冒泡排序是一种简单但效率较低的排序算法。其基本思想是通过不断交换相邻两个元素的位置，将待排数组中最大的元素冒泡至顶端。具体步骤如下：

cCopy Code
void bubble_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }
}

上述代码中，变量 arr 表示待排序数组，变量 n 表示数组长度。

2. 插入排序

插入排序是一种简单但效率较高的排序算法。其基本思想是不断将待排数组中未排部分的第一个元素插入已排部分中正确的位置。具体步骤如下：

cCopy Code
void insert_sort(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--;
        }
        arr[j+1] = key;
    }
}

上述代码中，变量 arr 表示待排序数组，变量 n 表示数组长度。

3. 快速排序

快速排序是一种常用的高效排序算法。其基本思想是通过不断地分割数组为两个子数组，已达到排序的目的。具体步骤如下：

cCopy Code
void quick_sort(int arr[], int left, int right) {
    if (left < right) {
        int pivot = partition(arr, left, right);
        quick_sort(arr, left, pivot - 1);
        quick_sort(arr, pivot + 1, right);
    }
}

int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    for (int j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    int tmp = arr[i+1];
    arr[i+1] = arr[right];
    arr[right] = tmp;
    return i+1;
}

上述代码中，变量 arr 表示待排序数组，变量 left 和 right 分别表示数组的左右端点。

4. 归并排序

归并排序是一种分治算法，其基本思想是将待排数组划分为若干个子数组，对每个子数组进行排序，并最终将子数组合并成一个有序的数组。具体步骤如下：

cCopy Code
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);
        merge(arr, left, mid, right);
    }
}

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, j = 0, 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) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

上述代码中，变量 arr 表示待排序数组，变量 left 和 right 分别表示数组的左右端点。