划分

布满荆棘的人生 2022-09-26 01:59 175阅读 0赞

### 接触快速排序之前首先需要了解划分。划分就是将数据划分为两组，比关键字大的划分在一组，比关键字小的划分在另外一组。 ###

### 划分算法可以理解是两个指针操作的进程。开始时指针分别指向数组头部和尾部（以数组为例，通常数组是没有头部和尾部所谓的，这里是简单描述这个问题），操作的过程是以下几个流程： ###

### 1 初始化leftPtr(向右检索的指针)在数组最左端，rightPtr指针在数组最右端。 ###

### 2 leftPtr向右移动，若数据项比关键字小，则继续移动。在移动的同时需要注意边界条件：leftPtr< right(数组最右端)，若数据项比关键字大，此时进入到step4。 ###

### 3 rightPtr向左移动，数据项比关键字大则继续移动，不做任何交换。移动的同时同样需要检测边界条件。若数据项比关键字小，则直接进入step4。 ###

### 4 交换step2 与step3 的leftPtr与rightPtr对应的数据项。 ###

### 5 可以返回交换的数据位置，并检测整个循环，若leftPtr>=rightPtr则查找结束，break跳出循环。 ###

### 用图表示以上过程为： ###

![这里写图片描述][20160915160720400]

### 上图表示初始化。 ###

![这里写图片描述][20160915160817816]

### 以上是step2 3 4 两端指针移动和数据交换过程 ###

![这里写图片描述][20160915160931120]

### 以上表示判断循环退出条件，当leftPtr与rightPtr指针相遇时，break退出while循环的过程。 ###

### 以下是划分算法的代码： ###

//对一个数组进行划分
    //小于这个数据的项放在左边，大于这个数的项放在右边
    //返回当前数据项的下标
    class Divide
    {
        private int[] array=null;
        //获取数组 随机数产生数组
        public Divide(int n)
        {
            array=new int[n];
            for(int i=0;i<n;i++)
            {
                int a=(int)(Math.random()*100);
                array[i]=a;
            }
            showArray();
        }
        //划分算法
        public int divide(int left,int right,int actionNum)
        {
    
             int leftPtr=left-1;
             int rightPrt=right+1;
             //不断进行划分 当left指针right指针相遇时跳出循环
             while(true)
             {
                 //循环从左向右进行查找
                 //注意边界监测
                 while(leftPtr<right&&array[++leftPtr]<actionNum)
                 {
                     ;//查找的数据项都比actionNum都要小 可以什么都不做
                 }
                 while(rightPrt>left&&array[--rightPrt]>actionNum)
                 {
                     ;//查找的数据项都actionNum多都要大 可以什么都不做
                 }
                 //判读退出循环条件
                if(leftPtr>=rightPrt)
                {
                    break;
    
                }
                 //当以上有两种情况发生时 进行交换数据项
                else
                {
                    swap(leftPtr,rightPrt);
                }   
             }
             return leftPtr;
        }
        public void swap(int left,int right)
        {
            int temp=0;
            temp=array[left];
            array[left]=array[right];
            array[right]=temp;
        }
        public void showArray()
        {
            for(int i=0;i<array.length;i++)
            {
                System.out.print(array[i]+" ");
            }
            System.out.println("");
        }
    }

### 测试与结果： ###

Divide a=new Divide(18);
            System.out.println(a.divide(0, 17, 20));
            a.showArray();

52 89 24 29 31 23 90 80 86 59 2 16 21 74 84 19 35 84 
    3
    19 16 2 29 31 23 90 80 86 59 24 89 21 74 84 52 35 84

### 由于是随机数产生的数组，故每次结果都是不一样的。以上测试将数字20作为关键字，数组中前三个数都是小于20，后面15个数组均大于20。 ###

### 关于划分的效率 ###

### 划分算法运行时间是O（N），运行时间与N成正比。一般来说比较的次数是对于交换的次数。最好情况是数组有序，这样交换的次数会比较少，计算更快。 ###

[20160915160720400]: /images/20220717/7af8476724d3489e85718ecb618cdb5a.png
[20160915160817816]: /images/20220717/ef54384836874d9b893b7fd740f20c53.png
[20160915160931120]: /images/20220717/1f1ca7c03e2f457eb2aef663a41783db.png