Qt实现排序的可视化

﹏ヽ暗。殇╰゛Y 2023-07-22 06:59 12阅读 0赞

网上有很多排序可视化的动图，我也用 QPainter 来绘制了下，目前实现了冒泡排序、选择排序（快速排序半完成）。（文末附 github 链接）

# 实现思路 #

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

> 1.  使用QEventLoop开启本地的事件循环，配合定时器来延时。这里面有个难点，双重循环中QEventLoop没法很好的中途退出，如果仅仅是展示还好。
> 2.  把排序操作的多重循环、递归展开为 if 形式，配合定时器。缺点是复杂的操作展开太麻烦，如果有 Python 那种 yeild 那就好了。
> 3.  使用多线程，UI 绘制动画效果（或者线程把绘制好的 Image 发送上来，或者线程里用两个 Image 轮流绘制），子线程进行排序操作。缺点是多线程设计起来太麻烦，交互和中途退出也不好设计。

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

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<data_count-1; i++)
            {
                for (int j=0; j<data_count-1-i; j++)
                {
    
                    _iTemp=j;
                    _jTemp=j+1;
                    _waitMutex.lock();
                    _waitCondition.wait(&_waitMutex);
                    if(!_runningFlag){
                        _waitMutex.unlock();
                        return;
                    }
                    if (_sortData[j]>_sortData[j+1]){
                        std::swap(_sortData[j],_sortData[j+1]);
                    }
                    _waitMutex.unlock();
                    emit sortUpdated();
                }
            }
    // ...
    //UI线程中
    //排序的定时器触发
        connect(&_sortTimer,&QTimer::timeout,this,[this]{
            if(isFinish()){
                _sortTimer.stop();
                emit sortFinished();
            }else{
                _waitMutex.lock();
                _waitCondition.wakeAll();
                _waitMutex.unlock();
            }
        });
    //此外，绘制时也要加锁

除了展现操作步骤，还需要展示交换动画，可以直接保存两者的下标，然后绘制时两者的横轴坐标加上偏移。

//两者横轴坐标之差  *  动画进度  =  横轴偏移
    const double animation_offset=(item_left_2-item_left_1)*_animationProgress;

# 实现效果与代码链接 #

下面展示实现效果：

### 冒泡排序 ###

template<typename T>
    void bubble_sort(T arr[], int len)
    {
        int i, j; 
        for (i = 0; i < len - 1; i++)
            for (j = 0; j < len - 1 - i; j++)
                if (arr[j] > arr[j + 1])
                {
                    std::swap(arr[j],arr[j+1]);
                }
    }

![2020040421224060.gif][]

### 选择排序 ###

template<typename T>
    void selection_sort(std::vector<T>& 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]);
        }
    }

![20200404212251347.gif][]

项目链接：[https://github.com/gongjianbo/VisualSort][https_github.com_gongjianbo_VisualSort]

[2020040421224060.gif]: /images/20230528/8332eeea2ba647c3972595cc1fe7e630.png
[20200404212251347.gif]: /images/20230528/558fdf8d28124205b8851a00268a7556.png
[https_github.com_gongjianbo_VisualSort]: https://github.com/gongjianbo/VisualSort