c++ - 堆排序从介绍到使用 vector 的 C++ 实现中的算法

Question

我一直在研究 C++ 中的堆排序函数，它遵循我们类(class)书籍《算法导论》第 3 版中的逻辑，但没有得到所需的输出。一直在脑海中解决这个问题并且很接近，但我没有看到我的错误。我正在使用 vector 并省略了从单独的文本文件中读取值的代码。

关于我在每个版本中的索引哪里出了问题有什么想法吗？添加，我用来测试的输入列表是 10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18。

我尝试的第一种方法更接近本书，但给出的输出为 10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1。如果我能弄清楚我是如何弄乱索引的，这是我的首选解决方案。

void maxHeapify(vector<int>&);
void buildMaxHeap(vector<int>&);
void heapSort(vector<int>&);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

heapSort(list);

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= A.size()) && (A[l] > A[i]))
    largest = l;
else
    largest = i;

if ((r <= int(A.size())) && (A[r] > A[largest]))
    largest = r;

if (largest != i)
{
    swap(A[i], A[largest]);
    maxHeapify(A, largest);
}
}

void buildMaxHeap(vector<int>& A)
{
for (int i = int((A.size()-1) / 2); i >= 1; i--)  
{
    maxHeapify(A, i);
}
}

void heapSort(vector<int>& A)
{

buildMaxHeap(A);
for (int i = int(A.size()-1); i >= 2; i--)  
    swap(A[1], A[i]);
    maxHeapify(A, 1);
}
}

我尝试的第二种方法以输出 2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 到 50 结束，这是一个随机排序的 50 个整数列表，但是在只有 20 个随机整数的列表中是正确的。代码如下:

void maxHeapify(vector<int>&, int, int);
void buildMaxHeap(vector<int>&, int);
void heapSort(vector<int>&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector<int> list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:\n";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
cout << "Sorted List:\n";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
    largest = r;

if (largest != i)
{
    swap(A[i - 1], A[largest - 1]);
    maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector<int>& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
    maxHeapify(A, i, n);
}
}

void heapSort(vector<int>& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 2; i--)
{
    swap(A[0], A[i]);
    maxHeapify(A, 1, i - 1);
}
}

Answer 1

书中提供的算法将索引视为 1,2,3....N , 它们从 1 开始。

所以只要遵循算法但记住一件事当我们访问数组时我们必须从索引中减去 1

所以你的第一个方法代码应该是:

void maxHeapify(vector<int>& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l-1] > A[i-1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r-1] > A[largest-1]))
    largest = r;

if (largest != i)
{
    swap(A[i-1], A[largest-1]);
    maxHeapify(A, largest, n);
}
}

在第二种方法中，您做错的是您正在检查关于基于 0 的索引 的边界。

我们不能通过此处基于 0 的索引，因为对于 0 索引，左 child 在索引 1 处，但 2*0 是0，所以 唯一的方法是在任何地方都使用基于 1 的索引，并且仅在访问您减去的元素时使用 - 1