1

我正在尝试将我的 Python 快速排序实现翻译成 C++ 并编写了一些代码。代码似乎坏了。我正在使用 Xcode 进行开发，我所看到的只是，当我编译和运行代码时(lldb)，程序似乎陷入了无限循环。

请帮助我找到错误并指出我在 C++ 实现中哪里出错了。

Python 快速排序代码：

from random import randint

def quickSort(lst):
    if not lst:
        return []
    else:
        pivot_index = randint(0, len(lst) - 1)
        pivot = lst[pivot_index]
        lesser = quickSort([l for i, l in enumerate(lst)
                            if l <= pivot and i != pivot_index])
        greater = quickSort([l for l in lst if l > pivot])
        #print lesser, pivot, greater
        return lesser + [pivot] + greater

print quickSort([3, 2, 5, 6, 1, 7, 2, 4, 234, 234, 23, 1234, 24, 132])

C++ 快速排序代码：

#include <iostream>
#include <cstdlib>
#include <ctime>

using namespace std;

// simple print function 
void print(int* lesser, int len_lesser, int pivot, int* greater, int len_greater) {
    for (int i=0; i < len_lesser-1; i++) {
        cout << lesser[i] << " ";
    }
    cout << pivot << " ";
    for (int i=0; i < len_greater-1; i++) {
        cout << greater[i] << " ";
    }
    cout << endl;
}

unsigned long long rdtsc(){
    unsigned int lo,hi;
    __asm__ __volatile__ ("rdtsc" : "=a" (lo), "=d" (hi));
    return ((unsigned long long)hi << 32) | lo;
}

int randint(int len) {
    // srand(time(0));
    srand((unsigned)rdtsc());
    return (rand() % (len) + 0);
}
void quickSort(int* lst, int len) {
    if (lst == NULL) {
        cout << "List Empty" << endl;
        return;
    }
    else {
        int lesser[] = {};
        int greater[] ={};
        int j = 0;
        int k = 0;
        int pivot_index = randint(len);
        int pivot = lst[pivot_index];
        //cout << pivot << endl;
        for (int i=0; i < len-1; i++) {
            if (lst[i] <= pivot && i != pivot_index) {
                lesser[j] = lst[i];
                j = j+1;
            }
        }
        int len_lesser = sizeof(lesser)/sizeof(int);
        quickSort(lesser, len_lesser);

        for (int i=0; i < len-1; i++) {
            if (lst[i] > pivot) {
                greater[j] = lst[i];
                k = k+1;
            }
        }
        int len_greater = sizeof(greater)/sizeof(int);
        quickSort(greater, len_greater);
        print(lesser, len_lesser, pivot, greater, len_greater);
    }

}


int main() {
    int lst[] = {3, 2, 5, 6, 1, 7, 2, 4, 234, 234, 23, 1234, 24, 132};
    int len = sizeof(lst)/sizeof(int);
    quickSort(lst, len);
    return 0;
}
4

2 回答 2

4

在C++您声明的数组中不是动态的。您将不得不std::vector动态使用或分配数据。否则这些调用（在函数 quickSort 中）：

lesser[j] = lst[i];

正在访问超出范围的索引。

于 2013-03-21T14:43:20.870 回答
2

你至少有一个你没有声明lesser也greater没有任何规模的主要问题：

int lesser[]  = {};
int greater[]  ={};

因此，稍后当您尝试访问它们时，您将越界：

lesser[j] = lst[i];

然后再取它的大小0：

int len_lesser = sizeof(lesser)/sizeof(int);

干净的解决方案是使用std::vector然后你不用担心分配或大小。您应该尝试启用警告并始终使用它们进行编译。在使用它gcc运行时-Wall -W -pedantic不允许我编译，它告诉我：

 36:26: error: zero-size array 'lesser'
 37:26: error: zero-size array 'greater'

这会立即告诉您出了什么问题。

于 2013-03-21T14:46:55.367 回答