概念
快速排序的基本思想是分治法，选取一个“基准数”作为比较参照，经过排序运算，将数据分为两个规模更小的数据源，其中一个所有的数据都比另一部分的小，然后递归进行操作从而使数据达到有序的状态。
分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。
快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*logN)。快速排序是不稳定的算法。
算法稳定性：假设在数列中存在 a[i] = a[j]，若在排序之前，a[i] 在a[j] 前面；并且排序之后，a[i] 仍然在a[j] 前面。则这个排序算法是稳定的！
实现方式
记录一下三种简单的实现方式，总结以代码+日志的方式展示，通过日志可以清晰的展示出每轮每次的数据操作。前提假设最终的目标排序方式都是升序，可以为了清晰展示出每次具体操作了哪些数据，日志[]中括号内展示的为数组下标，()小括号内展示的为本轮的数据源，""双引号内展示的为本次需要交换的两个值，''单引号内展示的为pre(前后指针)的值。
左右指针法
- 选取基准值，开始本轮循环；
- 从数组右侧开始递减比较，发现有值小于基准值，停下记录该下标；
- 从数组左侧开始递增比较，发现有值大于基准值，停下记录该下标；
- 将两个下标的值进行交换；
- 接着循环重复第2~4步，直到左右两指针相遇，表示这一轮的内循环比较结束；
- 此时左、右指针指向相同的值，将左、右指针指向的值与基准值交换（基准值归位），就完成了本轮的排序；
- 每轮排序完成后，基准值左边的都是小于它的，而右边都是大于等于它的，接着以基准值为分割点，将两个子集数据源从第1步进行递归操作；
通俗点说，就是一个指针从右侧依次递减，一个指针从左侧依次递增，当发现符合条件的情况时，交换两个指针指向的值，然后以基准值为分割点，将本次数据源分为两个小的数组，依次递归循环该操作。
这里需要注意的就是内部循环初始先从右侧开始还是左侧开始，这里先分析下本例当中，要求升序排列，从左侧（最终肯定是小于基准值的值）取默认基准值，当内部循环优先从右侧开始时，每次循环完，右侧指针指向的永远是小于基准值的值（排除已经是升序的情况），这时假如本次没有交换，在循环外右侧指针（等于左侧指针）就可以与基准值的进行交换，最终基准值归位，小于基准值的数都在一侧。
相应的，我们也可以在内循环时优先从左侧判断，这时在选基准值时就选择右侧的；或者尝试下降序时的初始方式，这里就不赘述了……
public static void quickSort(int left, int right) {
if (left >= right) {
return;
}
int l = left;
int r = right;
int target = arrs[l];
while (l < r) {
while (arrs[r] >= target && l < r) {
r--;
}
while (arrs[l] <= target && l < r) {
l++;
}
if (l < r) {
swap(arrs[l], arrs[r]);
}
}
if (l != left) {
swap(arrs[l], arrs[left]):
}
quickSort(left, l - 1);
quickSort(l + 1, right);
}
随机初始数组： [29, 13, 86, 2, 55, 7, 22, 33, ]
################
第1轮，基准值是29：
交换[2]和[6]位置的值
交换前的数据： [(29, 13, "86", 2, 55, 7, "22", 33), ]
交换后的数据： [(29, 13, "22", 2, 55, 7, "86", 33), ]
交换[4]和[5]位置的值
交换前的数据： [(29, 13, 22, 2, "55", "7", 86, 33), ]
交换后的数据： [(29, 13, 22, 2, "7", "55", 86, 33), ]
内循环结束，当前l=r=[4]，与基准值(下标[0])值交换
交换前的数据： [("29", 13, 22, 2, "7", 55, 86, 33), ]
交换后的数据： [("7", 13, 22, 2, "29", 55, 86, 33), ]
第1轮结束
第2轮，基准值是7：
交换[1]和[3]位置的值
交换前的数据： [(7, "13", 22, "2"), 29, 55, 86, 33, ]
交换后的数据： [(7, "2", 22, "13"), 29, 55, 86, 33, ]
内循环结束，当前l=r=[1]，与基准值(下标[0])值交换
交换前的数据： [("7", "2", 22, 13), 29, 55, 86, 33, ]
交换后的数据： [("2", "7", 22, 13), 29, 55, 86, 33, ]
第2轮结束
第3轮，基准值是22：
循环结束，当前l=r=[3]，与基准值(下标[2])值交换
交换前的数据： [2, 7, ("22", "13"), 29, 55, 86, 33, ]
交换后的数据： [2, 7, ("13", "22"), 29, 55, 86, 33, ]
第3轮结束
第4轮，基准值是55：
交换[6]和[7]位置的值
交换前的数据： [2, 7, 13, 22, 29, (55, "86", "33"), ]
交换后的数据： [2, 7, 13, 22, 29, (55, "33", "86"), ]
内循环结束，当前l=r=[6]，与基准值(下标[5])值交换
交换前的数据： [2, 7, 13, 22, 29, ("55", "33", 86), ]
交换后的数据： [2, 7, 13, 22, 29, ("33", "55", 86), ]
第4轮结束
################
排序最终数组： [2, 7, 13, 22, 29, 33, 55, 86, ]
填坑法
- 选取基准值，该下标即为第一个坑位A，开始本轮循环；
- 从数组右侧开始递减比较，当发现有值小于基准值时，将当前值填到坑位A中，同时当前下标替换为坑位B（注意：初始基准值被覆盖掉了，本轮操作最后，需要将该值填到坑位中）；
- 从数组左侧开始递增比较，当发现有值大于基准值，将值填到坑位B中，同时当前下标替换为坑位A；
- 不停的重复第2~3步的操作，直到左右两指针相遇，表示这一轮的内循环比较结束；
- 将基准值填到左右指针指向的坑位中，就完成了本轮的排序；
- 以基准值为分割点，将本次数据源分为两个小的数组，依次从第1步递归循环操作；
public static void quickSort(int left, int right) {
if (left >= right) {
return;
}
int l = left;
int r = right;
int target = arrs[l];
while (l < r) {
while (arrs[r] >= target && l < r) {
r--;
}
if (l < r) {
arrs[l] = arrs[r];
}
while (arrs[l] <= target && l < r) {
l++;
}
if (l < r) {
arrs[r] = arrs[l];
}
}
arrs[l] = target;
quickSort(left, l - 1);
quickSort(l + 1, right);
}
随机初始数组： [14, 18, 1, 28, 30, 11, 78, 55, ]
################
第1轮，基准值是14，当前坑位[0]：
交换前的数据： [("14", 18, 1, 28, 30, "11", 78, 55), ]
交换后的数据： [("11", 18, 1, 28, 30, "11", 78, 55), ] 当前坑位[5]，值是11
交换前的数据： [(11, "18", 1, 28, 30, "11", 78, 55), ]
交换后的数据： [(11, "18", 1, 28, 30, "18", 78, 55), ] 当前坑位[1]，值是18
交换前的数据： [(11, "18", "1", 28, 30, 18, 78, 55), ]
交换后的数据： [(11, "1", "1", 28, 30, 18, 78, 55), ] 当前坑位[2]，值是1
内循环结束，准备将基准值补上最后一个坑位 [(11, 1, "1", 28, 30, 18, 78, 55), ]
交换后的数据： [(11, 1, "14", 28, 30, 18, 78, 55), ]
第1轮结束
第2轮，基准值是11，当前坑位[0]：
交换前的数据： [("11", "1"), 14, 28, 30, 18, 78, 55, ]
交换后的数据： [("1", "1"), 14, 28, 30, 18, 78, 55, ] 当前坑位[1]，值是1
内循环结束，准备将基准值补上最后一个坑位 [(1, "1"), 14, 28, 30, 18, 78, 55, ]
交换后的数据： [(1, "11"), 14, 28, 30, 18, 78, 55, ]
第2轮结束
第3轮，基准值是28，当前坑位[3]：
交换前的数据： [1, 11, 14, ("28", 30, "18", 78, 55), ]
交换后的数据： [1, 11, 14, ("18", 30, "18", 78, 55), ] 当前坑位[5]，值是18
交换前的数据： [1, 11, 14, (18, "30", "18", 78, 55), ]
交换后的数据： [1, 11, 14, (18, "30", "30", 78, 55), ] 当前坑位[4]，值是30
内循环结束，准备将基准值补上最后一个坑位 [1, 11, 14, (18, "30", 30, 78, 55), ]
交换后的数据： [1, 11, 14, (18, "28", 30, 78, 55), ]
第3轮结束
第4轮，基准值是30，当前坑位[5]：
内循环结束，准备将基准值补上最后一个坑位 [1, 11, 14, 18, 28, ("30", 78, 55), ]
交换后的数据： [1, 11, 14, 18, 28, ("30", 78, 55), ]
第4轮结束
第5轮，基准值是78，当前坑位[6]：
交换前的数据： [1, 11, 14, 18, 28, 30, ("78", "55"), ]
交换后的数据： [1, 11, 14, 18, 28, 30, ("55", "55"), ] 当前坑位[7]，值是55
内循环结束，准备将基准值补上最后一个坑位 [1, 11, 14, 18, 28, 30, (55, "55"), ]
交换后的数据： [1, 11, 14, 18, 28, 30, (55, "78"), ]
第5轮结束
################
排序最终数组： [1, 11, 14, 18, 28, 30, 55, 78, ]
前后指针法
- 选取基准值，定义两个指针，cur 表示当前指针指向，pre 默认表示cur 指针的前一位；
- cur 和 pre 指针依次++ 进行递增比较，当cur 发现大于基准值时，pre 暂停递增（即[pre+1] 指向了一个大于基准值的值）；
- cur 接着++ 进行递增比较，当发现比基准值小时，对数组[pre+1] 和 数组[cur] 的值进行交换；
- 不停的重复第2~3步操作，直到一轮循环结束（即cur 从当前数据源从左移到了右）；
- 内循环结束后，将数组[pre+1] 的值与基准值进行交换；
- 以基准值为分割点，将本次数据源分为两个小的数组，依次从第1步递归循环操作；
public static void quickSort(int left, int right) {
if (left >= right) {
return;
}
int cur = left;
int pre = cur - 1;
int target = arrs[right];
while (cur < right) {
while (arrs[cur] < target && ++pre != cur) {
swap(arrs[cur], arrs[pre];
}
cur++;
}
swap(arrs[++pre], arrs[right]);
quickSort(left, pre -1);
quickSort(pre + 1, right);
}
随机初始数组： [86, 59, 63, 53, 68, 99, 58, 1, ]
################
第1轮，基准值是1，'pre'：[-1]，"cur"：[0]：
"cur"指针++了： [(86, "59", 63, 53, 68, 99, 58, 1), ] ，'pre'：[-1], "cur"：[1]
"cur"指针++了： [(86, 59, "63", 53, 68, 99, 58, 1), ] ，'pre'：[-1], "cur"：[2]
"cur"指针++了： [(86, 59, 63, "53", 68, 99, 58, 1), ] ，'pre'：[-1], "cur"：[3]
"cur"指针++了： [(86, 59, 63, 53, "68", 99, 58, 1), ] ，'pre'：[-1], "cur"：[4]
"cur"指针++了： [(86, 59, 63, 53, 68, "99", 58, 1), ] ，'pre'：[-1], "cur"：[5]
"cur"指针++了： [(86, 59, 63, 53, 68, 99, "58", 1), ] ，'pre'：[-1], "cur"：[6]
"cur"指针++了： [(86, 59, 63, 53, 68, 99, 58, "1"), ] ，'pre'：[-1], "cur"：[7]
内循环结束，准备将'++pre'(大于基准值的值)与基准值交换： [("86", 59, 63, 53, 68, 99, 58, "1"), ]
交换后的数据： [("1", 59, 63, 53, 68, 99, 58, "86"), ]
第1轮结束
第2轮，基准值是86，'pre'：[0]，"cur"：[1]：
"cur"指针++了： [1, ('59', "63", 53, 68, 99, 58, 86), ] ，'pre'：[1], "cur"：[2]
"cur"指针++了： [1, (59, '63', "53", 68, 99, 58, 86), ] ，'pre'：[2], "cur"：[3]
"cur"指针++了： [1, (59, 63, '53', "68", 99, 58, 86), ] ，'pre'：[3], "cur"：[4]
"cur"指针++了： [1, (59, 63, 53, '68', "99", 58, 86), ] ，'pre'：[4], "cur"：[5]
"cur"指针++了： [1, (59, 63, 53, '68', 99, "58", 86), ] ，'pre'：[4], "cur"：[6]
交换前的数据： [1, (59, 63, 53, 68, "99", "58", 86), ]
交换后的数据： [1, (59, 63, 53, 68, "58", "99", 86), ]
"cur"指针++了： [1, (59, 63, 53, 68, '58', 99, "86"), ] ，'pre'：[5], "cur"：[7]
内循环结束，准备将'++pre'(大于基准值的值)与基准值交换： [1, (59, 63, 53, 68, 58, "99", "86"), ]
交换后的数据： [1, (59, 63, 53, 68, 58, "86", "99"), ]
第2轮结束
第3轮，基准值是58，'pre'：[0]，"cur"：[1]：
"cur"指针++了： ['1', (59, "63", 53, 68, 58), 86, 99, ] ，'pre'：[0], "cur"：[2]
"cur"指针++了： ['1', (59, 63, "53", 68, 58), 86, 99, ] ，'pre'：[0], "cur"：[3]
交换前的数据： [1, ("59", 63, "53", 68, 58), 86, 99, ]
交换后的数据： [1, ("53", 63, "59", 68, 58), 86, 99, ]
"cur"指针++了： [1, ('53', 63, 59, "68", 58), 86, 99, ] ，'pre'：[1], "cur"：[4]
"cur"指针++了： [1, ('53', 63, 59, 68, "58"), 86, 99, ] ，'pre'：[1], "cur"：[5]
内循环结束，准备将'++pre'(大于基准值的值)与基准值交换： [1, (53, "63", 59, 68, "58"), 86, 99, ]
交换后的数据： [1, (53, "58", 59, 68, "63"), 86, 99, ]
第3轮结束
第4轮，基准值是63，'pre'：[2]，"cur"：[3]：
"cur"指针++了： [1, 53, 58, ('59', "68", 63), 86, 99, ] ，'pre'：[3], "cur"：[4]
"cur"指针++了： [1, 53, 58, ('59', 68, "63"), 86, 99, ] ，'pre'：[3], "cur"：[5]
内循环结束，准备将'++pre'(大于基准值的值)与基准值交换： [1, 53, 58, (59, "68", "63"), 86, 99, ]
交换后的数据： [1, 53, 58, (59, "63", "68"), 86, 99, ]
第4轮结束
################
排序最终数组： [1, 53, 58, 59, 63, 68, 86, 99, ]
网友评论