-1

在使用快速排序对数组进行排序之前，我想检查数组是否已排序。我总是在第 77 行遇到 stackoverflow，或者在第 65 行遇到数组索引越界错误。我的基本想法是检查前两个数字是否已排序，然后检查第二个和第三个，依此类推。如果它们未排序，则整个 while 循环应取消并使用快速排序开始排序，使用最后一个正确的排序值作为比较值。

public class customQuickSort 
{
    Runtime runtime = new Runtime();

    private int[] a;
    private int n;
    boolean isSorted = true;
    int arraySortCount = 0;
    int x = 0;

    public customQuickSort(int[] unsorted)
    {
        sort(unsorted);
    }
    @Override
    public void sort(int[] a)
    {
        this.a=a;
        n=a.length;
        runtime.start();
        quicksort(0, n-1);
        runtime.end(getCounter());
    }

    private void quicksort (int lo, int hi)
    {
        int i=lo, j=hi;
        while(isSorted = true && arraySortCount < a.length-1)
        {
            if(a[arraySortCount] <= a[(arraySortCount+1)])
            {
                if(arraySortCount == a.length-2)
                {
                    System.out.println("array sorted ascending");
                }
            }
            else if(a[arraySortCount] >= a[(arraySortCount+1)])
            {
                if(arraySortCount == a.length-2)
                {
                    System.out.println("array sorted descending");
                }
            }
            else
            {
                isSorted = false;
                x=a[c(arraySortCount)];
                System.out.println("unsorted");
            }
            arraySortCount++;
        }
        if(isSorted == false)
        {

            while (i<=j)
            {    
                while (a[i]<x)
                {
                    i++; 
                }
                while (a[j]>x) 
                {
                    j--; 
                }
                if (i<=j)
                {
                    exchange(i, j);
                    i++; j--;
                }
            }

            if (lo<j) quicksort(lo, j);
            if (i<hi) quicksort(i, hi);
        }
    }

    private void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
4

1 回答 1

1

只需使用

Arrays.sort(T[], Comparator<? super T> c)

它使用高度优化的排序算法

实现说明：此实现是一种稳定的、自适应的、迭代的归并排序，当输入数组部分排序时，它需要的比较次数远少于 n lg(n)，而当输入数组是随机排序时，它提供了传统归并排序的性能。如果输入数组接近排序，则实现需要大约 n 次比较。临时存储要求从几乎排序的输入数组的小常数到随机排序的输入数组的 n/2 对象引用不等。

该实现在其输入数组中平等地利用升序和降序，并且可以在同一输入数组的不同部分利用升序和降序。它非常适合合并两个或多个排序数组：只需连接数组并对结果数组进行排序。

该实现改编自 Tim Peters 的 Python 列表排序 (TimSort)。它使用了 Peter McIlroy 在 1993 年 1 月的第四届 ACM-SIAM 离散算法研讨会论文集上的“乐观排序和信息理论复杂性”中的技术。

在这里阅读更多

于 2013-11-03T17:52:01.913 回答