快速排序
2021-06-10 03:04
标签：cto alt org 数组 imp ack i++ public etl 快速排序 标签：cto alt org 数组 imp ack i++ public etl 原文地址：https://www.cnblogs.com/LeeBoom/p/kuai-su-pai-xu.html
从数列中挑出一个元素，称为 "基准"（pivot）;
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；
package com.example.leetcode.easy;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.Arrays;
/**
* 快速排序,分而治之
* @author LiPeng01
* @since 2021/3/1 4:10 下午
*/
public class Fast {
public static void main(String[] args) {
int[] num ={9,8,7,6,5,4,3,2,1};
quick(num,0,num.length-1);
Logger logger = LoggerFactory.getLogger(Merge.class);
logger.info(Arrays.toString(num));
}
/**
* 快排
* @param nums
* @param l
* @param r
*/
public static void quick(int[] nums,int l, int r){
if(l = pivot) {
j--;
}
//如果比基准数小,则该数填入到i的坑中,此时j的位置空出一个坑来(实际值还在),j不变记录坑位
if(i pivot) {
nums[j] = nums[i];
j--;
}
}
//直至i,j相遇,此时比基准数大的放在基准数右边,小的放在左边
//由于i或j停在此处一定是因为上一轮发生了填坑,即此处的已经被挖坑,所以将基准数填入即可
nums[i] = pivot;
return i;
}
}