[就像标题说的那样,我正在尝试为QuickSort编写代码,但是我正在按照讲座中提供给我们的伪代码来进行此操作。这不是一个任务,这是因为我只是想自己弄清楚。我在线上找到了一个QuickSort示例,但它看起来与我们的psuedocode所说的有所不同。我在网上找到的QuickSort代码使用了指针,但我认为给定的psuedocode中没有提到指针。换句话说,有人可以检查即时消息是否在正确的路径上,并指出我的混乱之处。谢谢!
我的代码
#include <iostream>
using namespace std;
int Partition(int arr[], int p, int r)
{
int x = arr[r];
int i = p - 1;
for (int j = p; j < r - 1; j++)
{
if (arr[j] <= x)
{
i = i + 1;
swap(arr[i], arr[j]);
}
swap(arr[i + 1], arr[r]);
}
return i + 1;
}
void Quicksort(int arr[], int p, int r)
{
if (p < r)
{
int k = Partition(arr, p, r);
Quicksort(arr, p, k - 1);
Quicksort(arr, k + 1, r);
}
}
void print(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
int main()
{
int arr[] = { 5, 3, 4, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
Quicksort(arr, 0, n);
print(arr, n);
//I get an error here "Stack around the variable 'arr' was corrupted"
}
This is the psuedocode for my QuickSort functionPicture number two is the given psuedocode for my Partition function
在Partition()中,如果i从不增加,则完成swap(arr [p-1],...),这很可能是堆栈错误的原因。通常,快速排序参数是第一个和最后一个索引,而不是第一个和结束(= last + 1)索引,在这种情况下,它是Quicksort(arr,0,n-1)。内部循环正在寻找值
#include <iostream>
using namespace std;
int Partition(int arr[], int p, int r)
{
int x = arr[r];
int i = p; // fix
for (int j = p; j < r; j++) // fix
{
if (arr[j] < x) // fix
{
swap(arr[i], arr[j]);
i = i + 1; // fix
}
}
swap(arr[i], arr[r]); // fix
return i; // fix
}
void Quicksort(int arr[], int p, int r)
{
if (p < r)
{
int k = Partition(arr, p, r);
Quicksort(arr, p, k - 1);
Quicksort(arr, k + 1, r);
}
}
void print(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
int main()
{
int arr[] = { 5, 3, 4, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
Quicksort(arr, 0, n-1); // fix
print(arr, n);
return 0; // fix
}