网站运营与数据分析,备案 网站名称怎么写,html5网站建设平台,涉密网络运行维护服务外包的单位简介
快速排序是对冒泡排序的一种改进#xff0c;是一种分治算法#xff0c;时间复杂度为O(nlogn)
基本思想
先从数列中取出一个数作为基准数。分区过程#xff0c;将比这个数大的数全放到它的右边#xff0c;小于或等于它的数全放到它的左边。再对左右区间重复第二步是一种分治算法时间复杂度为O(nlogn)
基本思想
先从数列中取出一个数作为基准数。分区过程将比这个数大的数全放到它的右边小于或等于它的数全放到它的左边。再对左右区间重复第二步直到各区间只有一个数。
Java实现代码
import java.util.Arrays;public class Main {public static void main(String[] args){//测试数据int[] nums new int[10];for(int i0;i10;i)nums[i] (int)(Math.random()*100);System.out.println(原数组);Arrays.stream(nums).forEach(num-{System.out.print(num );});quickSort(nums, 0, nums.length-1);System.out.println(\n排序结果);Arrays.stream(nums).forEach(num-{System.out.print(num );});}public static void quickSort(int[] nums, int low, int high){if(lowhigh){//以第一个数为基准数将大于基准数的数放于基准数右侧小于的则放于左侧int middle Qsort(nums, low, high);//对排序后的左部分排序quickSort(nums, low, middle-1);//对排序后的右部分排序quickSort(nums, middle1, high);}}public static int Qsort(int[] nums, int low, int high){/*** 单次排序* 步骤* 1.从右往左找出第一个比基准数小的数* 2.从左往右找出第一个比基准数大的数* 3.重复以上直到lowhigh*/int middle nums[low];while(lowhigh){//从右往左找出第一个比基准数小的数while(lowhighnums[high]middle)high--;nums[low] nums[high];//从左往右找出第一个比基准数大的数while(lowhighnums[low]middle)low;nums[high]nums[low];}nums[low] middle;//返回基准数的索引return low;}
}
参考
快速排序 —— 菜鸟教程
