单一函数的快速排序算法

Question

public static void sort(int[] a){
        if (a.length>1){
            int pivot=a[a.length-1];
            int left=0;
            int right=a.length-1;
            while(left<=right){
                while(a[left]<pivot)
                    left++;
                while(a[right]>pivot)
                    right--;
                if(left<=right){
                    int tmp=a[right];
                    a[right]=a[left];
                    a[left]=tmp;
                    left++;
                    right--;
                }
            }
            int[] tmp1=new int[right];
            for(int i=0;i<tmp1.length;i++)
                tmp1[i]=a[i];
            int[] tmp2=new int[a.length-right-1];
            for(int i=left;i<a.length;i++)
                tmp2[i-left]=a[i];
            sort(tmp1);
            sort(tmp2);
        }
    }

我试图用一个函数编写一种快速排序算法，但它不起作用。任何帮助都是值得赞赏的。谢谢

编辑：我解决了，谢谢大家的意见。

Answer 1

我认为问题是最后你没有使用

tmp1

和

tmp2

来符合新数组

a

...这是一种无需创建其他数组即可实现的方法：

    public static void sort(int[] a, int left, int right){
        if (left < right){
            int pivot = a[right];
            int pos = left - 1;
            for (int i = left; i < right; i++)
                if (a[i] <= pivot)
                    Swap(a, ++pos, i);
            Swap(a, pos + 1, right);
            sort(a, left, pos);
            sort(a, pos + 1, right);
        }

    }

    public  static void Swap(int[] a, int i, int j){
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }

排序的第一个调用必须是

sort(a, 0, a.length - 1)

希望对你有帮助

Answer 2

与大多数 int 排序方法相比，您的排序方法似乎非常出色。这是一个快速简单的方法。

public static void sort(int[] intArray){
    int n = intArray.length;
    int temp = 0;
    for(int i=0; i < n; i++){
        for(int j=1; j < (n-i); j++){
            if(intArray[j-1] > intArray[j]){
                temp = intArray[j-1];
                intArray[j-1] = intArray[j];
                intArray[j] = temp;
            }
        }
    }
}

这只是一个冒泡排序。我不明白递归的意义。还有许多其他类型的排序，但对于较短的数组长度，这是最简单的（IMO）。查找其他一些，他们所做的有点酷（排序算法）。

回答你的问题...... 就像@RobinCurbelo所说，你没有正确使用

temp1

和

temp2

。你的想法是存在的，但我认为你对你需要做的事情想得太多了。

Answer 3

你可以这样写代码，我不懂java，但这是pyhton中的代码： def fast_sort(my_arr, 低, 高):

pivot = my_arr[high]

pointer_1 = low
pointer_2 = low

while pointer_1 <= high:

    if my_arr[pointer_2] >= pivot:

        while (my_arr[pointer_1] > pivot):
            pointer_1 += 1

        holder = my_arr[pointer_1]
        my_arr[pointer_1] = my_arr[pointer_2]
        my_arr[pointer_2] = holder

    pointer_1 += 1
    pointer_2 += 1

index = pointer_2 - 1

if (low != index):
    quick_sort(my_arr, low, index-1)

if (high != index):
    quick_sort(my_arr, index+1, high)


return my_arr