成都高端响应式网站开发,怎么创建自己的购物平台,杭州网站模板,招生网站模板快速排序是在工具类常用的排序算法#xff0c;快速排序的思想主要是选定一个基准元素#xff0c;然后找到基准元素的位置#xff0c;然后再分别排序他左边的和他右边的,快速排序是不稳定的#xff0c;时间复杂度位Nlog(N),最极端的情况就是一个反向排好顺序的数组#xff…快速排序是在工具类常用的排序算法快速排序的思想主要是选定一个基准元素然后找到基准元素的位置然后再分别排序他左边的和他右边的,快速排序是不稳定的时间复杂度位Nlog(N),最极端的情况就是一个反向排好顺序的数组然后每次二分都分不开导致的时间复杂度最高
Testpublic void testSort(){int nums[] new int[]{1,4,8,2,3,4,7,8,0};// 快速排序quickSort(nums,0,nums.length-1);Arrays.stream(nums).forEach(System.out::println);}private void quickSort(int[] arr, int lo, int hi) {if(lohi) return ;int partitionpartition(arr,lo,hi);quickSort(arr,lo,partition-1);quickSort(arr,partition1,hi);}private int partition(int[] arr, int lo, int hi) {//把最左边的元素当作基准值int keyarr[lo];int leftlo;int righthi1;while(true) {//左指针遇到key的值才停下while(arr[left] key) {if(lefthi) break;}//右指针遇到key的值才停下while(key arr[--right]) {if(rightlo) break;}if(leftright) {//扫描了所有元素结束循环break;}else {//交换左右指针swap(arr,left,right);}}//right指向的值一定是小于或等于key值所以交换key和右指针的值swap(arr,lo,right);return right;}private static void swap(int[] arr, int i, int j) {int temparr[i];arr[i]arr[j];arr[j]temp;}
总结
快速排序就是主要在找一个数据的位置partition就是在对一个数字找到对应的位置大于他的放右边小于他的放左边这样得到了一个元素的位置并且将一个数组的排序分为了左右两边的排序然后再对左右两边的进行同样的排序操作递归即可完成对应的排序
