两个排序算法为同一个数组提供了两个不同的输出（quickSort和heapSort）！

我不明白为什么他们给我不同的输出，当我编译他们。例如，当我只编译一种算法时，答案是好的，另一种算法是一样的，但是当我编译它们时，它们给我一些奇怪的输出。两个排序算法为同一个数组提供了两个不同的输出（quickSort和heapSort）！

我的代码：

#include <iostream> 
using namespace std; 


int parent(int i){ 
    return i/2; 
} 
int leftChild(int i){ 
    return 2*i+1; 
} 
int rightChild(int i){ 
    return 2*i+2; 
} 
void maxHeapify(int a[], int i, int n){ 
    int largest; 
    int temp; 
    int l = leftChild(i); 
    int r = rightChild(i); 
    // p.countOperation("CMPbottomUp",n); 
    if (l <= n && (a[l] > a[i])) 
     largest = l; 
    else 
     largest = i; 
    //  p.countOperation("CMPbottomUp",n); 
    if (r <= n && (a[r] > a[largest])) 
     largest = r; 
    if (largest != i){ 
     // p.countOperation("ATTbottomUp",n); 
     temp = a[i]; 
     // p.countOperation("ATTbottomUp",n); 
     a[i] = a[largest]; 
     //p.countOperation("ATTbottomUp",n); 
     a[largest] = temp; 
     maxHeapify(a, largest, n); 
    } 
} 

void buildMaxHeap(int a[], int n){ 
    for (int i=n/2; i>=0; i--){ 
     maxHeapify(a, i, n); 
    } 
} 
void heapSort(int a[],int n){ 
    buildMaxHeap(a,n); 
    int n1=n; 
    int temp; 
    for(int i=n1;i>0;i--){ 
     temp = a[0]; 
     a[0] = a[i]; 
     a[i] = temp; 
     n1--; 
     maxHeapify(a,0,n1); 
    } 

} 

int partitionArray(int arr[], int left, int right){ 
    int i = left, j = right; 
    int tmp; 
    int pivot = arr[(left + right)/2]; 
    while (i <= j) { 
     while (arr[i] < pivot) 
      i++; 
     while (arr[j] > pivot) 
      j--; 
     if (i <= j) { 
      tmp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = tmp; 
      i++; 
      j--; 
     } 
    } 
    return i; 
} 

void quickSort(int arr[], int left, int right) { 
    int index; 
    index = partitionArray(arr, left, right); 
    if (left < index - 1) 
     quickSort(arr, left, index - 1); 
    if (index < right) 
     quickSort(arr, index, right); 
} 

int main(){ 
    int x[8]= {5,87,21,4,12,7,44,3}; 
    int a[8]; 
    for(int i=0;i<8;i++){ 
     a[i] = x[i]; 
    } 
    heapSort(x,8); 
    quickSort(a,0,8); 

    for(int i=0;i<8;i++){ 
     cout<<a[i]<<' '; 
    } 
    cout<<endl; 

    for(int j=0;j<8;j++){ 
     cout<<x[j]<<' '; 
    } 

    return 0; 
}

输出示例：

1）当我编译只有一个算法的输出为：3,4,5,7,12,21,44,87（其是好的）

2）当我在代码中编译它们的输出是：87,4,5,7,12,21,44,87（quickSort）和3,3,4,5,7 ，12,21,44（heapSort）

来源

2014-03-25 Di3sEl

使用调试器。 – Henrik

并打开编译器警告... – user3447428

编译程序好的只是让你知道代码是*语法*正确的。它并不能保证你的程序能够正常运行。如果程序无法按预期工作，那么您需要调试程序。你是否期望始终编写完美的程序，并且从不期望对它们进行调试？ – PaulMcKenzie

我认为应该工作：

heapSort(x,7); 
quickSort(a,0,7);

来源

2014-03-25 16:04:38 user3018144

Arrays a and x在堆叠中彼此相邻。看到你在输出中有多重值87，看起来你的排序函数访问你给它们的数组之外的内存。这是缓冲区溢出，一种未定义的行为。因此，你的代码可以做任何事情，因为你的变量值已经损坏（或者更糟，地址/指针被破坏）。

仔细检查你如何访问数组。请记住，长度为8的数组的C数组索引为0..7！

来源

2014-03-25 16:03:34 hyde

两个排序算法为同一个数组提供了两个不同的输出（quickSort和heapSort）！

回答

相关问题