大家好,又见面了,我是你们的朋友全栈君。
思路
对于给定的数组,从中选一个元素为比较对象,一般选最左或最右的元素,选左边为升序排,选右边反之。
数组array[]:
最左边:target = 5
数组下标:i = 0, j = 9
步骤:
①从右边遍历数组,把array[ j ]比5小的放在5的左边, j–;
交换位置后i = 0,j = 7:
②从左边遍历数组,把array[ i ]比5大的放在5的右边, i++;
交换位置后i = 5,j = 7:
③回到①②步骤循环执行:
循环执行后,比5小的都放在了5的左边,比5大的都放在了5的右边;
④此时5左边和右边部分还是乱序的,这就需要做递归操作,把0 2 3 1 4和 7 8 6 9 部分继续执行述排序步骤。
递归执行后:
代码示例:
public class _06FastSortExample {
/** * 左右两个哨兵 * * @param left * @param right 每次都是这个先 */
public void quicksort(int[] a, int left, int right) {
int i, j, t, temp;//哨兵i,哨兵j,交换ij用到t,基准数temp
if (left > right) {
//跳出
return;
}
//传过来的参数进行赋值
temp = a[left];//temp中存储的就是基准数
i = left;//左边哨兵
j = right;//右边哨兵
while (i != j) {
//顺序很重要,先从右边开始找
while (a[j] >= temp && i < j) {
j--;//记录哨兵j位置
}
//再从左边找:小于基准数的数
while (a[i] <= temp && i < j) {
i++;//记录哨兵i位置
}
//交换两个数在数组中的位置
if (i < j) {
t = a[i];
a[i] = a[j];
a[j] = t;
}
}
//最终将基准数归位 : 就是基准数跟ij相遇位置的数进行交换
a[left] = a[i];//a[i]给left的位置也就是0,就是基准数
a[i] = temp;//基准数该a[i]
quicksort(a, left, i - 1);//继续处理左边的,这里是一个递归的过程
quicksort(a, i + 1, right);//继续处理右边的 ,这里是一个递归的过程
}
public static void main(String[] args) {
int a[] = {
5,2,3,1,6,4,7,8,0,9};//数组//定义变量,这两个变量需要在子函数中使用
_06FastSortExample f = new _06FastSortExample();
f.quicksort(a, 0, a.length - 1);
for (int aa : a) {
System.out.println(aa);
}
}
}
其他算法:
Java二分查找法
Java冒泡排序
Java选择排序
Java插入排序
Java希尔排序
Java计数排序
Java快排算法
Java归并排序
Java堆排序
动图演示
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/128217.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...