正文

C语言实现链表排序算法，轻松入门教程

/0 浏览量
0523

链表排序是数据结构中一个常见且实用的操作。在C语言中，我们可以通过多种方式对链表进行排序。本文将详细介绍几种常见的链表排序算法，并提供详细的代码示例，帮助您轻松入门链表排序。

1. 链表排序概述

链表是一种非线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表排序的目标是将链表中的节点按照某种顺序排列，如升序或降序。

2. 常见的链表排序算法

2.1 冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

2.1.1 冒泡排序算法步骤

  1. 从第一个元素开始，比较相邻的两个元素。
  2. 如果第一个比第二个大（升序排序），就交换它们两个。
  3. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  4. 针对所有的元素重复以上的步骤，除了最后已经排序好的元素。
  5. 重复步骤1~4，直到排序完成。

2.1.2 冒泡排序代码示例

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

// 定义链表节点结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

// 创建新节点
struct ListNode* createNode(int val) {
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// 冒泡排序
void bubbleSort(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    struct ListNode *i, *j;
    int swapped;
    for (i = head; i != NULL; i = i->next) {
        swapped = 0;
        for (j = i->next; j != NULL; j = j->next) {
            if (i->val > j->val) {
                // 交换节点值
                int temp = i->val;
                i->val = j->val;
                j->val = temp;
                swapped = 1;
            }
        }
        // 如果在这一轮没有发生交换，说明链表已经排序完成
        if (swapped == 0) {
            break;
        }
    }
}

// 打印链表
void printList(struct ListNode *node) {
    while (node != NULL) {
        printf("%d ", node->val);
        node = node->next;
    }
    printf("\n");
}

// 主函数
int main() {
    struct ListNode *head = createNode(5);
    head->next = createNode(2);
    head->next->next = createNode(8);
    head->next->next->next = createNode(1);

    printf("Original list: ");
    printList(head);

    bubbleSort(head);

    printf("Sorted list: ");
    printList(head);

    return 0;
}

2.2 选择排序

选择排序是一种简单直观的排序算法。它的工作原理是：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.2.1 选择排序算法步骤

  1. 遍历整个链表，找到最小（大）值。
  2. 将最小（大）值与链表头部节点交换。
  3. 将剩余链表视为新的未排序链表，重复步骤1和2，直到链表排序完成。

2.2.2 选择排序代码示例

// 选择排序
void selectionSort(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    struct ListNode *i, *j, *minNode, *temp;
    for (i = head; i != NULL; i = i->next) {
        minNode = i;
        for (j = i->next; j != NULL; j = j->next) {
            if (j->val < minNode->val) {
                minNode = j;
            }
        }
        // 交换节点
        temp = i->val;
        i->val = minNode->val;
        minNode->val = temp;
    }
}

2.3 插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序）。

2.3.1 插入排序算法步骤

  1. 从第一个元素开始，该元素可以认为已经被排序。
  2. 取出下一个元素，在已排序的元素序列中从后向前扫描。
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置。
  5. 将新元素插入到该位置后。
  6. 重复步骤2~5。

2.3.2 插入排序代码示例

// 插入排序
void insertionSort(struct ListNode *head) {
    if (head == NULL || head->next == NULL) {
        return;
    }
    struct ListNode *i, *j, *temp;
    for (i = head->next; i != NULL; i = i->next) {
        temp = i;
        j = i->prev;
        while (j != NULL && j->val > temp->val) {
            j->next = j->next->next;
            j->next->prev = j;
            j = j->prev;
        }
        temp->prev = j;
        temp->next = j->next;
        j->next = temp;
        j->next->prev = temp;
    }
}

3. 总结

本文介绍了C语言中几种常见的链表排序算法，包括冒泡排序、选择排序和插入排序。通过这些示例，您可以轻松入门链表排序。在实际应用中，您可以根据具体需求选择合适的排序算法，并对代码进行优化和改进。希望本文对您有所帮助！

-- 展开阅读全文 --