排序算法 --- 快速排序
一、排序思想
- 将数组中的一个数作为基准，比该数小的放到左边，比该数大的放到右边；
- 对左右两边再进行上述操作，即把左边当成一个新数组，找新的基准数，右边也一样；
- 直到不能再分割下去为止。
欢迎大家关注我的公众号 javawebkf，目前正在慢慢地将简书文章搬到公众号，以后简书和公众号文章将同步更新，且简书上的付费文章在公众号上将免费。
案例：
假如待排序列如下：
初始状态
- 选定
6为基准数，然后先从右边开始遍历，找到一个比基准数小的数，如下图：
找到比基准数小的5
- 右边找到比基准数小的时候，右边先停下，再从左边开始遍历，找到比基准数大的，如下图：
找到比基准数大的7
- 这个时候，左右两边都先停下，交换
5和7的位置，结果如下：
第一次交换完成
- 然后继续从右边开始遍历，即从
7的位置开始，找到比基准数小的数，如下：
找到比基准数小的4
- 找到后停下，再从左往右找比基准数大的，即从
5开始找，结果如下：
找到比基准数大的9
- 这个时候，左右两边都停下，交换
9和4的位置，结果如下：
第二次交换完成
- 再从右边开始找比基准数小的，找到了
3，然后从左边找比基准数大的，左边指针移动到3的时候，左右指针重合了，如下：
指针重合
- 指针重合了，就将基准数和指针重合时所指的数交换位置，即交换
6和3的位置，如图：
第一躺排序完成
- 此时
6左边的都是比它小的，右边的都是比它大的。左边部分和右边部分看成是两个新的待排序列，两个序列都按照上述方式再进行排序，先排左边，再排右边。
二、代码实现
结合上面的案例，以及代码中的注释，可以说是思路十分清晰了，完整代码如下：
public static void sort(int[] arr, int left, int right) {
if (arr == null || arr.length == 1) {
return;
}
if (left > right) {
return;
}
int base = arr[left]; // 最左边的数当作基准数
int i = left; // 从左往右遍历的指针
int j = right; // 从右往左遍历的指针
int temp = 0; // 用来保存临时变量
// 当左右指针不相遇的时候，就进行检索
while(i != j) {
// 先从右往左检索，直到检索到比基准数小的
while (arr[j] >= base && i < j) {
j--;
}
// 再从左往右检索，直到检索到比基准数大的
while (arr[i] <= base && i < j) {
i++;
}
// 跳出了上面两个while循环，表示右边找到了基准数小的，左边找到了比基准数大的，交换位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 跳出了最外层while循环，表示i和j相等，左右指针相遇了，交换基准数和此时指针指的元素
arr[left] = arr[i];
arr[i] = base;
// 此时，第一躺排序完成，左边和右边看成新数组，重复上述步骤
sort(arr, j+1, right); // 排右边
sort(arr, left, i-1); // 排左边
}快速排序之所以成为快速排序，那就是因为它快，经测试，排1千万数据大概是1秒的样子，还真是有两把刷子。
举报
腾讯云开发者
