java中的递归快速排序 [英] Recursive Quick Sort in java

问题描述

这是我的快速排序代码.它给了我一个错误的答案，但我认为我的分区函数是正确的.

This is my quicksort Code. It gives me a wrong answer but i think my partition function is correct.

public class Quick_Sort {

public static void main(String[] args) 
{

    int a[] = {99,88,5,4,3,2,1,0,12,3,7,9,8,3,4,5,7};
        quicksort(a, 0, a.length-1);
}

static int partition(int[] a, int low , int hi)
{
    int pivot = hi;
    int i =low;
    int j = hi-1;
    while(i<j)
    {
        if(a[i]<=a[pivot])
        {
            i++;
        }
        if(a[i]>a[pivot])
        {   
        if((a[i]>a[pivot]) && (a[j]<=a[pivot]))
        {
            int temp= a[i];
            a[i]=a[j];
            a[j]=temp;
            i++;    
        }
        if(a[j]>a[pivot])
        {
            j--;
        }
        }
    }
    int temp= a[i];
    a[i]=a[pivot];
    a[pivot]=temp;
    return i;
}
static void quicksort(int[] a, int low, int hi)
{
    if(low>=hi)
    {
        return;
    }
    int split = partition(a, low, hi);
    quicksort(a, low, split-1);
    quicksort(a, split+1, hi);
}
}

这是最终的输出:

1 0 3 2 3 4 4 5 5 7 3 7 8 9 12 88 99

1 0 3 2 3 4 4 5 5 7 3 7 8 9 12 88 99

试过试运行，看不到错误

Tried dry running it, couldn't see the error

推荐答案

在您的 partition 方法中，您已将 j 分配给 hi - 1.它应该只设置为 hi.

In your partition method you have assigned j to hi - 1. It should be set to hi only.

static int partition(int[] a, int low , int hi)
{
    int pivot = hi;
    int i =low;
//  int j = hi-1; // CHANGE THIS TO 
    int j = hi; // THIS 
    while(i<j)

<小时>

我在进行更改后得到了这个输出:

---

I got this output after I made that change:

[0, 1, 2, 3, 3, 3, 4, 4, 5, 5, 7, 7, 8, 9, 12, 88, 99]

<小时>

希望这会有所帮助！

---

Hope this helps!

这篇关于java中的递归快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！