1. 概念
快速排序是一种比较高效的排序算法,采用 “分而治之” 的思想,通过多次比较和交换来实现排序,在一趟排序中把将要排序的数据分成两个独立的部分,对这两部分进行排序使得其中一部分所有数据比另一部分都要小,然后继续递归排序这两部分,最终实现所有数据有序。
2. 思路
① 给出一组待排序序列,我们取该序列的第一个元素为基准值。什么是基准值?就是相当于参考物吧。接着再取两个哨兵,什么是哨兵?暂且当它为指针吧;
② 那么这个序是怎么个排法?首先,我们在序列的最左边和最右边各放一个哨兵,我们分别称它们为 left 和 right,left 从左往右走寻找比基准值大的数,right 从右往左走寻找比基准值小的数;
③ 规定第一步应该让 right 先迈出,我们让它一直往左走,走到什么地步?直到它找到了比基准值小的数为止,就停下来。right 停下来之后,就轮到 left 走了,同样道理,当 left 找到了比基准值大的数时,它也停了下来,left 和 right 都停了,接下来,交换这两个位置的数值,第一轮互相奔赴的旅途结束;
④ 第一轮结束后,还有下一轮,现在它们两个都停在半路上,没有见到彼此,路途遥远继续走。同样的方法,left 继续 ++ 向右走,right- - 向左走,满足条件时等待双方都停下来,交换数值,交换完继续走;
⑤ 以上所有的奔赴过程,我们都通过 while 循环来实现。其中,外层 while 循环控制双方交换完数值之后继续奔赴,退出条件就是 left 和 right 相撞的那一刻。内层两个 while 循环控制它们各自从一个停止点到另一个停止点的行走过程,退出条件是找到下一个停止点的时候。相当于外层循环发号施令,说开始走,于是内层循环听到了指令,就让 left 和 right 各自走到了自己的下一个停止位置,交换数值之后,静等外层循环的指令,才可以再到下一个目标点;
⑥ 当 left == right 时,循环结束,我们把 left 和 right 相遇位置的数值与基准值互换一下,此时,整体上基准值左边的数均小于基准值右边的数,但是左右两边各自的排序是乱的;
⑦ 道理是一样的,此时我们可以从基准处将序列分为两部分,然后用递归的方法排序这两部分,最终实现所有数据有序排列。文章来源:https://www.toymoban.com/news/detail-629827.html
3. 代码实现
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {3, 2, 9, 11, 17, 4, 13, 7, 5, 1, 12};
int[] newArr = quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(newArr));
}
public static int[] quickSort(int[] arr, int low, int high) {
if (low > high) {
return arr;
}
int base = arr[low];
int left = low;
int right = high;
while (left != right) {
while (arr[right] >= base && left < right) {
right--;
}
while (arr[left] <= base && left < right) {
left++;
}
int temp;
temp = arr[right];
arr[right] = arr[left];
arr[left] = temp;
}
arr[low] = arr[left];
arr[left] = base;
quickSort(arr, low, left - 1);
quickSort(arr, right + 1, high);
return arr;
}
}
文章来源地址https://www.toymoban.com/news/detail-629827.html
到了这里,关于快速排序【Java算法】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!