搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 程序技术分享 > 快速排序(2)单边循环

快速排序(2)单边循环

程序技术分享 2019-11-08


快速排序-单边循环



01

引入单边循环

      上次已经介绍了快速排序的双边循环,今天简单的叙述一下,单边循环。

        无论是双边循环,还是单边循环,解决思路是一样的,都是选取基准数,让大于基准数的在一边,小于基准数的在另一边。重复递归执行,最终达到有序性。


02

如何做单边循环

        

        选定一个基准数(一般方便选取最开始或者结束的位置),定义两个变量,left ,current。current定义当前位置的指针,left标记小于的区域边界,

        做法是遍历数据,做到当前位置数据大于基准数据时位置不变,current+1;当前位置小于基准数据时候,当前位置和left指针的下一个位置交换数据,left和current指针分别向右移动一位。


        第一步:left和current。都指向第一个位置。选取的基准数也为第一个位置的数3.


快速排序(2)单边循环

        第二步:基准数与current比较,3=3;不交换位置。current向右移动到5位置,left不变。

快速排序(2)单边循环

        第三步:current=5>基准数,不交换位置,current向右移动一位,到1的位置。1<基准数,和left+1位置数 5交换数据,left指针向右移动,包裹住1,扩大小于基准数的区域,current指针向后移动。

快速排序(2)单边循环

        第四步: current=2 <3,当前位置与left指针下一个数据交换,2与5交换位置,并且left指针和current指针向后移动

快速排序(2)单边循环

    第五步:current为3=3,位置不变,left不变,current向后移动。

快速排序(2)单边循环

    第六步同上

快速排序(2)单边循环

    第七步同上

快速排序(2)单边循环

循环结束,交换left指针位置的数和基准数交换。此时left左边的数都是小于基准数的,left右边的数是大于等于基准数的,一次循环确定了基准数的位置不在变化,下面在分别对两个区域的数进行递归调用,确定每个区域每个数的位置,此时数据就是有序的。快速排序(2)单边循环



03

代码实现

public class QuickSortSing { public static void main(String[] args) { int[] arr_sort = new int[]{3,5,1,2,3,9,4};
if(arr_sort.length<2 || arr_sort==null){ return ; } sort(arr_sort,0, arr_sort.length-1); for (int val : arr_sort) { System.out.println(val); } }
public static void sort(int[] arr ,int l,int r){ if(l<r){             int p = patision(arr,l,r); //获取小于的值边界 sort(arr,l,p-1); sort(arr,p+1,r); } } /** * @param arr 待排序数组 * @param start 开始坐标 * @param end 结束坐标 * @return 小于的边界 */ public static int patision(int[] arr,int start, int end){ //选取范围内的第一个作为基准数 int provit = arr[start]; int left = start; //小于区域的边界 for (int i=start;i<=end;i++){ if(arr[i]<provit){ //交换位置 swap(arr,i,++left); }
} //最后交换第一个数和最小值的边界位置 swap(arr,start,left); return left; }
public static void swap(int[] arr, int index, int i) { int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; }}




  


快速排序(2)单边循环
END
快速排序(2)单边循环





快速排序(2)单边循环
长按扫码关注








版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《快速排序(2)单边循环》的版权归原作者「程序技术分享」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注程序技术分享微信公众号

程序技术分享微信公众号:nannanwangno1

程序技术分享

手机扫描上方二维码即可关注程序技术分享微信公众号

程序技术分享最新文章

精品公众号随机推荐