时间戳

首页 > 解决方案 > 快速排序递归 Java

java - 快速排序递归 Java

问题描述

我正在尝试使用递归对快速排序进行编码，但出现堆栈溢出错误。这是第二个递归函数给出的连续错误。我只是无法弄清楚。

public class QuickSortRec {
public static void quicksort(int input[],int a,int b)
{
    if(a<b)
    {
        int pivotpos=partition(input,a,b);
        quicksort(input, a,pivotpos-1);
        quicksort(input, pivotpos+1,b);
    }
}
private static int partition(int input[],int a,int b)
{
    int pivot=input[a];
    int count=0;
    for(int i=a+1;i< input.length;i++)
    {
        if(input[i]<pivot)
        {
            count++;
        }
    }
    int temp=input[a];
    input[a]=input[count];
    input[count]=temp;
    for(int i=0;i<count;i++)
    {
        if(input[i]>pivot)
        {
            for(int j=input.length-1;j>pivot;j--)
            {
                if(input[j]<pivot)
                {
                    temp=input[i];
                    input[i]=input[j];
                    input[j]=temp;
                }
            }
        }
    }
    return count;
}
public static void main(String[]args)
{
    int arr[]={6,2,10,8,15,3,4};
    int a=0;
    int b=arr.length-1;
    quicksort(arr,a,b);
    for(int i=0;i<arr.length;i++)
    {
        System.out.print(arr[i]+" ");
    }
  }
}

标签： javaarrayssorting

解决方案

我尝试调试您的程序，但并没有真正找到问题的解决方案，所以我决定尝试编写自己的解决方案，因为这个任务对我来说似乎很有趣。

所以我的目标是完全避免循环，只使用递归：

public static void main(String[] args)
{
    int   array[]     = { 6, 2, 10, 8, 15, 3, 4 };
    int[] sortedArray = quicksort(array);
    
    for (int currentNumber : sortedArray)
    {
        System.out.print(currentNumber + " ");
    }
}

static int index = 0;
static int tempIndex;

private static int[] quicksort(int[] inputArray)
{
    tempIndex = index;
    int totalArrayLength = inputArray.length;
    if (index != totalArrayLength - 1)
    {
        if (inputArray[index] > inputArray[index + 1])
        {
            int temporary = inputArray[index + 1];
            inputArray[index + 1] = inputArray[index];
            inputArray[index] = temporary;
            quickSort2(inputArray);
        }
        index++;
        quicksort(inputArray);
    }
    return inputArray;
    }

    private static void quickSort2(int[] inputArray)
    {
    if (tempIndex != 0 && inputArray[tempIndex] < inputArray[tempIndex - 1])
    {
        if (tempIndex != 0)
        {
            int temporary2 = inputArray[tempIndex];
            inputArray[tempIndex] = inputArray[tempIndex - 1];
            inputArray[tempIndex - 1] = temporary2;
            tempIndex--;
            quickSort2(inputArray);
        }
    }
}

推荐阅读