排序算法

排序算法是计算机科学中的基础算法，用于将一组数据按照特定顺序排列。本文将详细介绍C语言中常用的排序算法及其实现。

排序算法的基本概念

排序的定义

排序是将一组数据元素按照某个关键字的值的大小，从小到大（升序）或从大到小（降序）排列的过程。

排序算法的分类

按时间复杂度分类

类别	时间复杂度	算法举例
常数阶	O(1)	无
对数阶	O(log n)	无
线性阶	O(n)	桶排序、计数排序、基数排序
线性对数阶	O(n log n)	快速排序、归并排序、堆排序
平方阶	O(n²)	冒泡排序、选择排序、插入排序
立方阶	O(n³)	无
指数阶	O(2ⁿ)	无

按空间复杂度分类

类别	空间复杂度	算法举例
原地排序	O(1)	冒泡排序、选择排序、插入排序、快速排序
非原地排序	O(n)	归并排序、桶排序、计数排序、基数排序

按稳定性分类

类别	定义	算法举例
稳定排序	相等元素的相对顺序保持不变	冒泡排序、插入排序、归并排序、计数排序
不稳定排序	相等元素的相对顺序可能改变	选择排序、快速排序、堆排序

基本排序算法

1. 冒泡排序 (Bubble Sort)

算法思想

比较相邻的元素，如果前一个比后一个大，就交换它们
对每一对相邻元素执行同样的操作，从开始第一对到结尾的最后一对
每一轮结束后，最大的元素会「冒泡」到数组的末尾
重复以上步骤，每次比较的元素个数减1

实现代码

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        // 标记本轮是否发生交换
        int swapped = 0;
        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;
                swapped = 1;
            }
        }
        // 如果本轮没有交换，说明数组已经有序
        if (!swapped) {
            break;
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    bubbleSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n)（数组已有序）
- 最坏情况：O(n²)（数组逆序）
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：稳定

2. 选择排序 (Selection Sort)

算法思想

首先在未排序序列中找到最小（或最大）元素，存放到排序序列的起始位置
再从剩余未排序元素中继续寻找最小（或最大）元素，放到已排序序列的末尾
重复第二步，直到所有元素均排序完毕

实现代码

#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;
            }
        }
        // 交换元素
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    selectionSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n²)
- 最坏情况：O(n²)
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：不稳定

3. 插入排序 (Insertion Sort)

算法思想

将待排序序列分为已排序和未排序两部分
初始时，已排序部分只包含第一个元素
依次将未排序部分的每个元素插入到已排序部分的适当位置
重复第三步，直到未排序部分为空

实现代码

#include <stdio.h>

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        // 将大于key的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    insertionSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n)（数组已有序）
- 最坏情况：O(n²)（数组逆序）
- 平均情况：O(n²)
空间复杂度：O(1)
稳定性：稳定

高级排序算法

4. 快速排序 (Quick Sort)

算法思想

选择一个基准元素（通常是第一个或最后一个元素）
将数组分为两部分，小于基准的元素放在左边，大于基准的元素放在右边
对左右两部分递归执行上述步骤
当子数组长度为1或0时，排序完成

实现代码

#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[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 小于基准的元素的索引
    
    for (int j = low; j < high; 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);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n log n)（每次分区都将数组均分）
- 最坏情况：O(n²)（数组已有序或逆序）
- 平均情况：O(n log n)
空间复杂度：O(log n)（递归调用栈）
稳定性：不稳定

5. 归并排序 (Merge Sort)

算法思想

将数组分成两半
递归地对两半进行排序
将排序好的两半合并成一个有序数组

实现代码

#include <stdio.h>
#include <stdlib.h>

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    // 创建临时数组
    int *L = (int *)malloc(n1 * sizeof(int));
    int *R = (int *)malloc(n2 * sizeof(int));
    
    // 复制数据到临时数组
    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++;
    }
    
    // 释放临时数组
    free(L);
    free(R);
}

// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        
        // 递归排序左右两部分
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        
        // 合并
        merge(arr, left, mid, right);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    mergeSort(arr, 0, n - 1);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
