c++链表选择排序(找最小元素交换)

Question

昨天想试试链用表选择排序，结果写了好久都没实现。
用选择排序，双循环遍历链表，找到最小的元素和前面的交换指针位置。我发现两个元素相邻和不相邻交换代码不一样。而且指针的指向很乱很容易迷。
最后我妥协了，直接遍历，找到一个比它小的元素就交换里面的数据而不是交换指针(我感觉这样虽然简单了不少但效率很低，我并不想这样)。
找到一个小的就交换很简单，但是从内层循环里找到最小的再进行交换就会难很多，我就想不明白了。
请问大家之前写过类似的代码吗？可以教教我怎么弄吗？

Answer 1

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7738419
• 这篇博客也不错, 你可以看下问题：同一个进程中，先后对同一个文件描述符进行写入 / 读取 操作，读写指针的位置导致读取内容失败
• 除此之外, 这篇博客: C与C++程序设计学习笔记中的 5、某电视台举办了低碳生活大奖赛。题目的计分规则相当奇怪：每位选手需要回答10个问题（其编号为1到10），越后面越有难度。答对的，当前分数翻倍；答错了则扣掉与题号相同的分数（选手必须回答问题，不回答按错误处理）。每位选手都有一个起步的分数为10分。某获胜选手最终得分刚好是100分，如果不让你看比赛过程，你能推断出他（她）哪个题目答对了，哪个题目答错了吗？如果把答对的记为1，答错的记为0，则10个题目的回答情况可以用仅含有1和0的字符串来表示。例如：0010110011 就是可能的情况。你的任务是算出所有可能情况。每个答案占一行。 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• #include <stdio.h>
  int ti[11] = { 0 }; //用来存储每道题的回答情况0或者1,0表示错误，1表示正确
  //提醒：数组ti的编号实际用1-10
  //score表示当前得分，num是当前第num道题目
  void f(int score, int num)
  {
  	if (num == 11)//10道题目全部做完
  	{
  		if (score == 100)
  		{
  			int i = 0;
  			for (i = 1; i <= 10; i++)
  				printf("%d", ti[i]);
  			printf("\n");
  		}
  	}
  	else //10道题目没有做完
  	{
  		ti[num] = 1; //讨论第num道题目的正确情况
  		f(score * 2, num + 1);
  		ti[num] = 0; //讨论第num道题目的错误情况
  		f(score - num, num + 1);
  	}
  }
  int main(void)
  {
  	f(10, 1);//从基础分10分开始，从第1题开始
  	return 0;
  }
  

  
  
• 您还可以看一下 李宇豪老师的微信小程序支付&退款&物流接口思路讲解（付前后台代码+数据库文件）课程中的 课程全面介绍小节, 巩固相关知识点
  
• 以下回答由chatgpt基于相关博客总结生成:

  我可以为您提供一个使用选择排序在C++链表中找到最小元素并进行交换的示例代码。使用选择排序的主要思想是在内部循环中找到最小元素并将其与外部循环的当前元素交换。以下是示例代码：

  // 定义链表节点的结构体
  struct ListNode {
      int val;
      ListNode* next;
      ListNode(int x) : val(x), next(nullptr) {}
  };
  
  void selectionSort(ListNode* head) {
      ListNode* cur = head;
      while (cur != nullptr) {
          ListNode* minNode = cur;
          ListNode* p = cur->next;
          while (p != nullptr) {
              if (p->val < minNode->val) {
                  minNode = p;
              }
              p = p->next;
          }
          if (minNode != cur) {
              std::swap(cur->val, minNode->val);
          }
          cur = cur->next;
      }
  }
  

  该函数使用双重循环，在内部循环中搜索最小值并保存其节点指针，当内循环结束后，如果最小节点不是当前节点，则交换它们的值。外部循环每次迭代都会将当前节点移到下一个节点，并重复搜索和交换的过程，直到链表末尾。这样可以确保整个链表中所有节点都被正确排序。

  如果您需要对链表中节点的指针进行交换，使用 std::swap 函数可以很方便地完成。这里 std 是 C++ 标准库命名空间，swap 是其中的一个函数，可用于交换两个对象的值。如果您想使用手动交换指针，可以使用类似以下代码：

  ListNode* tmp = node1->next;
  node1->next = node2->next;
  node2->next = tmp;
  

  其中 node1 和 node2 是需要交换的节点，tmp 是一个指向节点的指针，用于保存其中一个节点的 next 指针，以便在交换过程中恢复连接关系。

  希望这个例子对您有所帮助！