快速排序

const count = ui.signal(20);
const speed = ui.signal(10);
const values = ui.signal([]);
const state = ui.signal({
arr: [],
ops: [],
index: 0,
running: false,
done: false,
pivot: -1,
left: -1,
right: -1,
settled: [],
message: '请生成随机数组'
});

let timer = null;
let generation = 0;

function stopTimer() {
generation++;
if (timer !== null) {
clearTimeout(timer);
timer = null;
}
}

function createPlan(input) {
const work = input.slice();
const ops = [];

function quickSort(low, high) {
if (low >= high) return;

const pivot = work[high];
let i = low - 1;

for (let j = low; j < high; j++) {
  ops.push({
    type: 'compare',
    i: j,
    j: high,
    pivot: high,
    message: '比较 ' + work[j] + ' 与基准值 ' + pivot
  });

  if (work[j] <= pivot) {
    i++;

    if (i !== j) {
      ops.push({
        type: 'swap',
        i: i,
        j: j,
        pivot: high,
        message: '交换两个元素'
      });

      const temp = work[i];
      work[i] = work[j];
      work[j] = temp;
    }
  }
}

if (i + 1 !== high) {
  ops.push({
    type: 'swap',
    i: i + 1,
    j: high,
    pivot: high,
    message: '基准值移动到正确位置'
  });

  const temp = work[i + 1];
  work[i + 1] = work[high];
  work[high] = temp;
}

ops.push({
  type: 'pivot',
  i: i + 1,
  j: high,
  pivot: i + 1,
  message: '基准值 ' + pivot + ' 已归位'
});

quickSort(low, i);
quickSort(i + 2, high);

}

quickSort(0, work.length - 1);
return ops;
}

function reset(input) {
stopTimer();
const arr = input.slice();

values.set(arr.slice());

state.set({
arr: arr,
ops: createPlan(arr),
index: 0,
running: false,
done: arr.length <= 1,
pivot: -1,
left: -1,
right: -1,
settled: [],
message: arr.length <= 1 ? '排序完成' : '准备排序'
});
}

function nextStep() {
const s = state.get();

if (s.index >= s.ops.length) {
state.set({
...s,
running: false,
done: true,
message: '排序完成'
});
return;
}

const op = s.ops[s.index];
const arr = s.arr.slice();
const settled = s.settled.slice();

if (op.type === 'swap') {
const temp = arr[op.i];
arr[op.i] = arr[op.j];
arr[op.j] = temp;
}

if (op.type === 'pivot') settled[op.pivot] = true;

const next = s.index + 1;
const done = next >= s.ops.length;

state.set({
...s,
arr: arr,
index: next,
running: false,
done: done,
pivot: op.pivot,
left: op.i,
right: op.j,
settled: settled,
message: done ? '排序完成' : op.message
});
}

function delay() {
return Math.round(1100 - speed.get() * 50);
}

function startAuto() {
const s = state.get();
if (s.done || s.running || !s.arr.length) return;

stopTimer();
const token = generation;

state.set({
...state.get(),
running: true,
message: '自动排序中'
});

function tick() {
if (token !== generation) return;

const current = state.get();

if (!current.running || current.index >= current.ops.length) {
  timer = null;
  state.set({
    ...current,
    running: false,
    done: true,
    message: '排序完成'
  });
  return;
}

const op = current.ops[current.index];
const arr = current.arr.slice();
const settled = current.settled.slice();

if (op.type === 'swap') {
  const temp = arr[op.i];
  arr[op.i] = arr[op.j];
  arr[op.j] = temp;
}

if (op.type === 'pivot') settled[op.pivot] = true;

const next = current.index + 1;
const done = next >= current.ops.length;

state.set({
  ...current,
  arr: arr,
  index: next,
  running: !done,
  done: done,
  pivot: op.pivot,
  left: op.i,
  right: op.j,
  settled: settled,
  message: done ? '排序完成' : op.message
});

if (done || token !== generation) {
  timer = null;
  return;
}

timer = setTimeout(tick, delay());

}

timer = setTimeout(tick, delay());
}

function randomArray() {
const n = count.get();
const arr = [];

for (let i = 0; i < n; i++) {
arr.push(5 + Math.floor(Math.random() * 96));
}

reset(arr);
script.toast('已生成 ' + n + ' 个随机数');
}

