让数组排序动起来：利用OpenCV将数组排序可视化

让数组排序动起来：利用OpenCV将数组排序可视化

Comments 0 Comment

排序是基本的算法之一，常用的有选择排序、插入排序、起泡排序、归并排序、快速排序等，大多数程序语言也内置了对数组的排序操作。在学习阶段还是需要掌握和理解这些排序的规则的，如果把数组以图形的方式显示出来并把排序过程做成动画，会更容易理解与接受。今天就利用OpenCV来实现将排序展示出来。

OpenCV做成动态只需要记住使用cv2.waitKey(delay),就可以让画面停顿delay毫秒，我们可以在排序的每一步，停顿几十毫秒并将当前的数组以图形的方式展示出来，这样进行排序就可以将排序可视化。本文将用Python和C#对此任务进行讨论。

Python

Python安装OpenCV不再赘述，建立空的Main.py文件以及新建图片文件background.png。导入必要的包，以及预定义常量：

import cv2
import random
import math
N=500
upperbound=100
winSize=300
winName="sortviz"
delay_frame=50
delay_sorted=1000
backgroundColor=[0x80,0x80,0x80]
foreColor = [0xFF,0xFF,0x0]

N和upperbound是数组的大小和数组中元素可能的最大值，排序前的数组是通过随机数生成的，所以要预先给定数组中可能的最大值upperbound。接下来winSize和winName是窗口尺寸与窗口名称，在使用cv2.imshow(winName,mat)对图像更新时，只要名为winName的窗口存在，mat就会更新在名为winName的窗体中，从而实现动态的效果。设定每50毫秒刷新一次，排序结束后延迟为1000毫秒。背景色是灰色，前景色是Aqua，这里指定的就是[Blue,Green,Red]。

设计一个函数，用来进行快速排序

def qSort(a,lwbd,upbd):
    if(lwbd<upbd):
        t=a[lwbd]
        i=lwbd
        j=upbd
        while i!=j:
            while i<j and a[j]>t:
                j-=1
            if i<j:
                a[i]=a[j]
                i+=1
            while i<j and a[i]<=t:
                i+=1
            if i<j:
                a[j]=a[i]
                j-=1
        a[i]=t
        qSort(a,lwbd,i-1)
        qSort(a,i+1,upbd)

如果我们要通过控制台看排序的每步，应该在qSort()的递归调用前将列表a输出，而现在要将a显示在openCV的窗体上，就将更新语句放在这个位置。现在需要编写将列表a转换为图形的函数plotArray()，同时将qSort()包装一下：

def drawBackground():
    img[0:winSize,0:winSize]=backgroundColor
def fillRectangele(p1,p2):
    img[p1[0]:p2[0],p1[1]:p2[1]]=foreColor
def plotArray(a):
    drawBackground()
    columnWidth=winSize/N
    for i in range(len(a)):
        fillRectangele(
                (winSize-int(a[i]*winSize/upperbound),int(i*columnWidth)),
                (winSize,int((1+i)*columnWidth))
            )
    return
def qSort(a,lwbd,upbd):
    if(lwbd<upbd):
        t=a[lwbd]
        i=lwbd
        j=upbd
        while i!=j:
            while i<j and a[j]>t:
                j-=1
            if i<j:
                a[i]=a[j]
                i+=1
            while i<j and a[i]<=t:
                i+=1
            if i<j:
                a[j]=a[i]
                j-=1
        a[i]=t
        cv2.waitKey(delay_frame)
        plotArray(a)
        cv2.imshow(winName,img)
        qSort(a,lwbd,i-1)
        qSort(a,i+1,upbd)
    return
def QuickSort():
    a=[random.randint(0,upperbound) for _ in range(N)]
    qSort(a,0,len(a)-1)
    cv2.waitKey(delay_sorted)

每次将数组画在窗体上需要用drawBackground()重绘背景，从而将之前画的覆盖掉，然后将当前的数组在空白的背景上画出来。数组中a[i]的值画在图上缩放高为a[i]*winSize/upperbound，宽度为columnWidth的矩形。

