洛谷p1923 数据过不了

题目的数据碰到就会死循环不输出，但是手打其他数据是可以的。

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn = 6e6;
int list[maxn]; int n,k;
void quicksort(int l, int r) {
    if (l >= r)return;/*左指针小于右指针*/
    int i = l, j = r,base = list[l];
    while (i < j) {
        while (i < j && list[j] >= base)--j;/*右指针指向元素理应大于基准元素*/
        while (i < j && list[i] <= base)++i;
        if (i < j)swap(list[i], list[j]);
    }
    swap(list[l], list[i]);/*将基准值换到正确的位置*/
    if (i == k+1) {
        printf("%d\n", list[i]);/*quicksort的特性*/
        return;
    }
    if(k+1<i)quicksort(l, i - 1);/*去小区间里搜*/
    else quicksort(i + 1, r);

}
int main() {
    while (scanf("%d%d", &n, &k) == 2) {
        memset(list, 0, sizeof(list));
        for (int i = 1; i <= n; ++i)scanf("%d", &list[i]);
        quicksort(1, n);
    }
}

修改后，可以试试

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
using namespace std;

const int MAXN = 5e6 + 5;
int a[MAXN], n, k;

int quick_select(int l, int r, int k) {
    if (l == r) return a[l];
    // 随机选取基准值
    int p = rand() % (r - l + 1) + l;
    swap(a[p], a[l]);
    int i = l, j = r, pivot = a[l];
    while (i < j) {
        while (i < j && a[j] >= pivot) --j;
        while (i < j && a[i] <= pivot) ++i;
        swap(a[i], a[j]);
    }
    swap(a[l], a[i]);
    if (k == i) return a[i];
    else if (k < i) return quick_select(l, i - 1, k);
    else return quick_select(i + 1, r, k);
}

int main() {
    srand(time(NULL));
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    printf("%d\n", quick_select(0, n - 1, k));
    return 0;
}

代码陷入死循环的原因是因为你的quick_sort函数有问题，有种情况 l==r && l == k+1 没有考虑到，导致什么都没输出，你需要将

if (l >= r)return;/*左指针小于右指针*/

修改为

if (l > r) return;/*左指针小于右指针*/
if (l == r && l == k + 1) {
    printf("%d\n", list[l]);
    return;
}

修改后实测可以AC

引用chatGPT作答，对于该代码实现的快速选择算法，我们可以发现在进行递归的时候，如果选定的基准值较小，递归将会一直向右子区间移动，直到右子区间为空，此时程序将会进入死循环，导致程序卡死。这很可能是因为在选择基准值的时候，我们选取的值过小，导致在递归时候总是会往右边移动。

为了避免这种情况的发生，我们可以尝试改变选择基准值的方式，例如可以通过随机选择基准值，或者选择多个元素然后取中位数作为基准值等方式来避免这种情况的发生。

另外，对于该代码中的快速排序算法，还存在以下问题：

对于重复元素的处理不够优秀，会导致算法的性能下降；
代码实现的快速排序算法是递归实现，存在函数调用的开销，对于大规模数据的排序效率可能不够理想；
代码中使用了递归调用，可能导致栈溢出的问题，需要特别注意。
因此，为了使代码更加健壮和高效，我们可以考虑使用其他更优秀的排序算法，例如堆排序、归并排序等，也可以考虑使用迭代实现的快速排序算法。

你代码里的k是啥意思？

该回答引用ChatGPT
这个问题可能是由于数据卡了快排的最坏时间复杂度引起的死循环。快速排序的最坏时间复杂度是$O(n^2)$，当选取的枢轴值（pivot）为最大或最小值时，会导致分区不平衡，在左边或右边的区间中递归快排的时间复杂度就会非常高，甚至退化为$O(n^2)$，导致超时或内存溢出。建议使用随机选择枢轴值或者中位数作为枢轴来避免最坏情况的发生。

代码中的问题可能也在于没有处理好边界条件。当通第一次排序确定了第$k+1$小的元素位置时，还需特判$i==k+1$的情况，及时输出第$k+1$小的元素。建议添加对边界情况的处理。

这段代码是快速排序求解第k小的数，但是在某些数据下会进入死循环并无法输出结果。可能原因是什么？

这段代码中没有判断基准元素是否合法，即基准元素有可能会取到数组边界上的值。当基准元素取到数组最后一个元素时，左右指针都会指向同一个位置，如果此时该位置上的值比基准元素大，则右指针不断向左移动，最终指向非法位置，导致程序出现死循环而无法输出结果。解决方法是固定基准元素的取值范围，例如可以将基准元素取为随机位置上的元素。

