代码之家  ›  专栏  ›  技术社区  ›  Dikshit Karki

快速排序在java中没有按预期工作

  •  0
  • Dikshit Karki  · 技术社区  · 4 年前

    我学会了快速排序的理论。我试着用java实现这个算法,但是我没有看到所有的数字都被排序,我不能指出我犯了什么错误。

    快速排序.java

    public class QuickSort {
    
        public void quicksort(int[] arr, int lb, int ub) {
            //up=upper bound
            //lb=lower bound
            
            if(lb<ub) {
              int loc=partition(arr,lb,ub);
              quicksort(arr,lb,loc-1);
              quicksort(arr,loc+1,ub);
            }
            
        }
        
        public int partition(int[] arr,int lb,int ub) {
            int pivot=arr[lb];
            int start=lb;
            int end=ub-1;
            
            while(start<end) {
                while(arr[start]<=pivot && start<arr.length-1) {
                    start++;
                    }
            
            while(arr[end]>pivot) {
                end--;
            }
            
            if(start<end) {
                swap(start,end,arr);
            }
            }
            
            swap(lb,end,arr); //swapping pivot value with end
            return end;
        }
        
          public void swap(int start,int end,int[] arr) {
             // System.out.println(end+" "+pivot);
              int temp=arr[start];
              arr[start]=arr[end];
              arr[end]=temp;
          }
    
    }
    

    主要类别:

    import java.util.Arrays;
    
    public class Program {
        
        public static void main(String[] args) {
            int[] arr= {7,6,10,5,9,2,1,15,7};
            QuickSort q=new QuickSort();
          q.quicksort(arr,0,arr.length);
          System.out.println(Arrays.toString(arr));
        }
    
    }
    

    我的输出是:

    [2, 5, 6, 7, 1, 7, 9, 10, 15]
    

    我重新检查了我的代码,并做了一些调试,但第一次通过它是工作良好。我不知道,在什么时候是错误的?

    0 回复  |  直到 4 年前
        1
  •  1
  •   KiwiB0y    4 年前

    这家伙做的正是你要找的:)看看他的 隔板

    Random pivot quicksort in Java

    以下是可以对helper函数执行的操作:

    public static void sort(int arr[], int lb, int ub) {
        if (lb < ub) {
    
            int part = partition(arr, lb, ub);
    
            // Sorts the partitions
            sort(arr, lb, part - 1);
            sort(arr, part + 1, ub);
        }
    }
    
    public static void displayArray(int[] arr) {
        System.out.print("[ ");
        for (int x :
                arr) {
            System.out.print(x + " ");
        }
        System.out.print("]");
    }
    
    public static void main(String[] args) {
    
        int[] arr = {7, 6, 10, 5, 9, 2, 1, 15, 7};
        int len = arr.length;
    
        displayArray(arr);
        sort(arr, 0, len-1);
        System.out.println();
        displayArray(arr);
    
    }