首页 > 代码库 > Java算法快速排序
Java算法快速排序
快速排序的原理:每次将序列以一个值为界限分成两组,在将两个序列分别以一个界限分成两组这样一直分下去。
int[] a = {11,222,44,63,84,11,24,53,123,25,98,76,34};
第一步:以34将数组a分成两组 11, 25, 24, 11 34, 63, 44, 53, 123, 222, 98, 76, 84
第二步:以11将11, 25, 24, 11分为两组 11, 11, 24, 25。以84将34, 63, 44, 53, 123, 222, 98, 76, 84分为两组34, 63, 44, 53, 76, 84 98, 123, 222。
这样一直循环下去直到不能再分。
import java.util.Arrays; public class QuickSort { public static int partition(int[] arrays,int left,int right){ int leftPart = left -1; int rightPart = right; //拿出数组最后一个词作为界限,数组的最后一个本身不参与比较 int median = arrays[right]; while(true){ while(leftPart < rightPart && arrays[++leftPart] <= median); while(leftPart < rightPart && arrays[--rightPart] >= median); if(leftPart >= rightPart){ break; }else{ change(arrays,leftPart,rightPart); } } //将界限的值也就是数组最后一个放到两组的中间 change(arrays,leftPart,right); System.out.println(Arrays.toString(arrays)); return leftPart; } public static void quickSort(int[] arrays,int left,int right){ if(left >= right){ return; }else{ int partition = partition(arrays, left, right); //分别在递归排序两个组,中间的界限不参与。 quickSort(arrays,left,partition-1); quickSort(arrays,partition+1,right); } } public static void change(int[] arrays,int left,int right){ int temp = arrays[left]; arrays[left] = arrays[right]; arrays[right] = temp; } public static void main(String[] args) { int[] a = {11,222,44,63,84,11,24,53,123,25,98,76,34}; quickSort(a, 0,a.length-1); System.out.println(Arrays.toString(a)); } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。