在我们的课本中，看到最多的就是选择第一个元素作为中轴，但是在很多书上却选择最后一个元素作为中轴。下面就让我们来一睹选取最后一个元素作为中轴的快排。
注：本文中的所有算法都采用双向扫描法，即，设两个下标i和j，i和右扫描，j向左扫描，直到i不小于j。而当下标为i的数小于中轴时，跳过并继续向右扫描，否则停止扫描，并开始j的向左扫描，相对地，当下标为j的数大于中轴时，跳过并继续向右扫描，否则停止扫描，然后交换下标为i和j的两个数，并从下一个位置继续两个方向的扫描，直到i不小于j。最后把中轴与下标为i的元素交换即完成一趟的快排。
下面就以最后一个元素作为中轴来说明。
初始数据为： 8 1 4 9 0 3 5 2 7 6
中轴为：6，第一趟快排的情景如下：
8 1 4 9 0 3 5 2 7 6
↑ ↑
i→ ←j
第一次交换后：
2 1 4 9 0 3 5 8 7 6
↑ ↑
i j
第二次交换后：
2 1 4 5 0 3 9 8 7 6
↑ ↑
i j
第三次交换前：
2 1 4 5 0 3 9 8 7 6
↑ ↑
j i
将下标为i的元素与最后一个元素（中轴）交换
即，一趟快排后：
2 1 4 5 0 3 6 8 7 9
对左边的数组和右边的数组重复上述过程。
选取最后一个元素作为中轴的好处是简单直观，操作一致。因为我们通常把下标为i的元素与中轴元素作为交换，而i则总是指向比中轴大的元素，而把大的元素放到后面总是合理的。
二、双向描述法中的越界问题
快速排序中都非常喜欢使用双向扫描法，然而这个方法却存在一个越界问题，考虑如下的情况：
8 1 4 6 9 3 5 2 7 0
i→ ←j
当我们选取最后一个元素作为中轴时，j向左扫描，一直到找到一个比0小的数，但是它却是数组中的最小值，所以j会一直向左走，直到越界。
这个问题无论是使用第一个元素作为中轴，还是使用最后一个元素作为中轴都会存在。所以，在双向描述中，必然有一个方向（远离中轴的方法）要做越界检查。
选取最后一个元素作为中轴的快排的关键代码
[cpp]
void QSort(DataType *data, int left, int right)
{
//如果数据的个小数为1或0则不需要排序
if(left >= right)
return;
//取最后一个元素作为枢纽
DataType centre = data[right];
int i = left;
int j = right-1;
while(true)
{
//从前向后扫描，找到第一个小于枢纽的值，
//在到达数组末尾前，必定结果循环,因为最后一个值为centre
while(data[i] < centre)
++i;
//从后向前扫描，此时要检查下标，防止数组越界
while(j >= left && data[j] > centre)
--j;
//如果没有完成一趟交换，则交换
if(i < j)
Swap(data[i++], data[j--]);
else
break;
}
//把枢纽放在正确的位置
Swap(data[i], data[right]);
QSort(data, left, i - 1);
QSort(data, i + 1, right);
}
三、随机选元法
我们知道，在快排中，中轴的选择对于算法的效率是非常重要的，选择一个好的中轴选择策略会使算法的效率显著提高。
无论是前面说的选取第一个元素还是最后一个元素作为中轴，其实都是一个坏的选元方法。因为当元素基本有序时，这两种方法都会使算法的效率非常低，最坏情况下，是O(n^2)。
随机选元法的思路：使用随机数生成函数生成一个随机数rand，随机数的范围为[left, right]，并用此随机数为下标对应的元素a[rand]作为中轴，并与最后一个元素a[right]交换，然后进行与选取最后一个元素作为中轴的快排一样的算法即可。
随机选元法仍然存在扫描越界问题，所以在远离中轴的方法上仍然需要检查下标。
随机选元法的关键代码
[cpp]
void QSort(DataType *data, int left, int right)
{
//如果数据的个小数为1或0则不需要排序
if(left >= right)
return;
//随机选取一个元素作为枢纽，并与最后一个元素交换
int ic = Random(left, right);
Swap(data[ic], data[right]);
DataType centre = data[right];
int i = left;
int j = right-1;
while(true)
{
//从前向后扫描，找到第一个小于枢纽的值，
//在到达数组末尾前，必定结果循环,因为最后一个值为centre
while(data[i] < centre)
++i;
//从后向前扫描，此时要检查下标，防止数组越界
while(j >= left && data[j] > centre)
--j;
//如果没有完成一趟交换，则交换
if(i < j)
Swap(data[i++], data[j--]);
else
break;
}
//把枢纽放在正确的位置
Swap(data[i], data[right]);
QSort(data, left, i - 1);
QSort(data, i + 1, right);
}
inline int Random(int begin, int end)
{
//产生begin至end，包括begin和end的随机数，即[begin, end]范围的整数
return rand()%(end - begin + 1) + begin;
}
从上面的代码也可以看出，随机选法与选取最后一个元素作为中轴的方法是非常相近的，只是多了把随机的中轴放到最后的位置的操作。
四、三数中值分割法