利用随机数方法实现从小到大的堆排序（注：不得使用泛型集合）

Question

static void Main(string[] args)
{
int[] array = GenerateRandomArray(10); // 生成随机数组
Console.WriteLine("原始数组:");
PrintArray(array);

    HeapSortAlgorithm(array); // 堆排序

    Console.WriteLine("排序后的数组:");
    PrintArray(array);
}

// 生成随机数组
static int[] GenerateRandomArray(int size)
{
    Random random = new Random();
    int[] array = new int[size];
    for (int i = 0; i < size; i++)
    {
        array[i] = random.Next(100); // 生成0到100之间的随机数
    }
    return array;
}

// 打印数组
static void PrintArray(int[] array)
{
    foreach (int num in array)
    {
        Console.Write(num + " ");
    }
    Console.WriteLine();
}

// 堆排序算法
static void HeapSortAlgorithm(int[] array)
{
    int n = array.Length;

    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
    {
        Heapify(array, n, i);
    }

    // 从堆中提取元素，逐个放置到数组末尾，并重新构建堆
    for (int i = n - 1; i > 0; i--)
    {
        // 将当前根节点（最大值）与数组末尾元素交换
        int temp = array[0];
        array[0] = array[i];
        array[i] = temp;

        // 重新构建堆，只需考虑根节点
        Heapify(array, i, 0);
    }
}

// 通过调整节点使其符合最大堆的性质
static void Heapify(int[] array, int n, int rootIndex)
{
    int largest = rootIndex; // 假设根节点最大
    int leftChild = 2 * rootIndex + 1;
    int rightChild = 2 * rootIndex + 2;

    // 比较根节点与左子节点
    if (leftChild < n && array[leftChild] > array[largest])
    {
        largest = leftChild;
    }

    // 比较根节点与右子节点
    if (rightChild < n && array[rightChild] > array[largest])
    {
        largest = rightChild;
    }

    // 如果根节点不是最大值，则交换根节点和最大节点
    if (largest != rootIndex)
    {
        int temp = array[rootIndex];
        array[rootIndex] = array[largest];
        array[largest] = temp;

        // 递归调整交换后的子树
        Heapify(array, n, largest);
    }
}

Answer 1

不知道你这个问题是否已经解决, 如果还没有解决的话:

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/7623125
• 这篇博客也不错, 你可以看下用递归的方法实现字符串的逆序（不调用库函数）
• 除此之外, 这篇博客: 【数据结构与算法】之深入解析“最优运动员比拼回合”的求解思路与算法示例中的 ② 随机化模拟 部分也许能够解决你的问题, 你可以仔细阅读以下内容或者直接跳转源博客中阅读:
  
  • 为每一个运动员随机生成一个战斗力（保证 firstPlayer 和 secondPlayer 为最大和次大），当两个运动员进行比拼时战斗力较高的获胜。
  • 不断模拟，统计 firstPlayer 和 secondPlayer 相遇的轮次的最大值和最小值即可。
  • 如果是看所有用例的总用时，那么需要根据 n 的大小来设置模拟次数。
  • C++ 示例：

  struct node {
      int a , b;
      bool operator <(const node &p) {
          return b < p.b;
      }
  }player[30];
  
  class Solution {
  public:
      vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
          srand(time(NULL));
  
          // 根据n的大小设置模拟次数
          int N;
          if(n <= 10)
              N = 800;
          else if (n <= 20)
              N = 8000;
          else N = 38000;
  
          int ans1 = 9999 , ans2 = 0 , rest , now;
          
          while(N--)
          {
              // 剩余的运动员
              rest = n;
  
              // 初始化战斗力
              for(int i = 1 ; i <= n ; i++)
              {
                  player[i].a = rand() % 1075943;
                  player[i].b = i;
              }
              player[firstPlayer].a = 11000000;
              player[secondPlayer].a = 10999999;
              
              // 统计轮次
              now = 1;
           
              // 模拟比赛
              while(rest > 1)
              {
                  for(int i = 1 ; i <= rest / 2 ; i++)
                  {
                      if(player[i].a < player[rest + 1 - i].a)
                          player[i] = player[rest + 1 - i];
  
                      // 统计firstPlayer和secondPlayer相遇轮次的最大值和最小值
                      if(player[i].b == firstPlayer && player[rest + 1 - i].b == secondPlayer)
                          ans1 = min(ans1 , now) , ans2 = max(ans2 , now);
                  }
                  now++;
                  rest = (rest + 1) / 2;
                  sort(player + 1 , player + rest + 1);
              }
          }
          
          vector<int> ans = {ans1 , ans2};
          return ans;
  
      }
  };
  

• 您还可以看一下 吴刚老师的【吴刚大讲堂】电商视觉的排版与应用方法课程中的 基础页面功能布局优化方法小节, 巩固相关知识点
  

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^