空间复杂度：O(n)
稳定性：稳定

6. 堆排序 (Heap Sort)

算法思想

将待排序序列构建成一个大顶堆
将堆顶元素（最大值）与末尾元素交换
将剩余n-1个元素重新构建成一个堆
重复步骤2-3，直到整个序列有序

实现代码

#include <stdio.h>

// 交换元素
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化largest为根
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点
    
    // 如果左子节点大于根
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    // 如果最大值不是根
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        
        // 递归调整受影响的子堆
        heapify(arr, n, largest);
    }
}

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // 逐个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将堆顶元素与末尾元素交换
        swap(&arr[0], &arr[i]);
        
        // 调整剩余的堆
        heapify(arr, i, 0);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    heapSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n log n)
- 最坏情况：O(n log n)
- 平均情况：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

线性时间排序算法

7. 计数排序 (Counting Sort)

算法思想

找出待排序数组中的最大值和最小值
统计数组中每个值为i的元素出现的次数，存入计数数组C的第i项
对所有的计数累加，得到计数数组C
反向填充目标数组

实现代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void countingSort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    
    // 找出最大值和最小值
    int max = arr[0], min = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }
    
    int range = max - min + 1;
    
    // 创建计数数组
    int *count = (int *)calloc(range, sizeof(int));
    if (count == NULL) {
        fprintf(stderr, "内存分配失败\n");
        return;
    }
    
    // 统计每个元素出现的次数
    for (int i = 0; i < n; i++) {
        count[arr[i] - min]++;
    }
    
    // 反向填充原数组
    int index = 0;
    for (int i = 0; i < range; i++) {
        while (count[i] > 0) {
            arr[index++] = i + min;
            count[i]--;
        }
    }
    
    free(count);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {4, 2, 2, 8, 3, 3, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    countingSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：O(n + k)，其中k是数组中元素的范围
空间复杂度：O(k)
稳定性：稳定

8. 桶排序 (Bucket Sort)

算法思想

将数组分到有限数量的桶里
每个桶再各自排序（可能使用别的排序算法）
最后将各个桶中的元素有序地合并起来

实现代码

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建新节点
Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到链表（保持有序）
void insertSorted(Node **head, int data) {
    Node *newNode = createNode(data);
    
    if (*head == NULL || (*head)->data >= data) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    
    Node *current = *head;
    while (current->next != NULL && current->next->data < data) {
        current = current->next;
    }
    
    newNode->next = current->next;
    current->next = newNode;
}

// 桶排序
void bucketSort(int arr[], int n) {
    if (n <= 1) {
        return;
    }
    
    // 找出最大值
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    
    // 桶的数量
    int bucketCount = 10;
    
    // 创建桶
    Node **buckets = (Node **)calloc(bucketCount, sizeof(Node *));
    if (buckets == NULL) {
        fprintf(stderr, "内存分配失败\n");
        return;
    }
    
    // 将元素分配到桶中
    for (int i = 0; i < n; i++) {
        int bucketIndex = (arr[i] * bucketCount) / (max + 1);
        insertSorted(&buckets[bucketIndex], arr[i]);
    }
    
    // 从桶中收集元素
    int index = 0;
    for (int i = 0; i < bucketCount; i++) {
        Node *current = buckets[i];
        while (current != NULL) {
            arr[index++] = current->data;
            Node *temp = current;
            current = current->next;
            free(temp);
        }
    }
    
    free(buckets);
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    bucketSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：
- 最好情况：O(n + k)
- 最坏情况：O(n²)
- 平均情况：O(n + k)
空间复杂度：O(n + k)
稳定性：稳定

9. 基数排序 (Radix Sort)

算法思想

按照低位先排序，然后收集
再按照高位排序，然后再收集
依此类推，直到最高位

实现代码

#include <stdio.h>
#include <stdlib.h>

// 获取数组中的最大值
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

// 计数排序（按指定位数排序）
void countSort(int arr[], int n, int exp) {
    int *output = (int *)malloc(n * sizeof(int));
    int count[10] = {0};
    
    // 统计每个数字出现的次数
    for (int i = 0; i < n; i++) {
        count[(arr[i] / exp) % 10]++;
    }
    
    // 计算累积次数
    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }
    
    // 构建输出数组
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }
    
    // 复制回原数组
    for (int i = 0; i < n; i++) {
        arr[i] = output[i];
    }
    
    free(output);
}