• 这有个类似的问题, 你可以参考下: https://ask.csdn.net/questions/7759237
• 你也可以参考下这篇文章：洛谷 P1909 买铅笔 题解
• 除此之外, 这篇博客: 程序设计-红皮书代码题记录中的 讲义P195-递归排序两个学生成绩链表 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 终于到了最后一题，递归排序我原以为是归并排序，原来是要求只要用递归实现的就行了，这里采用的是简单的插入排序的思想

  /*
  输入的内容：
  21190232 lisi 94
  21190121 zhangsan 100
  21190504 wangwu 83
  21190833 zhaoliu 88
  
  文件in.txt中的内容：
  21190125 qianqi 89
  21190602 zhouba 95
  21191127 sunjiu 78
  21190919 zhengshi 91
  
  */
  typedef struct studenttype
  {   
      int number;     //学号
      char name[20];  //姓名
      int score;      //成绩
      struct studenttype* next;
  }student;
  student* head1 = (student*)malloc(sizeof(student)); //链表1的头节点
  student* head2 = (student*)malloc(sizeof(student)); //链表2的头节点
  
  //将链表2的节点按大小逐个插入到链表1中
  //node1是链表1的节点，prenode1是node1的前驱节点，node2是链表2的节点
  void sort_twolist(student* prenode1, student* node1, student* node2)
  {
      //如果链表2已经遍历到结束，说明排序完毕
      if (node2 == NULL) return;
      //如果链表2还未结束，而链表1已经遍历到结束，则把链表2后续的节点都直接插入到prenode1的后面
      if (node1 == NULL)
      {
          prenode1->next = node2;
          return;
      }
      //如果node2的成绩比node1的成绩小，就把node2插入到prenode1和node1之间
      if (node1->score > node2->score)
      {
          student* reanode2 = node2->next;    //node2的后继节点
          prenode1->next = node2;
          node2->next = node1;
          //链表1变为prenode1->node2->node1
          //由于reanode2的成绩肯定大于等于node2的成绩，因此接下来比较reanode2和node1的成绩
          sort_twolist(node2, node1, reanode2);
      }
      //如果node2的成绩大于等于node1的成绩，就继续递归遍历链表1
      else
      {
          sort_twolist(node1, node1->next, node2);
      }
  }
  
  int main()
  {
      head1->next = NULL;
      head2->next = NULL;
      int n = 4;
      for (int i = 0; i < n; i++)
      {
          student* temp = (student*)malloc(sizeof(student));
          scanf("%d %s %d", &temp->number, temp->name, &temp->score);
          //边插入边排序
          student* it1, * it2;
          for (it1 = head1, it2 = head1->next; it2 != NULL;it1 = it1->next, it2 = it2->next)
          {
              if (it2->score > temp->score) break;
          }
          it1->next = temp;
          temp->next = it2;
      }printf("\n");
  
      FILE* fp = fopen("in.txt", "r");
      while (1)
      {
          student* temp = (student*)malloc(sizeof(student));
          fscanf(fp, "%d %s %d", &temp->number, temp->name, &temp->score);
          if (feof(fp)) break;
          //边插入边排序
          student* it1, * it2;
          for (it1 = head2, it2 = head2->next; it2 != NULL; it1 = it1->next, it2 = it2->next)
          {
              if (it2->score > temp->score) break;
          }
          it1->next = temp;
          temp->next = it2;
      }printf("\n");
  
  
      printf("排序前：\n\n");
      printf("链表1：\n");
      for (student* it = head1->next; it != NULL; it = it->next)
      {
          printf("%d %s %d\n", it->number, it->name, it->score);
      }printf("\n");
  
      printf("链表2：\n");
      for (student* it = head2->next; it != NULL; it = it->next)
      {
          printf("%d %s %d\n", it->number, it->name, it->score);
      }printf("\n");
  
      sort_twolist(head1, head1->next, head2->next);  //调用递归排序函数
  
      printf("排序后：\n\n");
      for (student* it = head1->next; it != NULL; it = it->next)
      {
          printf("%d %s %d\n", it->number, it->name, it->score);
      }printf("\n");
  
      return 0;
  }
  

   示例：

    

这是一份使用快排求解Top K问题的代码，思路是通过快排将数组分为两部分，一部分都小于基准值，一部分都大于基准值，然后判断基准值所在位置和K的大小关系，再分别对小区间和大区间递归调用。最终找到第K大的元素并输出。需要注意的是，K的值传入的是下标，因此在判断K和基准值所在位置关系时需要加1。

可能是程序中的一个小错误导致了死循环。可以尝试修改以下几处：

1. 在 quicksort函数中，应该把基准值选为 list[l]而不是 list[0]。因为数组下标从 0 开始时才需要选 list[0]，而这个程序中数组下标从 1 开始。
2. 在判断 i 是否等于 k+1 的时候，应该先判断 i 是否在数组范围内。具体来说，条件应该改为 if (i <= n && i == k+1)。
3. 如果希望程序对于每组数据都输出一次结果，则需要在 while 循环外部加上一个 printf("\n");，用于输出换行符。
   修改后的代码如下：
   #define _CRT_SECURE_NO_WARNINGS
   #include
   #include
   #include
   #include
   using namespace std;
   const int maxn = 6e6;
   int list[maxn], n, k;
   void quicksort(int l, int r) {
   if (l >= r) return; // 左指针小于右指针
   int i = l, j = r, base = list[l];
   while (i < j) {

    while (i < j && list[j] >= base) --j;  // 右指针指向元素理应大于基准元素
    while (i < j && list[i] <= base) ++i;
    if (i < j) swap(list[i], list[j]);
   

   }
   swap(list[l], list[i]); // 将基准值换到正确的位置
   if (i == k + 1) {

    printf("%d\n", list[i]);  // quicksort 的特性
    return;
   

   }
   if (k + 1 < i) quicksort(l, i - 1); // 去小区间里搜
   else quicksort(i + 1, r);
   }
   int main() {
   int cnt = 0;
   while (scanf("%d%d", &n, &k) == 2) {

    memset(list, 0, sizeof(list));
    for (int i = 1; i <= n; ++i) scanf("%d", &list[i]);
    quicksort(1, n);
    printf("\n");  // 每组数据输出一个换行符
   

   }
   return 0;
   }