这样，将background.png作为窗体显示，调整窗口尺寸为宽高均为winSize的3通道图像，接下来调用QuickSort()就可以把快速排序的过程展示出来了。

img = cv2.imread("background.png")
img.resize(winSize,winSize,3)
QuickSort()
cv2.waitKey(0)

要实现更多的排序按照类似的方法，在排序过程中加入cv2.waitKey(delay_frame)和plotArray(a)以及cv2.imshow()就可以画出相应排序的动态图像。例如冒泡排序

def BubbleSort():
    a=[random.randint(0,upperbound) for _ in range(N)]
    n=N-1
    while n>0:
        lastChangeIndex=0
        for i in range(n):
            if(a[i]>a[i+1]):
                t=a[i]
                a[i]=a[i+1]
                a[i+1]=t
                lastChangeIndex = i
        cv2.waitKey(delay_frame)
        plotArray(a)
        cv2.imshow(winName,img)
        n=lastChangeIndex
    cv2.waitKey(delay_sorted)

除了将数组a以柱状图的形式展示之外，还可以将a画成极坐标形式的散点，只需要将plotArray()函数进行修改。a[i]表示到图形中心的距离为a[i]*winSize/(2*upperbound)的一个点，不同点用不同的角度区分。

def drawPoint(x,y):
    w = 1
    l = 3
    img[x-l:x+l,y-w:y+w]=foreColor
    img[x-w:x+w,y-l:y+l]=foreColor
def plotArray(a):
    drawBackground()
    center = winSize/2
    dtheta = 6*math.pi/len(a)
    for i in range(len(a)):
        R = a[i]*winSize/(2*upperbound)
        drawPoint(
                int(center+R*math.cos(i*dtheta)),
                int(center+R*math.sin(i*dtheta))
                )
    return

C#

C#中使用OpenCV也非常方便，在Nuget管理包中安装OpenCvSharp，在程序前using OpenCvSharp;，同样是预定义一些常量，然后初始化数组。使用C#可以新建Mat类而不需要指定图片。新建Mat对象后，绘图过程与Python类似，不再赘述。

这里用C#实现了冒泡排序、选择排序、插入排序、快速排序。

