使用 JavaScript 进行快速排序动画

• 下载源代码 - 1 Kb

引言

本文的目的是使用 JavaScript 展示一种可能的快速排序算法动画。快速排序是一种实用且快速的排序算法。它是计算机科学标准算法课程中的一个基本主题。快速排序算法是“分而治之”算法设计技术的一个很好的例子；这种技术的结果算法可以使用递归简洁而优雅地表达。为了帮助理解该算法，教育者可能会展示算法在特定输入上的执行过程。该过程通常显示输入数组的内容以及执行过程中各个阶段的其他关键参数。这本质上就是我们的 JavaScript 代码所做的，但方式更加生动。

动画快速排序算法可以从 此处 运行。

界面提供两种视图之一（显示下拉列表框）。在“收缩”视图中，每次调用算法时都会显示数组，并将 lo、hi 和 mid 参数的值显示在左侧。当前数组的线条显示会随着每次交换动态变化。在“展开”视图中，每次交换元素时，数组都会显示在单独的行上，并且交换的元素会使用不同的颜色高亮显示。在这两种视图中，lo 到 hi 的元素显示为灰色背景，而其他元素则显示为白色背景。枢轴元素以红色前景色标识。

用于动画的方法与作者在 汉诺塔 文章中提出的方法相同。正如作者所指出的，直接将 setInterval() 调用放在要动画化的过程中是混乱的根源。一种有效的方法是运行正常的非动画过程直到完成，同时使用堆栈保存感兴趣的参数。然后处理堆栈，并利用 JavaScript 的 setInterval() 函数结合一些视觉元素来显示算法的进度。

快速排序是如何工作的？

快速排序的递归算法可以用以下 Quicksort(A, lo, hi) JavaScript 函数表示：

function Quicksort(A, lo, hi) 
{  if (lo < hi) 
   {  var mid = Partition(A,lo,hi);
      Quicksort(A,lo,mid-1);
      Quicksort(A,mid+1,hi);
   } 
} 

该函数的输入是 待排序项的数组 A。lo 和 hi 参数分别表示数组中某个未排序部分的最低索引和最高索引。对于上述函数的初始调用，lo 和 hi 参数分别由调用者设置为数组的第一个（最左边）和最后一个（最右边）索引。

如前图所示，快速排序使用分而治之的策略，将输入数组分成两部分（段）并递归地对每个部分进行排序。快速排序使用一个辅助过程来就地分区其输入（就地意味着不使用额外的辅助数组）。分区过程如下进行：

它选择一个元素 P 并排列元素，使得 ≤ P 的元素移到序列的左侧，而 > P 的元素移到右侧。用于分区的元素 P 被称为 枢轴 元素。枢轴可以是待分区输入序列中的任何元素；然而，通常选择第一个（最左边）元素作为枢轴。

function Partition(A, lo, hi)
{// Input: An integer array A[lo..hi]  
 // Output: The array A arranged as: elements <= pivot, pivot, elements > pivot
 // Return the final position of pivot 
 // The pivot is A[lo] but it can be any of the elements A[lo], ..., A[hi];
 // If pivot is other than A[lo] then (at the start) swap it with A[lo]
 
   paramStack.push([-lo,hi]); // push lo and hi
   
   var pivot = A[lo];   
   var left = lo+1; 
   var right = hi;
   while (left <= right)
   {  while ((left <= right) && (A[left] <= pivot)) left++;
      while ((left <= right) && (A[right] > pivot)) right--;
      if (left < right)
      {  // save left and right parameters to paramStack array 
         paramStack.push([left,right]); 
         var t = A[left]; A[left] = A[right]; A[right] = t; left++; right--; 
      }
   }
  
   // Final swap: swap pivot with A[right] and return right (final pivot location) 
   A[lo] = A[right]; A[right] = pivot;
   paramStack.push([lo,right]); // push lo and right 
   return right;
}

一种简单的分区输入数组的算法由前面的 Partition() 函数给出。

注意：该函数在三个地方（粗体行）进行了修改，使用 paramStack.push() 来保存 lo 和 hi 值以及正在交换的数组元素的位置。

这使用了两个指针（left 和 right），分别设置为要分区的数组的开始和结束。左指针向右移动，跳过 ≤ pivot 的元素，而右指针向左移动，跳过 > pivot 的元素，但当左指针和右指针停止且 left < right 时，会交换相应的元素。当左指针和右指针相遇或交叉时，过程结束。然后执行一次涉及枢轴元素和右指针指向的元素的最终交换，将枢轴放到其正确排序的位置。

快速排序的动画

如前图所示，我们的动画快速排序程序代码由六个函数组成：

ExecuteQS()、Quicksort()、Partition()、ProcessStack()、PrintArray()、AnimateArrow()。

上图显示了这些函数之间的关系。Quicksort() 和 Partition() 函数如前所述。以下显示了其他函数的代码片段。

var A;  // The input array for Quicksort
var paramStack; // A global array used as a stack 

function ExecuteQS()
{ // Some initialization code goes here, omitted form brevity
  // The array A (global) is the input to Quicksort 
    
  paramStack=[]; // paramStack array is global
  var B = A.slice(); // Make a duplicate of array A
  Quicksort(A,1,A.length-1);
 
  A = B.slice(); // Restore array A 
  ProcessStack(); 
}

function ProcessStack()
{  var elem = document.getElementById("arr0");
   if (elem) elem.parentNode.removeChild(elem); 
   elem = document.getElementById("arr1");
   if (elem) elem.parentNode.removeChild(elem); 

   if (paramStack.length==0)  
   { PrintArray(A,-1,0); return; }
    
   gelem1 = null; gelem2 = null;
   newRow = false;
   var param = paramStack.shift(); // Get parameters from paramStack
    
   left = param[0]; right = param[1]; 
   
   if (left < 0)  // Check if parameters are lo and hi
   {  newRow =true;
      lo = -left;  hi = right; 
     
      prevleft = lo;  // a bug creeps if RHS is lo+1
      prevright = hi;
 
      param = paramStack.shift();  
     
      left = param[0]; right = param[1]; 
   } 
       
   dispLeft = left-prevleft; // no. of cells to move left arraow
   dispRight = prevright-right ; // no. of cells to move right arraow
   
   if (left==lo) dispLeft = right - prevleft;
   
   PrintArray(A, prevleft, prevright);
 
   prevright = right; prevleft = left;

   // Modify the array; the modified array will be shown the 
   // next time ProcessStack() (and thus PrintArray) is called
   var t = A[left]; A[left] = A[right]; A[right] = t; 
  
   if (!Timer1) Timer1 = setInterval(AnimateArrow,Speed); // Start animation
} 


function PrintArray(A, prevleft, prevright)
{ // This function renders the array A as an HTML list 
  // The program code is omitted for brevity  
}
function AnimateArrow()
{ // This function is called as a result of 
  // the call to setInterval() in ProcessSatck()
  // The program code is omitted for brevity 
}

结论

在渲染的动画中，left 箭头不允许移动到 right 箭头之外。这种行为是可以接受的，因为保存到堆栈中的数据是交换的位置，而不是指针 left 经过的所有位置。n=20 的“预定义”示例显示（输出的第一行）left 箭头没有移动，因为其当前位置是 right 箭头最终会到达的位置。

该程序代码已在最新版本的流行浏览器中进行了测试。它在最新版本的 IE（版本 11）、Chrome（版本 30）和 Firefox（版本 24）中都能正常工作。