xiaoyu's blog

Coding for a better life!

0%

可视化之快速排序

发表于 分类于 Disqus：

在线体验

设计思路

1. 排序算法部分

快速排序的思想就是在序列中选择一个支点pivot, 让小于pivot的元素放在它的左边，不小于（说大于的话不准确）它的元素放在它的右边。

visualgo.net 的实现，维护三个序列，s1, s2, unknown

s1中存放小于的元素，s2中存放不小于支点的元素，unknown是未排序序列（具体的区分在动画中很清楚）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function partition(a, i, j) {
  let m = i, p = a[i];
  for (let k = i + 1; k <= j; k++) {
    if (a[k] < p) {
      m++;
      swap(a, m, k);
    }
  }
  swap(a, m, i);
  return m;
}

function quickSort(a, low, high) {
  if (low < high) {
    int m = partition(a, low, high);
    quickSort(a, low, m - 1);
    quickSort(a, m + 1, high);
  }
}

2. 动画部分

排序的每一步操作存储在未来发生的回调函数执行队列中，全局变量 step 代表操作步数

假设每一步动画时延为1s，
那么在未来的0s, 1s, 2s, ..., step * 1s 将会在页面上看到具体的排序操作，
如果没有CSS的过渡效果，那么整个过程将会显得十分生硬。
例如我将第一个节点的位置与第3个节点的位置交换，
在 0s - 1s 有一段时间间隔，设置 transiton: all 1s 就能看到过渡效果。

完整代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
<script>
  let step = 0;
  let nodeList = document.getElementsByClassName('num'),
    reloadBtn = document.querySelector('.reload'),
    sortBtn = document.querySelector('.sort');
  let initColor = 'rgb(173, 216, 230)',
    sortedColor = 'rgb(255, 165, 0)',
    pivoColor = 'rgb(255, 255, 0)',
    s1Color = 'rgb(60, 179, 113)',
    s2Color = 'rgb(153, 50, 204)',
    activeColor = 'rgb(220, 20, 60)';

  let colorMap = {
    'sorted': sortedColor,
    's1': s1Color,
    's2': s2Color,
    'init': initColor,
    'pivo': pivoColor,
    'active': activeColor
  };
  let showConsoleNode = document.querySelector('.showConsole');
  let arr = [], timeout = 0.4, queue = [];

  function handleChange() {
    let selectOps = document.querySelector('#speed-control');
    // console.log(selectOps)
    let selectIdx = selectOps.selectedIndex;
    let val = selectOps.options[selectIdx].value;
    timeout = Number(val);
    console.log(timeout)
  }

  function swapPosition(node1, node2) {
    [node1.style.left, node2.style.left] = [node2.style.left, node1.style.left];
  }

  function setBgColor(nodeArr, color) {
    for (let i = 0; i < nodeArr.length; i++) {
      nodeArr[i].style.background = color;
    }
  }

  function swap(arr, i, j) {
    [arr[i], arr[j]] = [arr[j], arr[i]];
  }

  function createFrameForChangeColor(arr, step, nodeType) {
    setTimeout(() => {
      console.log('select:' + arr[0].innerText);
      setBgColor(arr, colorMap[nodeType]);
    }, step * timeout * 1.6 * 1000);
  }

  function createFrameForSwapPos(node1, node2, step) {
    setTimeout(() => {
      console.log(`swap ${node1.innerText}, ${node2.innerText}`);
      swapPosition(node1, node2)
    }, step * timeout * 1.6 * 1000)
  }

  function resetColorForPartOfArr(arr, l, r, m, step) {
    setTimeout(() => {
      for (let i = l; i <= r; i++) {
        let node = nodeList[arr[i].nodeIndex];
        if (i !== m) {
          setBgColor([node], initColor);
        } else {
          setBgColor([node], sortedColor);
        }
      }
    }, step * timeout * 1.6 * 1000);
  }

  function resetColorForAll(step) {
    setTimeout(() => {
      for (let i = 0; i < nodeList.length; i++) {
        let node = nodeList[arr[i].nodeIndex];
        setBgColor([node], initColor);
      }
    }, step * timeout * 1.6 * 1000);
  }


  function partition(a, i, j) {
    let m = i, p = a[i];
    createFrameForChangeColor([nodeList[a[i].nodeIndex]], step++, 'pivo');
    for (let k = i + 1; k <= j; k++) {
      createFrameForChangeColor([nodeList[a[k].nodeIndex]], step++, 'active');
      if (a[k].val < p.val) {
        m++;
        createFrameForChangeColor([nodeList[a[k].nodeIndex]], step++, 's1');
        createFrameForSwapPos(nodeList[a[m].nodeIndex], nodeList[a[k].nodeIndex], step++);
        swap(a, m, k);
      } else {
        createFrameForChangeColor([nodeList[a[k].nodeIndex]], step++, 's2')
      }
    }
    createFrameForSwapPos(nodeList[a[m].nodeIndex], nodeList[a[i].nodeIndex], step++);
    swap(a, m, i);
    resetColorForPartOfArr(arr, i, j, m, step++);
    return m;
  }

  function quickSort(a, low, high) {
    if (low <= high) {
      let m = partition(a, low, high);
      quickSort(a, low, m - 1);
      quickSort(a, m + 1, high);
    }
  }

  function init() {
    let fragment = document.createDocumentFragment();
    for (let i = 0; i < 10; i++) {
      let div = document.createElement('div'),
        num = parseInt(Math.random() * 10 + 1);
      arr.push({
        val: num,
        nodeIndex: i, //这里保存的是节点在nodeList中的位置
      });
      div.className = 'num';
      div.style.height = `${num * 20}px`;
      div.style.left = `${i * 50}px`;
      div.style.bottom = '0';
      div.style.background = initColor;
      div.style.transition = `left ${timeout}s, background ${timeout * 0.6}s`;
      div.innerText = num;
      fragment.append(div);
    }
    document.querySelector('.animate-contanier').append(fragment);
  }

  function reload() {
    arr = [];
    for (let i = 0; i < 10; i++) {
      let div = nodeList[i],
        num = parseInt(Math.random() * 10 + 1);
      arr.push({
        val: num,
        nodeIndex: i,
      });
      div.style.left = `${i * 50}px`;
      div.style.bottom = '0';
      div.style.height = `${num * 20}px`;
      div.innerText = num;
    }
  }

  init();
  document.querySelector('.sort').addEventListener('click', function () {
    quickSort(arr, 0, 9, 0);
    resetColorForAll(step)
  })
</script>