我的快速排序实现有什么问题？

关于我的幼稚快速排序算法只是一个快速（哈哈）问题：我的快速排序实现有什么问题？

#include <iostream> 

template <class T> 
void quicksort2(T array[] , int start, int end){ 
    int i = start; 
    int j = end; 
    int temp; 
    int pivot = (end - start)/2; 

    // Partioning 
    while(i <= j){ 

    while(array[i] < array[pivot]){ 
     i++; 
    } 
    while(array[j] > array[pivot]){ 
     j--; 
    } 

    if(i <= j){ 
     temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     i++; 
     j--; 
    } 
    } 

    // Sorting partions 
    if(start <= j){ 
    quicksort2(array , start , j); 
    } 
    if(end >= i){ 
    quicksort2(array , i , end); 
    } 
}

当我运行一个测试阵列上的代码，它似乎只有阵列（不到边的左侧）被排序并且不会跳转到排序右侧并创建一个无限循环。

运行代码之前有点警告，有时会在我测试阵列上运行代码时冻结我的机器。

无论如何，感谢您的帮助！此外，这不是用于作业（什么类与排序算法需要你马上学习快速排序？）

来源

2014-01-17 The Alex

快速排序是我在大学的高级算法课程中学到的第一个算法，就像永远以前一样。 –

你正在运行windows吗？ –

你使用'temp'是有点危险的。 'temp'是'int'但是'array [i];'在'temp = array [i];'是'T'。我会建议使用['std :: swap']（http://en.cppreference.com/w/cpp/algorithm/swap），但看起来很愚蠢。我用手写了10次，9次好，1次错。讨厌的错误。 'std :: swap（array [i]，array [j]）'应该这样做，并且已经被模板化了。 – luk32

我会用问题回答你的问题。

如何处理在start == end时调用方法的情况？

每次运行都会将您的小节围绕数据点进行分割，因此每次递归运行时，您都有上次的1/2的长度。所以，你首先排序前半部分，然后是第一个1/4，然后是第一个1/8。最终，您将调用start = end = 0的方法。这使得0 - 0/2是数据透视表，它是0.

通过您的代码运行该案例，您会看到您不是处理您的方法尝试对其自身排序一个条目的情况。它会卡在一个无限的递归循环，直到它崩溃与...

堆栈溢出。

来源

2014-01-17 15:51:42

另外，你的数据透视计算是错误的。如果你的开始和结束是2和4，那么4 - 2 = 2/2 = 1。所以你的枢纽指数超出开始，结束的范围。 –

此外内部循环不是交叉检查（当'我'穿过'j'），所以你可以继续前进。 – wmorrison365

@LouLouviere啊，枢纽计算是不是我的意思是它。我曾打算将它作为（左+右）/ 2。感谢您的支持。在解决这个问题并实现代码来处理你描述的情况之后，代码现在可以正常工作。万分感谢！ –

你可能想看看你使用'='。我相信你可以使用> =和< =与枢轴点进行比较，但在进行交换时不需要。

然后kicker是递归调用 - 你肯定不想使用=那里，我认为这是一个无限递归的原因，它最终会崩溃，因为j永远不会比起始少。所以基本上每一个都与一个=比较，删除它，每一个没有=的比较，都加一个。

来源

2014-01-17 16:03:48

我的快速排序实现有什么问题？

回答

相关问题