快速排序 是对冒泡排序的改进算法，其平均复杂度是O(nlogn)，是一种不稳定的排序算法，其基本流程如下：
与归并排序类似，用分支的思想，假设有三个数 1 0 -1 需要升序排列，约定，从中随机选择一个数作为 基准点，将大于基准点的数放在基准点的右侧，小于基准点的数放在左侧，则能得到：
若选择 1 作为基准点，则有：0，-1，1 和 -1，0，1 两种可能的情况，其中有一种（-1，0，1）是已经排好序的情况，另一种则需要在 0，-1之间再选择一个基准点进行排序才能排好若选择 0 作为基准点，则只有 -1，0，1这一种情况，即排好序的情况若选择 -1 作为基准点，则也有两种情况而快速排序正是这样的一个大流程：选择基准点，将大于基准点的数放至右侧，小于基准点的数放置左侧，然后在左侧重新选择基准点，重复进行，因此，选择基准点就尤为重要，如果选择的不好，则会出现像上面三个数却要选择两次基准点的情况；如果选择的好，即最优情况，每次选择的基准点都是当前要排列的部分的中间值，此时快速排序算法达到最优。一般情况下，基准点不会选择当前需要排列的部分的最值，但也不太可能每次都选择的是中间值，因为选择基准点不可能比较所有的数然后找出中间值（那样还不如直接排序），所以，只要保证基准点不是最值就能保证快速排序不会到它的最差解（最差就是冒泡排序的O(n^2)，相当于每次的基准点都是最大值或最小值，此时每一轮只排了一个数），做法是比较要比较的部分的第一个数、中间数以及最后一个数的大小，把这三个数中第二大的数交换到这一部分的开头即可（放到开头是保证交换完之后这个基准点会处于中间的某一位置），详细流程如下：
初始数组为 1, -1, 2, 5, -4, 0, -2, -3, 3, 4 选择基准点： 比较整个数组第 0 个、第 （0+9）/ 2 = 4 个，第 9 个数的大小，即 1，-4，4 三者大小，选择 1 作为基准点，并将其放到左端，即第 0 的位置，将这三个数交换成1，-4，4的位置（但在原数组还是处于这三个位置）： 数组变为 1, -1, 2, 5, -4, 0, -2, -3, 3, 4，1 是基准点，按如下方式进行交换： 先从尾部开始比较，如果大于基准点则不用动，小于基准点则将它覆盖到左端，然后从头部开始，如果小于基准点则不用动，大于基准点则将它覆盖到右端，然后再从尾部…这样循环： 1, -1, 2, 5, -4, 0, -2, -3, 3, 4，1 为基准点，首先比较尾部，大于 1 的不用动，第一个小于 1 的数是 -3，将其覆盖左端得到数组 ： -3, -1, 2, 5, -4, 0, -2, -3, 3, 4 然后从头部开始，找到第一个大于 1 的数 2，将其覆盖到右端（此时右端为原 -3 所在处）： -3, -1, 2, 5, -4, 0, -2, 2, 3, 4 然后从右端继续，找到 -2，进行覆盖： -3, -1, -2, 5, -4, 0, -2, 2, 3, 4 （左端的 2 变为 -2） 接着找左端的 5，覆盖到右端： -3, -1, -2, 5, -4, 0, 5, 2, 3, 4 （右端的 -2 变为 5） 找右端的 0，覆盖到左端： -3, -1, -2, 0, -4, 0, 5, 2, 3, 4 （左端的 5 变为 0） 然后发现左端已经没有数大于基准点 1 了，此时比较就完成了，最后把基准点的值赋到最后应该修改的位置，即 右端的 0 位置应该变为 基准点 1： -3, -1, -2, 0, -4, 1, 5, 2, 3, 4
这样，一次快速排序的划分就结束了，可以发现，上面过程其实是左右交叉进行，其中，左边的 x 变为 y 的话，下一次必定是右边的 y 变为 z，然后又是 左边的 z 变为 a…最终数组变为 -3, -1, -2, 0, -4, 1, 5, 2, 3, 4，其中，基准点 1 左边的数都比 1 小，右边的数都比 1 大，接下来将数组分为 1 左侧和 1 右侧分别重复进行上述操作即可完成整个数组的排序
根据以上描述可以写出升序排列的算法：
/** * 交换数组中的两个元素 * 由于选择基准点时要常常用到交换两个数， * 因此另外封装一个函数 * @param nums 要交换的数组 * @param index1 要交换的第一个元素下标 * @param index2 要交换的第二个元素下标 */ void swap(int nums[], int index1, int index2) { int tmp = nums[index1]; nums[index1] = nums[index2]; nums[index2] = tmp; } /** * 选择一个基准点，把大于基准点的数放一边，小于它的放另一边 * 优化基准点的选择，比较左端、中间以及右端的值， * 将第二小的放在左端并将作为基准点，最小的放在中间，最大的放在右端， * 这样，当一轮比较结束之后，原来左端的值会跑到偏中间的位置 * @param nums 要排序的数组 * @param left 要选择基准点那一部分数组的左端点下标 * @param right 要选择基准点那一部分数组的右端点下标 */ void middle(int nums[], int left, int right) { int m = (left+right) / 2; /** * 前两个交换可以将右端点的元素变为三个中最大， * 第三次交换可以将左端点的值变为第二大，即 * 将 m 处的元素值变为最小 */ if(nums[left] > nums[right]) swap(nums, left, right); if(nums[m] > nums[right]) swap(nums, m, right); if(nums[left] < nums[m]) swap(nums, left, m); } /** * 快速排序主体，把大于基准点的数放一边，小于它的放另一边 * 采用递归分治，一部分一部分解决问题 * @param nums 待排序数组 * @param l 待排序的左端点下标 * @param r 待排序的右端点下标 */ void quickUpSort(int nums[], int l, int r) { /** * 递归出口，当区间左右端相等，即 说明此区间只有一个数 * 直接返回 */ if(l >= r) return; int left = l, right = r; /** * 优化基准点的数据 */ middle(nums, left, right); /** * 直接将优化好的数组区间头部作为基准点 */ int key = nums[left]; /** * 循环将左右端的值移到相应的位置，直到 * 左端点下标大于等于右端点下标，说明 * 整个区间已经满足要求，退出循环 */ while(left < right) { /** * 定位右端第一个小于基准点的数，找到后直接将 * 这个不满足要求的数覆盖到左边，使其满足要求 */ while(left<right && nums[right]>=key) --right; nums[left] = nums[right]; /** * 定位左端第一个大于基准点的数，找到后直接将 * 这个不满足要求的数覆盖到右边，使其满足要求 */ while(left<right && nums[left]<=key) ++left; nums[right] = nums[left]; } /** * 最后将基准点放回到数组 */ nums[left] = key; /** * 开始递归，此时 left(或 right)所对应的值就是上一次的 * 基准点的值，因此就以此为界分成两段，分别调用自身 */ quickUpSort(nums, l, left-1); quickUpSort(nums, left+1, r); }降序算法就是将大于基准点的数放到基准点右侧，小于的放到左侧