class Program
{
    enum PolyMode
    {
        polar,
        linear
    };
    const int winSize = 500;
    const string winName = "sortedvis";
    const int N = 500;
    const int upperbound = 100;
    const int delay_sorted = 1000;
    const int delay_frame = 50;
    static void Main(string[] args)
    {
        List<int> a = new List<int>(N);
        for(int i=0;i<N;i++)
        {
            a.Add(0);
        }
        var board = new Mat(winSize, winSize, MatType.CV_8UC3);
        Cv2.NamedWindow(winName);
        BubbleSort(ref board, ref a);
        SelectionSort(ref board, ref a);
        InsertionSort(ref board, ref a);
        QuickSort(ref board,ref a);
        Cv2.WaitKey(0);
    }
    static void DrawBG(ref Mat mat)
    {
        mat.FillConvexPoly(new Point[] {
            new Point(0,0),
            new Point(winSize,0),
            new Point(winSize,winSize),
            new Point(0,winSize)
        }, Scalar.Gray);
    }
    static void PolyArr(ref Mat mat, ref List<int> a, string putText = null)
    {
    const PolyMode polyMode = PolyMode.polar;
        switch (polyMode)
        {
            case PolyMode.polar:
                kernal_PolarArr(ref mat, ref a, putText);
                break;
            case PolyMode.linear:
                kernal_ColumnArr(ref mat, ref a, putText);
                break;
            default:
                break;
        }
    }
    static void kernal_ColumnArr(ref Mat mat,ref List<int> a,string putText=null)
    {
        DrawBG(ref mat);
        var width = winSize / N;
        var expandRate = winSize / upperbound;
        for(int i=0;i<a.Count;i++)
        {
            mat.FillConvexPoly(new Point[]
            {
                new Point(i*width,winSize),
                new Point(i*width,winSize- a[i]*expandRate),
                new Point((i+1)*width,winSize-a[i]*expandRate),
                new Point((i+1)*width,winSize)
            },Scalar.Aqua) ;
        }
        if (putText != null)
        {
            Cv2.PutText(mat, putText, new Point(30, 30), HersheyFonts.HersheyDuplex, 1, Scalar.Black);
        }
        Cv2.ImShow(winName, mat);
    }
    static void kernal_PolarArr(ref Mat mat, ref List<int> a, string putText = null)
    {
        DrawBG(ref mat);
        var center = winSize / 2;
        var dtheta = 10*Math.PI/a.Count;
        for (int i = 0; i < a.Count; i++)
        {
            var R = (a[i]) * winSize*1.0 / (2*upperbound);
            mat.DrawMarker(new Point(center+R*Math.Cos(i*dtheta),center-R*Math.Sin(i*dtheta)),
                Scalar.Aqua,
                MarkerTypes.Cross,
                5);
        }
        if (putText != null)
        {
            Cv2.PutText(mat, putText, new Point(30, 30), HersheyFonts.HersheyDuplex, 1, Scalar.Black);
        }
        Cv2.ImShow(winName, mat);
    }
    static void BubbleSort(ref Mat mat, ref List<int> a)
    {
        shuffle(ref a);
        PolyArr(ref mat, ref a);
        int i, lastChangedIndex,t, n = a.Count-1;
        while(n>0)
        {
            lastChangedIndex = 0;
            for(i=0;i<n;i++)
            {
                if(a[i]>a[i+1])
                {
                    t = a[i];
                    a[i] = a[i + 1];
                    a[i+1]=t;
                    lastChangedIndex = i;
                }
            }
            Cv2.WaitKey(delay_frame);
            PolyArr(ref mat, ref a,"Bubble Sort");
            n = lastChangedIndex;
        }
        Cv2.WaitKey(delay_sorted);
    }
    static void SelectionSort(ref Mat mat, ref List<int> a)
    {
        shuffle(ref a);
        PolyArr(ref mat, ref a);
        int i, j, k, t;
        for(i=0;i<a.Count-1;i++)
        {
            k = i;
            for(j=i+1;j<a.Count;j++)
            {
                if (a[k] > a[j])
                    k = j;
            }
            t = a[i];
            a[i] = a[k];
            a[k] = t;
            Cv2.WaitKey(delay_frame);
            PolyArr(ref mat, ref a, "Selection Sort");
        }
        Cv2.WaitKey(delay_sorted);
    }
    static void InsertionSort(ref Mat mat,ref List<int>a)
    {
        shuffle(ref a);
        PolyArr(ref mat, ref a);
        int j,t;
        for(int i=1;i<a.Count;i++)
        {
            t = a[i];
            for( j=i-1;j>=0 && t<a[j];j--)
            {
                a[j + 1] = a[j];
            }
            a[j + 1] = t;
            Cv2.WaitKey(delay_frame);
            PolyArr(ref mat, ref a, "Insertion sort");
        }
        Cv2.WaitKey(delay_sorted);
    }
    static void QuickSort(ref Mat mat,ref List<int> a)
    {
        shuffle(ref a);
        PolyArr(ref mat, ref a);
        qSort(ref mat, ref a, 0, a.Count - 1);
        Cv2.WaitKey(delay_sorted);
    }
    static void qSort(ref Mat mat, ref List<int> a, int lwbd, int upbd)
    {
        if (lwbd < upbd)
        {
            int i, j, t;
            t = a[lwbd];
            i = lwbd;
            j = upbd;
            while (i != j)
            {
                while (i < j && a[j] > t)
                    j--;
                if (i < j)
                    a[i++] = a[j];
                while (i < j && a[i] <= t)
                    i++;
                if (i < j)
                    a[j--] = a[i];
            }
            a[i] = t;
            Cv2.WaitKey(delay_frame);
            PolyArr(ref mat, ref a, "Quick sort");
            qSort(ref mat, ref a, lwbd, i - 1);
            qSort(ref mat, ref a, i + 1, upbd);
        }
    }
    static void shuffle(ref List<int> a)
    {
        Random rd = new Random();
        for (int i=0;i<a.Count;i++)
        {
            a[i] = rd.Next(0, upperbound);
        }
    }
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注