快速排序，用c++语法中用得最多的排序算法。一般情况下，它的算法时间为NlogN，相比插入排序，希尔排序来说，它在处理大数据量上具有相当的优势。
快速排序使用了递归的思想，即将其中的一部分再交由算法本身进行处理。它的基本原理如下：
- 当数组长度只有1时，即结束排序
- 当数组长度大于1时，随机的取一个数（记为中数）对数组进行分割，即将整个数组分为三个部分，一是所有小于等于中数的数据，二是中数本身，三为所有大于等于中数的数据。在三部分数据中，允许数据长度为0,即有可能所有的数据都比中数小或大。
所以，快速排序的基本实现步骤，即首先判断结束条件，在满足条件1时，直接结束；接下来，取中数，即取一个适合当作中间数的元素；再接着就是分割数组了，将所有小于中数的数据，放到数组左边，将所有大于中数的数据放到数组右边；最后再对所有左边的数据进行递归排序，对所有右边的数据进行递归排序。
因此，算法的重点在于如何进行数组分割，即要满足一个数据比较关系，即数组[left]<=中数<数组[right]。同时，又要保证不要进行无谓的替换，即在处理过程中中不对所有左边（或右边）的数据进行交换。因此，采取一个算法，即是只需要将左边>=中数的数据和右边<=中数的数据进行交换即可，当左边或者右边已没有数据可交换时，即结束分割。
具体的做法，即是采取从两边向中间靠的方式，即使用left和right变量分别从两边向中间靠，当left碰到比中数大的数时停止，right碰到比中数小的数时停止，然后交换left和right的数据，然后再继续，走到left>right，即表示整个数组实际上已经完成了遍历，而且left变量左边的数据均比中数小，而右边的数则均比中数大，当然left所处的位置也比中数大。最后将left与路数交换，left所在的位置，即是中数所在的位置。接下来，重复对start-left排序，left+1至end排序，即完成递归排序。
详细的代码如下所示：
/** 演示快速排序 */
public static void kuaisuSort(int[] ints) {
kuaisuSort(ints, 0, ints.length - 1);
}
private static void kuaisuSort(int[] ints, int start, int end) {
if(start >= end)//长度至少大于1
return;
//寻找到一个中间数
int middle = xunzhaoMiddle(ints, start, end);
int middleValue = ints[middle];
//将中间数弄到最后去
swap(ints, middle, end);
int left = start, right = end - 1;
while(true) {
while(ints[left] < middleValue)//标注1
left++;
while(right > start && ints[right] > middleValue)
right--;
if(left < right) {
swap(ints, left++, right--);
} else
break;
}
//再将最后一个数换回来
swap(ints, left, end);
//排左边
kuaisuSort(ints, start, left - 1);
//排右边
kuaisuSort(ints, left + 1, end);
}
/** 寻找中间数算法，即取start，end和中间一个坐标的数，返回大小在中间的那个数的坐标 */
private static int xunzhaoMiddle(int[] ints, int start, int end) {
int middle = (start + end) / 2;
if(ints[start] > ints[middle]) {
if(ints[start] > ints[end])
return ints[middle] > ints[end] ? middle : end;
return start;
} else {
if(ints[start] > ints[end])
return start;
else
return ints[middle] > ints[end] ? end : middle;
}
}
整个算法本身不复杂，重点是要理解其中的正确性。如上面代码中的标注1,这里i++并没有做越界的判断。这是因为，我们只是将其对中数进行比较，并且中数的位置在end位置处，对于i++,至少不能越界，因为当i=end时，判断就结束。
转载请标明出处:i flym
本文地址:https://www.iflym.com/index.php/code/understand-quick-sort-most-used-sort.html