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

参考资料

苟且一下