用堆排序对字符串进行排序 | C++

Question

我是 C++ 新手我的代码有问题我想对字符串数组进行排序。使用选择排序，它可以工作但是使用堆排序，有一个问题是什么都没有打印出来（我也有合并排序的这个问题）我认为问题是 strcmp()，但 IDK 如何修复它

#include<iostream>
#include<cstring>
#define MAX_LEN 100

void heapify(char arr[][MAX_LEN], int size, int i);
void heapSort(char arr[][MAX_LEN], int size);
// MAIN
int main (){
  char arr[][MAX_LEN] = {"V", "Gorz", "Arta", "BM", "Monster"};
  int size = sizeof(arr) / sizeof(arr[0]);
  heapSort(arr, size);
  // printing array
  for(int i = 0; i < 0; i++){
    std::cout << arr[i] << " ";
  }
  std::cout << std::endl;
  return 0;
}
//==============================================================
// heapify function: check left and right children and also the parent
// and heapify it
void heapify(char arr[][MAX_LEN], int size, int i){
  
  int largest, l, r;
  largest = i;
  l = 2 * i;
  r = 2 * i + 1;
  //left child
  if(l < size){
    if(std::strcmp(arr[l], arr[largest]) > 0)
        largest = l;
  //right child
  }
  if(r < size){
    if(std::strcmp(arr[r], arr[largest]) > 0)
        largest = r;
  //if largest != i
  }
  if(largest != i){
    std::strcpy(arr[largest], arr[i]);
    heapify(arr, size, largest);
  }
} 
//==============================================================
// main heap sort function uses heapify function and then remove element
// one by one and re arrages it and heapify again
void heapSort(char arr[][MAX_LEN], int size){
  for(int i = size / 2 - 1; i >= 0; i--){
    heapify(arr, size, i);
  }
  for(int i = size - 1; i > 0; i--){
    std::strcpy(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

Answer 1

您的代码中存在一些问题。

以 heapify() 开头：

你正在计算一个堆元素的左边和右边为-

  l = 2 * i;
  r = 2 * i + 1;

假设 i 是 0。在这种情况下，它会将 l 作为 0，这是不正确的。应该是

  l = 2 * i + 1;
  r = 2 * i + 2;

这里，

  if(largest != i){
    std::strcpy(arr[largest], arr[i]);

您正在将 arr[i] 复制到 arr[largest]。因此，数组 arr 的 largest 索引处的字符串将被数组 arr 的 i 位置处的字符串覆盖。相反，您应该交换它们：

  if(largest != i){
    std::swap(arr[largest], arr[i]);
    ^^^^^^^^^

现在，heapSort() 中的问题：

这里，

  for(int i = size - 1; i > 0; i--){
    std::strcpy(arr[0], arr[i]);

你犯了同样的错误，将 arr[i] 复制到 arr[0]。相反，您应该交换它们：

  for(int i = size - 1; i > 0; i--){
    std::swap(arr[0], arr[i]);
    ^^^^^^^^^

现在，来到main()：

检查这个

  // printing array
  for(int i = 0; i < 0; i++){
                 ^^^^^

由于循环条件错误 (i < 0)，此循环体永远不会执行。循环条件应该是 i < size:

for(int i = 0; i < size; i++){
               ^^^^^^^^

用堆排序对字符串进行排序 | C++

sorting strings with heap sort | C++

c++

arrays

sorting

heap

heapsort