链表+快速排序

TN Hacker

2025-06-19 18:25:27

发布于：北京

3阅读

0回复

0点赞

作者最不愿意写的来了
链表，是一种数据结构，链表和数组的区别包括数组大小固定，链表大小可动态调整
。链表不具有的特点是可随机访问任一元素。链表分为单向链表和双向链表。
链表需要指针来保存内存地址
链表和数组的优缺点：
数组：

优点：方便查找
缺点：删除和插入不方便，浪费时间

单链表：

优点：不浪费空间
缺点：改查不方便
链表有什么部分：
节点：包含数据域和指针域
数据域：包含数据
指针域：包含下一个结点的地址
头节点：数据域不保存数据
尾节点：指针域为空

样例：猴子选大王
题目描述
n只猴子按照身高从低到高顺时针围成一圈，编号为1~n，从编号为1的猴子顺时针从1开始报数，每次报到m的猴子就出圈，下一只猴子继续从1开始报数，如此反复，直到剩下一只猴子，它就是大王
代码：

#include <iostream>
using namespace std;

// 定义链表节点结构
struct Monkey {
    int id;         // 猴子的编号
    Monkey* next;   // 指向下一只猴子的指针
    
    // 构造函数
    Monkey(int num) : id(num), next(nullptr) {}
};

int main() {
    int n, m;
    cin >> n >> m;  // 输入猴子数量n和报数m
    
    // 处理特殊情况
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    
    // 创建循环链表
    Monkey* head = new Monkey(1);
    Monkey* current = head;
    
    // 构建链表，将n只猴子连接成环
    for (int i = 2; i <= n; i++) {
        current->next = new Monkey(i);
        current = current->next;
    }
    current->next = head;  // 最后一只猴子指向头节点，形成环
    
    // 初始化指针和计数器
    Monkey* prev = current;  // prev指向当前节点的前一个节点
    current = head;          // current指向当前节点
    int count = 1;           // 报数计数器，从1开始
    
    // 循环直到剩下一只猴子
    while (current->next != current) {
        if (count == m) {
            // 当前猴子出圈
            prev->next = current->next;  // 跳过当前节点
            Monkey* temp = current;
            current = current->next;     // 移动到下一个节点
            delete temp;                 // 释放内存
            count = 1;                   // 重新开始报数
        } else {
            // 继续报数
            prev = current;
            current = current->next;
            count++;
        }
    }
    
    // 输出最后剩下的猴子编号
    cout << current->id << endl;
    
    // 释放最后一个节点的内存
    delete current;
    
    return 0;
}

快速排序
快速排序实际上在代码量并不快速，不过运行效果还可以，时间复杂度最大为 O(n²)。
快速排序采用 “分治思想”，基本步骤如下：

选择基准值：从数组中选择一个元素作为基准（pivot）。
分区操作：将数组分为两部分，使得左边元素都小于等于基准，右边元素都大于等于基准。
递归排序：对左右两个子数组递归执行快速排序。
具体样例：
题目描述
给定含有 n 个整数的序列，请将这个序列升序排列。

注意：请用快速排序完成，输出第一行是排序前
代码：

#include <iostream>
#include <vector>
using namespace std;

// 交换两个元素
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}
// 打印数组
void printArray(const vector<int>& arr) {
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i];
        if (i < arr.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;
}
// 快速排序的分区函数
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[low];
    int left = low + 1;
    int right = high;
    
    while (true) {
        while (left <= right && arr[left] <= pivot) {
            left++;
        }
        while (left <= right && arr[right] >= pivot) {
            right--;
        }
        if (left > right) {
            break;
        }
        swap(arr[left], arr[right]);
    }
    swap(arr[low], arr[right]);
    return right;
}

// 快速排序函数
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        printArray(arr); // 输出每趟排序后的结果
        
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    int n;
    cin >> n;
    
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    printArray(arr); // 输出初始数组
    quickSort(arr, 0, n - 1);
    
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

热门讨论