// 基数排序
void radixSort(int arr[], int n) {
    int max = getMax(arr, n);
    
    // 对每一位进行计数排序
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countSort(arr, n, exp);
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    printArray(arr, n);
    
    radixSort(arr, n);
    
    printf("排序后: ");
    printArray(arr, n);
    
    return 0;
}

算法分析

时间复杂度：O(d*(n + k))，其中d是位数，k是基数
空间复杂度：O(n + k)
稳定性：稳定

排序算法的比较与选择

排序算法比较表

算法	最好时间复杂度	最坏时间复杂度	平均时间复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n)	O(n²)	O(n²)	O(1)	稳定
快速排序	O(n log n)	O(n²)	O(n log n)	O(log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	稳定
桶排序	O(n + k)	O(n²)	O(n + k)	O(n + k)	稳定
基数排序	O(d(n + k))	O(d(n + k))	O(d(n + k))	O(n + k)	稳定

排序算法的选择

根据数据规模选择

小规模数据（n < 100）：插入排序、冒泡排序
中等规模数据（100 ≤ n < 10000）：快速排序、堆排序
大规模数据（n ≥ 10000）：归并排序、桶排序、计数排序、基数排序

根据数据分布选择

基本有序：插入排序、冒泡排序
随机分布：快速排序
分布范围小：计数排序
分布均匀：桶排序
多位数：基数排序

根据内存限制选择

内存充足：归并排序、桶排序、计数排序、基数排序
内存有限：快速排序、堆排序、插入排序、选择排序

排序算法的实际应用

1. 数组排序

#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;
            }
        }
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    selectionSort(arr, n);
    
    printf("排序后: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    
    return 0;
}

2. 结构体排序

#include <stdio.h>
#include <string.h>

// 学生结构体
typedef struct {
    char name[50];
    int score;
} Student;

