快速排序进入无限循环

我正在尝试编写快速排序的代码，但它始终在进行无限循环，我试图在下面的代码中找到错误，请有人帮忙。快速排序进入无限循环

#include<stdio.h> 
#include<stdlib.h> 

int arr[100]; 

void quicksort(int low,int high) 
{ 
    int i = low,j = high,pivotIndex,pivot; 
    pivotIndex = rand()%20; 
    pivot = arr[pivotIndex]; 

    if(i>=j) 
     return; 

    while(i<j) 
    { 

     while(arr[i]<pivot && i<j) 
     { 
      i++; 
     } 

     while(arr[j]>pivot && j>i) 
     { 
      j--; 
     } 

     if(i<j) 
     { 
      int temp = arr[i]; 
      arr[i] = arr[j]; 
      arr[j] = temp; 
     } 

    } 
    quicksort(low,i); 
    quicksort(i+1,high); 
} 

int main() 
{ 
    int i,j,temp; 

    for(i=0;i<20;i++) 
     arr[i] = rand()%21; 

    for(i=0;i<20;i++) 
     printf("%d ",arr[i]); 
    printf("\n"); 

    quicksort(0,19); 

    for(i=0;i<20;i++) 
      printf("%d ",arr[i]); 
    printf("\n"); 

    return 0; 
}

来源

2012-10-31 user1543957

@DEVENDERGOYAL：您的编辑更改的问题，实际上固定在它的错误之一，在这个问题上的一个问题是这样的错误。确保在编辑时 - 你不会改变问题本身。 – amit

你支点的选择是错误的，你应该选择在（指数）一转动范围[low,high)，当你在范围[0,20)选择了一个支点：

pivotIndex = rand()%20;

这稍后将分区不顺利，并且您后来用于递归的值i将是错误的。

编辑：

还有一个问题是与分配，也应该考虑到与枢轴元素及其重复做的 - 应该有某种“电网断路器” - 的数据透视应该转到数组的一侧（或者其他选择）。
例如，假设数据的关键是5，数组是[5,3,8,5]：
您将只是无限地交换5的一遍又一遍，这是错误的。

来源

2012-10-31 08:32:30 amit

-1

pivotIndex = rand()%20; 
pivot = arr[pivotIndex];

每次

在这里，您拨打的快速排序的pivotIndex可能不在范围内（低，高）。您可以使用

pivotIndex = low+rand()%(high-low);

我相信这将在范围内产生pivotIndex用。

来源

2012-10-31 08:39:47

'我确定这会生成范围内的pivotIndex。“它不会，考虑低= 10，高= 20，初始数组只有20个元素。（结果可能是pivotIndex == 29）你应该让他在指出问题后找出这个问题，IMO。 – amit

作为一个排序插件的作者，我可以向你保证，重新创建这些类型的算法可以真正让你成为众矢之的。 ; o）

必须特别注意（如前所述）选择主元，算法如何影响主元值（例如，VBA以浮点形式进行整数运算，导致各种奇怪），'剩饭'去的地方，最后一步如何处理最后一个分区（你不会第一个跳过这里的几条记录）。

下面是在许多语言排序算法的链接：

http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

来源

2012-10-31 11:05:06 Avan

快速排序进入无限循环

回答

相关问题