function render() {
const s = state.get();
const n = s.arr.length;
const total = s.ops.length;
const progress = total ? s.index / total * 100 : 0;
const max = Math.max(1, ...s.arr);
const barWidth = n <= 20 ? 9 : n <= 40 ? 5 : 3;

const bars = s.arr.map((value, i) => {
let color = '#64748B';

if (s.settled[i]) color = '#22C55E';
else if (i === s.pivot) color = '#F59E0B';
else if (i === s.left || i === s.right) color = '#38BDF8';

const barHeight = Math.max(3, Math.round(value / max * 130));

return ui.column([
  ui.stack([
    ui.text('', {
      width: barWidth,
      height: barHeight,
      background: color,
      radius: 1
    })
  ], {
    width: barWidth + 2,
    height: 136,
    justify: 'end',
    align: 'center'
  })
], {
  width: Math.max(barWidth + 2, Math.floor(310 / Math.max(1, n))),
  height: 140,
  justify: 'end',
  align: 'center',
  gap: 0
});

});

const sections = [
ui.heading('快速排序', {
size: 28,
lines: 1
}),

ui.text('QUICK SORT · 柱状图演示', {
  size: 13,
  color: '#94A3B8',
  lines: 1
}),

ui.divider({ color: '#475569' }),

ui.heading('随机数组设置', {
  size: 19,
  lines: 1
}),

ui.text('数组长度：' + count.get() + ' / 100', {
  size: 15,
  lines: 1
}),

ui.slider('调整数组长度', count.get(), v => {
  count.set(v);
}, {
  min: 5,
  max: 100,
  step: 1,
  accent: '#38BDF8'
}),

ui.button('随机生成', () => {
  randomArray();
}, {
  id: 'random',
  tone: 'primary'
}),

ui.divider({ color: '#475569' }),

ui.row([
  ui.text('数据量：' + n, {
    size: 14,
    lines: 1
  }),
  ui.text(s.done ? '已完成' : s.running ? '自动运行' : '已暂停', {
    size: 14,
    color: s.done ? '#22C55E' : '#38BDF8',
    align: 'right',
    lines: 1
  })
]),

ui.text('步骤：' + s.index + ' / ' + total, {
  size: 14,
  lines: 1
}),

ui.progress('执行进度', progress, {
  accent: '#38BDF8'
}),

ui.text(s.message, {
  size: 17,
  bold: true,
  lines: 2
}),

ui.text('橙色：基准值  蓝色：比较位置  绿色：已归位', {
  size: 12,
  color: '#94A3B8',
  lines: 2
})

];

if (n > 0) {
sections.push(
ui.scrollTop ? ui.text('柱状图：共 ' + n + ' 个元素', {
size: 13,
color: '#CBD5E1',
lines: 1
}) : ui.text('柱状图', {
size: 13,
color: '#CBD5E1',
lines: 1
})
);

sections.push(ui.row(bars, {
  gap: 0,
  align: 'end',
  justify: 'start'
}));

sections.push(ui.text(
  n <= 30 ? s.arr.join('  ') : '数据较多，使用窄柱显示',
  {
    size: 11,
    color: '#94A3B8',
    lines: n <= 30 ? 4 : 2
  }
));

}

sections.push(
ui.divider({ color: '#475569' }),

ui.heading('自动排序速度', {
  size: 19,
  lines: 1
}),

ui.slider('速度：' + speed.get() + ' / 20', speed.get(), v => {
  speed.set(v);
}, {
  min: 1,
  max: 20,
  step: 1,
  accent: '#38BDF8'
}),

ui.text('每步间隔约 ' + delay() + ' 毫秒', {
  size: 13,
  color: '#94A3B8',
  lines: 1
}),

ui.row([
  ui.button('单步执行', () => {
    stopTimer();
    const x = state.get();
    if (x.done || !x.arr.length) return;

    state.set({
      ...x,
      running: false
    });
    nextStep();
  }, {
    id: 'step',
    tone: 'primary',
    disabled: s.done || s.running || !n
  }),

  ui.button('自动排序', () => {
    startAuto();
  }, {
    id: 'auto',
    tone: 'primary',
    disabled: s.done || s.running || !n
  })
], { gap: 6 }),

ui.row([
  ui.button('暂停', () => {
    stopTimer();
    const x = state.get();

    state.set({
      ...x,
      running: false,
      message: x.done ? '排序完成' : '已暂停'
    });
  }, {
    id: 'pause',
    tone: 'neutral',
    disabled: !s.running
  }),

  ui.button('重新开始', () => {
    if (values.get().length) reset(values.get());
  }, {
    id: 'restart',
    tone: 'neutral',
    disabled: !n
  })
], { gap: 6 }),

ui.heading('排序结果', {
  size: 18,
  lines: 1
}),

ui.text(s.done ? s.arr.join(', ') : '排序完成后显示最终结果', {
  size: 13,
  color: s.done ? '#22C55E' : '#94A3B8',
  lines: 8
})

);

return sections;
}

reset([]);
ui.setTitle('快速排序可视化');
ui.render(render);