// 按分数排序
void sortStudentsByScore(Student students[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (students[j].score > students[j + 1].score) {
                Student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

// 按姓名排序
void sortStudentsByName(Student students[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (strcmp(students[j].name, students[j + 1].name) > 0) {
                Student temp = students[j];
                students[j] = students[j + 1];
                students[j + 1] = temp;
            }
        }
    }
}

void printStudents(Student students[], int n) {
    for (int i = 0; i < n; i++) {
        printf("姓名: %s, 分数: %d\n", students[i].name, students[i].score);
    }
}

int main() {
    Student students[] = {
        {"张三", 85},
        {"李四", 92},
        {"王五", 78},
        {"赵六", 90},
        {"钱七", 88}
    };
    int n = sizeof(students) / sizeof(students[0]);
    
    printf("排序前:\n");
    printStudents(students, n);
    
    // 按分数排序
    sortStudentsByScore(students, n);
    printf("\n按分数排序后:\n");
    printStudents(students, n);
    
    // 按姓名排序
    sortStudentsByName(students, n);
    printf("\n按姓名排序后:\n");
    printStudents(students, n);
    
    return 0;
}

3. 链表排序

#include <stdio.h>
#include <stdlib.h>

// 链表节点结构
typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建新节点
Node *createNode(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        fprintf(stderr, "内存分配失败\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 插入节点到链表末尾
void append(Node **head, int data) {
    Node *newNode = createNode(data);
    
    if (*head == NULL) {
        *head = newNode;
        return;
    }
    
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = newNode;
}

// 打印链表
void printList(Node *head) {
    Node *current = head;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

// 归并两个有序链表
Node *merge(Node *left, Node *right) {
    if (left == NULL) {
        return right;
    }
    if (right == NULL) {
        return left;
    }
    
    Node *result;
    if (left->data <= right->data) {
        result = left;
        result->next = merge(left->next, right);
    } else {
        result = right;
        result->next = merge(left, right->next);
    }
    return result;
}

// 找到链表中间节点
Node *findMiddle(Node *head) {
    if (head == NULL) {
        return head;
    }
    
    Node *slow = head;
    Node *fast = head->next;
    
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;
}

// 链表归并排序
Node *mergeSortList(Node *head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    
    // 找到中间节点
    Node *middle = findMiddle(head);
    Node *nextToMiddle = middle->next;
    
    // 分割链表
    middle->next = NULL;
    
    // 递归排序左右两部分
    Node *left = mergeSortList(head);
    Node *right = mergeSortList(nextToMiddle);
    
    // 合并排序后的链表
    return merge(left, right);
}

int main() {
    Node *head = NULL;
    
    // 创建链表
    append(&head, 12);
    append(&head, 11);
    append(&head, 13);
    append(&head, 5);
    append(&head, 6);
    append(&head, 7);
    
    printf("排序前: ");
    printList(head);
    
    head = mergeSortList(head);
    
    printf("排序后: ");
    printList(head);
    
    // 释放链表
    Node *temp;
    while (head != NULL) {
        temp = head;
        head = head->next;
        free(temp);
    }
    
    return 0;
}

总结

排序算法是计算机科学中的基础算法，本文介绍了C语言中常用的排序算法，包括：

基本排序算法：

冒泡排序：简单直观，适合小规模数据
选择排序：交换次数少，适合部分有序数据
插入排序：适合基本有序数据

高级排序算法： 4. 快速排序：平均性能最好，适合大规模随机数据 5. 归并排序：稳定，适合外部排序 6. 堆排序：原地排序，适合大顶堆/小顶堆场景

线性时间排序算法： 7. 计数排序：适合范围小的整数排序 8. 桶排序：适合均匀分布的数据 9. 基数排序：适合多位数排序

选择排序算法的依据：

数据规模
数据分布
内存限制
稳定性要求

通过理解和掌握这些排序算法，你可以根据具体场景选择最合适的排序方法，提高程序的性能和效率。

排序算法 ​

排序算法的基本概念 ​

排序的定义 ​

排序算法的分类 ​

按时间复杂度分类 ​

按空间复杂度分类 ​

按稳定性分类 ​

基本排序算法 ​

1. 冒泡排序 (Bubble Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

2. 选择排序 (Selection Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

3. 插入排序 (Insertion Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

高级排序算法 ​

4. 快速排序 (Quick Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

5. 归并排序 (Merge Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

6. 堆排序 (Heap Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

线性时间排序算法 ​

7. 计数排序 (Counting Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

8. 桶排序 (Bucket Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

9. 基数排序 (Radix Sort) ​

算法思想 ​

实现代码 ​

算法分析 ​

排序算法的比较与选择 ​

排序算法比较表 ​

排序算法的选择 ​

根据数据规模选择 ​

根据数据分布选择 ​

根据内存限制选择 ​

排序算法的实际应用 ​

1. 数组排序 ​

2. 结构体排序 ​

3. 链表排序 ​

总结 ​

排序算法

排序算法的基本概念

排序的定义

排序算法的分类

按时间复杂度分类

按空间复杂度分类

按稳定性分类

基本排序算法

1. 冒泡排序 (Bubble Sort)

算法思想

实现代码

算法分析

2. 选择排序 (Selection Sort)

算法思想

实现代码

算法分析

3. 插入排序 (Insertion Sort)

算法思想

实现代码

算法分析

高级排序算法

4. 快速排序 (Quick Sort)

算法思想

实现代码

算法分析

5. 归并排序 (Merge Sort)

算法思想

实现代码

算法分析

6. 堆排序 (Heap Sort)

算法思想

实现代码

算法分析

线性时间排序算法

7. 计数排序 (Counting Sort)

算法思想

实现代码

算法分析

8. 桶排序 (Bucket Sort)

算法思想

实现代码

算法分析

9. 基数排序 (Radix Sort)

算法思想

实现代码

算法分析

排序算法的比较与选择

排序算法比较表

排序算法的选择

根据数据规模选择

根据数据分布选择

根据内存限制选择

排序算法的实际应用

1. 数组排序

2. 结构体排序

3. 链表排序

总结