时间戳

首页 > 解决方案 > 自定义快速排序在 java 中不起作用

java - 自定义快速排序在 java 中不起作用

问题描述

我已经实现QuickSort了，但是由于某些奇怪的原因，我的代码给出了 StackOverflow 异常。我一直在努力理解为什么我的代码会破坏任何想法，为什么我的代码会被破坏？还有其他方法可以优化吗？递归导致我的堆栈溢出；但不能放在发生这种情况的地方！

   import java.io.*;
   import java.util.*;
   import java.text.*;
   import java.math.*;
   import java.util.regex.*;

public class Solution {

    static void quickSort(int[] arr,int low,int high) {
        // Complete this function
        int p =partition(arr,low,high);
         System.out.println("partiion at p[]"+p); 
        if(low<p){

            System.out.println("starging quickSort at low[]"+low+" hgh["+(p-1)); 
            quickSort(arr,low,p-1);    
        }

        if(p<high){
            System.out.println("starging quickSort at low[]"+p+1+" hgh["+high); 
            quickSort(arr,p+1,high);    
        }


    }
    static void swap(int []a,int x,int y){
        int tmp = a[y];
        a[y]=a[x];
        a[x]=tmp;
    }

    static int partition(int[] arr,int low,int high){
        int pivot = arr [low+ (high-low)/2];
        int left  = low;
        int right = high;
        System.out.println("pivot["+pivot+"] left ["+left+"]right["+right+"]");


        while(left<= right)
        {

            while(arr[left] < pivot){
                left++;
            }
            System.out.println("**..done now left ["+left+"]");


            while(arr[right] >pivot){
                right--;
            }

            System.out.println("##..done now right ["+right+"]");

            if(left <=right){
                swap(arr,left,right);
                right--;
                left++;
            }

                        System.out.println("#swapping");


            for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }

            System.out.println("done#swapping");
        }            

        return left;
    }
    static int[] quickSort(int[] arr) {
        quickSort(arr,0,arr.length-1);
        return arr;

    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int arr_i = 0; arr_i < n; arr_i++){
            arr[arr_i] = in.nextInt();
        }
        System.out.println("ubsoted ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + (i != arr.length - 1 ? " " : ""));
        }
        System.out.println("");

        int[] result = quickSort(arr);
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i] + (i != result.length - 1 ? " " : ""));
        }
        System.out.println("");


        in.close();
    }
}

标签： javaquicksort

解决方案

您没有指定返回语句，这就是递归调用快速排序时堆栈溢出的原因。

因此，在快速排序方法中添加这样的返回条件作为第一条语句。

static void quickSort(int[] arr,int low,int high) {

     if (high <=low) {
         return;
     }

推荐阅读