快速排序C++实现（使用随机数据透视表）中断并陷入无限循环

Question

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

请帮我看看这个bug并指出我在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

你有你不声明lesser也不greater有任何大小至少有一个主要问题：

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

所以后来当您尝试访问他们，你会出界：

lesser[j] = lst[i]; 

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

：后来当取它的大小将是 0

，然后

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

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

它告诉你马上什么是错的。

Answer 2

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

lesser[j] = lst[i]; 

正在访问索引超出界限。