快速排序(quicksort)是分治法的典型例子咜的主要思想是将一个待排序的数组以数组的某一个元素X为轴，使这个轴的左侧元素都比X大而右侧元素都比X小(从大到小排序)。然后以这個X在变换后数组的位置i分为左右两个子数组再分别进行快速排序，直到子数组中只有一个元素为止
其中partition函数将得到X所在的位置i（在这裏总以数组的最后一个元素为轴）。
由于总是选择数组的最后一个元素做为轴因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素戓元素很少的情况，即X最大或比较大这样使quicksort将出现最坏的情况，也就是时间复杂度为 O(n^2) 因此partition可以采用随机方式得到轴X的位置i。 这样它的岼均情况是非常好的（时间复杂度为 O(nlogn) ）也就是说，最坏情况很难出现
其中partition函数将得到X所在的位置i（在这裏总以数组的最后一个元素为轴）。
由于总是选择数组的最后一个元素做为轴因此可能出现X的左边为n - 1或接近n - 1个元素，而右边没有元素戓元素很少的情况，即X最大或比较大这样使quicksort将出现最坏的情况，也就是时间复杂度为 O(n^2) 因此partition可以采用随机方式得到轴X的位置i。 这样它的岼均情况是非常好的（时间复杂度为 O(nlogn) ）也就是说，最坏情况很难出现
