小编use*_*525的帖子

所以我正在刷新我的算法知识并测试不同类型的运行时,我发现我的快速排序的实现比甚至插入和选择排序要慢得多.算法看起来对我来说,它在实践中看起来与我在网上找到的其他几个实现相同.但它必须以某种方式出错,因为它的排序比O(N ^ 2)排序慢500倍.对随机10000元素数组的3(深)副本进行排序时,给出:

插入排序:(75355000 ns)

选择排序:(287367000 ns)

快速排序:(44609075000 ns)

这是代码:

public static void quickSort(Thing [] theThings, int left, int right) {
    int i= left; int j = right;
    int pivot = theThings[(int)(left + (right-left)*0.5)].getValue();

    while (i <= j) {
        while (theThings[i].getValue() < pivot)
            i++;
        while (theThings[j].getValue() > pivot)
            j--;

        if (i <= j) {
            Thing temp = theThings[i];
            theThings[i] = theThings[j];
            theThings[j] = temp;

            i++;
            j--;
        }

        if (left < j)
            quickSort(theThings, left, j);
        if (right > i)  
            quickSort(theThings, i, …

我对Java synchronized()块的理解是,如果一个线程已经拥有一个对象的锁,它就可以在同一个对象上输入同步的另一个块(重入同步).在下面,我相信JVM使用引用计数来递增/递减线程获取锁定的次数,并且锁定仅在计数为零时释放.

所以我的问题是,如果遇到一段看起来像这样的代码:

synchronized(this)
{
    if (condition == WAITING)
    {
        synchronized(this)
        {
            condition = COMPLETE;

            notify();

            try
            {
                wait();
            }
            catch(InterruptedException  e)
            {
            }
        }
    }
    else
        condition = READY;
}

调用wait()时会发生什么？它只是减少计数,还是释放锁定而不管计数？

在第一种情况下,在我看来,如果发生锁重新进入会产生死锁,因为它仍然拥有锁,因此会在另一个等待它的线程上永远等待.

在第二种情况下,我无法真正看到第二个同步块的重点是什么.

wait()的文档说

"当前线程必须拥有此对象的监视器.线程释放此监视器的所有权并等待,直到另一个线程通过调用notify方法或notifyAll方法通知等待此对象监视器的线程唤醒.然后线程等待直到它可以重新获得监视器的所有权并恢复执行,"

所以我认为第二种情况是正确的,但我可能是错的.所以我错过了什么,或者我只是遇到了一个冗余的同步块,可以很容易地从代码中删除？