$\Large\color{black}{此更新针对近期某细心玩家提出的“边界问题”进行补充。}$

原帖位置

严格来讲，快速排序取中点作为枢值时，有向下取整和向上取整两种方式。原帖中主要针对序列划分和递归做了图解，代码以向下取整的方式为例，此帖给出向上取整的方式，并给出不同的边界处理方式，补全考研知识点的缺漏。

取中点时取整方式的不同，对应到代码中主要有变化的有两处：枢轴位置，递归参数

向下取整：

左右端点：left, right
枢轴位置：mid = (left + right) / 2
递归参数：QuickSort(arr, left, high), QuickSort(arr, high + 1, right)

向上取整：

左右端点：left, right
枢轴位置：mid = (left + right + 1) / 2
递归参数：QuickSort(arr, left, low - 1), QuickSort(arr, low, right)

两种方式递归参数是一一对应的，下图说明了互换之后会发生什么：

如果取中点时向下取整，但是递归参数用的是向上取整的参数$(left,low-1)$和$(low,right)$，那么如图所示$high=low+1$，且该段已经升序排列时，$pivotKey=1$，按照之前的划分方式，$low$和$high$都会移到1的位置，此时递归的参数分别为$(1,0)$和$(1,2)$，$(1,0)$由于$left > high$自动退出，$(1,2)$和递归前的参数完全一致，那么就会进入死循环，向上取整的例子同理。再补充一张图，代表递归参数和枢轴位置一一对应时，正确执行递归的演示：