快速排序C++实现（使用随机支点）崩溃并陷入无限循环

Question

我正在尝试把我的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;
}

Answer 1

在 C++ 中，你声明的数组不是动态的。这意味着你不能随意改变数组的大小。如果你想要一个可以动态调整大小的数组，你需要使用 std::vector，或者自己手动分配内存。否则，在这个快速排序的函数中：

lesser[j] = lst[i];

你会访问到一个超出范围的索引，这样会出错。

Answer 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'

这会立刻告诉你哪里出错了。