Qt实现排序的可视化

网上有很多排序可视化的动图，闲来无聊我也用 QPainter 来绘制下，逐步完善中。（文末附 github 链接）

实现思路

这里面比较麻烦的是，每一次循环都需要暂停一段时间便于展示，但我们又不能在 UI 线程 sleep，能想到的方法有：

1. 使用 QEventLoop 开启事件循环，配合定时器或属性动画来延时，动画结束就退出事件循环进行下一步排序判断。 
2. 把排序操作的多重循环、递归展开为 if 形式，配合定时器。缺点是复杂的操作展开太麻烦，如果有 Python 那种 yeild 那就好了。
3. 使用多线程，UI 绘制动画效果（或者线程把绘制好的 Image 发送上来，或者线程里用两个 Image 轮流绘制），子线程进行排序操作。缺点是多线程设计起来太麻烦，交互和中途退出也不好设计。
4. 使用协程，但是得引入一个协程库，没有用事件循环方便。

事件循环方式（下图为冒泡排序）：

    QEvent loop;
    QTimer timer;
    connect(&timer, QTimer::timeout, &loop, &QEventLoop::quit);
    int len = arr.length();
    for (int arrI = 0; arrI < len - 1; arrI++)
    {
        for (int arrJ = 0; arrJ < len - 1 - arrI; arrJ++)
        {
            if (arr[arrJ] > arr[arrJ + 1]) {
                timer.start(500);
                loop.exec();
                qSwap(arr[arrJ], arr[arrJ + 1]);
            } else {
                timer.start(300);
                loop.exec();
            }
            update();
        }
    }

展开循环的方式（下图为冒泡排序）：

void BubbleSort::runStep()
{
    //冒泡排序，两层循环，这里for替换为if，方便重入
    if(_i < _sortData.count()-1)
    {
        if ( _j < _sortData.count()-1-_i)
        {
            if(_sortData[_j]>_sortData[_j+1])
            {
                //交换动画初始化
                _swapIndex=_j;
                _sortTimer.stop(); //步骤展示定时器
                _animationProgress=0;
                _animationLine.start(); //动画时间线
            }
            _jTemp=_j++;
            return;
        }
        ++_i;
        _j=0;
        _jTemp=0;
        return;
    }
    _isFinish=true;
}

多线程的方式，线程中使用条件变量来等待 UI 线程的定时/动画结束再去唤醒他（下图为冒泡排序）：

// ...
//排序线程中
        const int data_count=_sortData.count();
        for (int i=0; i arr[j + 1]) {
                std::swap(arr[j],arr[j+1]);
            }
        }
    }
}

选择排序

template
void selection_sort(std::vector& arr) {
    for (int i = 0; i < arr.size() - 1; i++) {
        int min = i;
        for (int j = i + 1; j < arr.size(); j++)
            if (arr[j] < arr[min])
                min = j;
        std::swap(arr[i], arr[min]);
    }
}