Android 图形化排序算法

发表于 | 分类于 | 评论数： | 阅读次数：

排序算法不好理解？那就来个 GUI 的!

上篇C语言实现各排序算法的完成，使得自己对排序有了一定的了解，最近看到一个 iOS 图形化排序过程，因此今天就完成 Android 端的图形化排序过程。

排序算法实现很简单，其重点是要实现安卓 View 跟随排序的动态变化。

由于计算机执行排序算法的高效性，对一定数量的数组排序都是 毫秒级 的，因此我们要考虑 放大排序时间，给可视化界面完整的动态过程。

一、总体功能界面

界面

maingif

功能

  • 六种排序算法完成
  • 可视动态化界面实现
  • 时间计时器
  • 算法时间复杂度说明

项目

  1. Android 图形化排序地址：https://github.com/jiyiren/JYSort
  2. C 实现排序项目地址：https://github.com/jiyiren/CSort

二、实现重点

数据与界面的初始化

  1. 数据是随机生成 100个数组 成一个数组，当然这个长度我们定义成全局变量，可以自行修改。
  2. 界面的初始化由上到下分别为 Toolbar菜单栏、主体排序可视窗口、时间复杂度 等。
  3. 重点在于中间主体排序 可视窗口的绘制：因为可视的 View 就是要表示数组中各个数据的大小，因而我们就将每个柱状 View 的高度用于表示数组中各个数据的大小，但是由于手机界面有限，如果有的数据过大那么绘制将超出屏幕。因此我们采取将 3/5 个屏幕像素与数组中最大值的比值作为每个数转为高度的一个因素，也就是说数组中数据不管多大，其高度最高最大为 3/5 个屏幕大小。而其宽度则是根据数组长度由屏幕宽度计算得出，具体如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//初始化界面的柱状图
private void initView() {
    if(ll_root==null){
        ll_root= (LinearLayout) findViewById(R.id.ll_root);
    }
    if(ll_sortpart==null) {
        ll_sortpart = (LinearLayout) ll_root.findViewById(R.id.ll_sortpart);
    }
    if(mViews.size()<=0) {
        for (int i = 0; i < mArray.length; i++) {
            View view = new View(this);
            ll_sortpart.addView(view);
            LinearLayout.LayoutParams layoutParams = (LinearLayout.LayoutParams) view.getLayoutParams();
            columnWidth = (screenWidth - DensityUtil.dp2px(this, paddingLR * 2)) / mArray.length
                        -DensityUtil.dp2px(this, intervalColumn);
            layoutParams.setMargins(DensityUtil.dp2px(this, intervalColumn), 0, 0, 0);
            layoutParams.height = (int) (mArray[i] * pixPerNum());
            layoutParams.width = columnWidth;
            view.setLayoutParams(layoutParams);
            view.setBackgroundColor(ContextCompat.getColor(this, R.color.colorPrimaryDark));
            mViews.add(view);
        }
    }
}    
//获得在高度上，单位数字所代表的像素，由于屏幕高度是像素，而我们的排序为int数字，要想形象化绘制成柱状图
//就要计算出单位数字的像素，然后通过数组中的数字相乘即可得到柱状view的高度了
private double pixPerNum(){
    columnPixPerNum=(double) screenHeight*0.6/(Max(mArray));
    return columnPixPerNum;
}
//获得数组中最大数字，仅仅用于@pixPerNum方法中
private int Max(int array[]){
    int max=0;
    for(int i=0;i<array.length;i++){
        if(max<array[i]){
            max=array[i];
        }
    }
    return max;
}

排序同时界面更新

  1. 界面的中每个柱状View与数组一一对应，这样我们只需要记住排序数组的下标就可以同步View数组了。
  2. 排序是耗时操作，我们需要开启线程进行排序，因此需要用到消息传递来通知界面的变化，这里主要使用Handler来进行处理线程消息。
  3. 整个流程为：在开启排序时，算法中的数组在进行数据交换时，我们会记录此时交换数据的两个下标，同时将这些数据包装成消息发送给Handler,Handler将界面柱状View数组中两个相同下标的View高度互换，达到界面显示与排序一致的效果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * 排序线程类
 */
class SortThread extends Thread{
    @Override
    public void run() {
        switch (currentSortKind){
            case 0://快速
                quicksort(mArray,0,mArray.length-1);
                break;
            case 1://堆
                HeadSort(mArray,mArray.length);
                break;
            case 2://归并
                int[] mtemp=new int[SIEZ_ARRAY];
                MergeSort(mArray,mtemp,0,mArray.length-1);
                break;
            case 3://插入
                insertsort(mArray,0,mArray.length-1);
                break;
            case 4://冒泡
                bubblesort(mArray,0,mArray.length-1);
                break;
            case 5://选择
                selectsort(mArray,0,mArray.length-1);
                break;
        }
        handler.sendEmptyMessage(WHAT_SORT_FINISH);
    }
}
/**
 * 选择排序
 * @param array
 * @param startIndex
 * @param endIndex
 */
void selectsort(int array[],int startIndex,int endIndex){
    int i,j,minIndex;
    for(i=startIndex;i<endIndex;i++){
        minIndex=i;
        //选出最小下标，放在最前面
        for(j=i+1;j<=endIndex;j++){
            if(array[minIndex]>array[j]){
                minIndex=j;
            }
        }
        if(minIndex!=i){
            int temp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=temp;
            //此处发送消息通知Handler更新View层变化
            sleepAndSendMessage(i,minIndex);
        }
    }
}
//交换两个View的高度，这是Handler处理界面变化的方法
private void swapColumHeight(View viewone,View viewtwo){
    LinearLayout.LayoutParams paramsone= (LinearLayout.LayoutParams) viewone.getLayoutParams();
    LinearLayout.LayoutParams paramstwo= (LinearLayout.LayoutParams) viewtwo.getLayoutParams();
    int temp=paramsone.height;
    paramsone.height=paramstwo.height;
    paramstwo.height=temp;
    viewone.setLayoutParams(paramsone);
    viewtwo.setLayoutParams(paramstwo);
}

排序延迟操作

由于排序算法只有在对数以万计的数据时才会有可见的时间长度，因而我们如果像正常一样设置排序和界面更新时，每个排序算法都几乎在毫秒级别完成，并且界面变化几乎不可见。

因此，我们需要让排序算法尽可能地延长一定时间，达到界面的变化可视化级别。

我们在数组交换数据时发送消息给 Handler 处进行了一定的时间延迟，当然不会过长，此处设置了 10ms。( 也同时因为这样的设置，界面显示的耗时操作实际上并非算法真正的排序时间，而应该减去延迟时间乘以延迟操作的次数。)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//交换的信号
private void sleepAndSendMessage(int i,int j){
    try {
    	 //此处延迟10ms
        Thread.sleep(10);
        Message message=new Message();
        message.what=WHAT_SORT_SWAP_VIEW;
        message.arg1=i;
        message.arg2=j;
        handler.sendMessage(message);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
}

三、动画演示

快速排序

fast

堆排序

heap

归并排序

merge

插入排序

insert

冒泡排序

bubble

选择排序

select

四、总结

项目

  1. Android图形化排序地址：https://github.com/jiyiren/JYSort
  2. C实现排序项目地址：https://github.com/jiyiren/CSort

参考资料

苟且一下