文档章节

Java数据结构与算法(第七章高级排序2)

小风89
 小风89
发布于 2015/10/26 22:35
字数 780
阅读 143
收藏 6

划    分

        划分数据就是把数据分为两组,使所有关键字大于特定值的数据项在一组,是所有关键字小于特定值的数据项在另一组。

package com.gaojipaixu.partition;

public class Arraypar{
    private long[] theArray;
    private int nElems;
    
    public Arraypar(int max){
        theArray = new long[max];
        nElems = 0;
    }
    
    public void insert(long value){
        theArray[nElems] = value;
        nElems++;
    }
    
    public int size(){
        return nElems;
    }
    
    public void display(){
        System.out.print("A=");
        for (int i = 0; i < nElems; i++) {
            System.out.print(theArray[i]+" ");
        }
        System.out.println("");
    }
    
    public int partitionIt(int left,int right,long pivot){
        int leftPtr = left-1;
        int rightPtr = right+1;
        while(true){
            while(leftPtr<right && 
                theArray[++leftPtr]<pivot)
                ;
            while(rightPtr>left && 
                theArray[--rightPtr]>pivot)
                ;
            if(leftPtr >= rightPtr)
                break;
            else{
                long temp ;
                temp = theArray[leftPtr];
                theArray[leftPtr] = theArray[rightPtr];
                theArray[rightPtr] = temp;
            }
        }
        return leftPtr;
    }
}
public static void main(String[] args) {
		int maxSize = 16;
		Arraypar arr ;
		arr = new Arraypar(maxSize);
		for (int i = 0; i < maxSize; i++) {
			long n = (int)(java.lang.Math.random()*199);
			arr.insert(n);
		}
		arr.display();
		
		long pivot = 99;
		
		System.out.println("Pivot is "+pivot);
		int size = arr.size();
		
		int partDex = arr.partitionIt(0, size-1, pivot);
		
		System.out.println(",Partition is at index "+partDex);
		arr.display();
		
	}
	
//输出:
A=170 142 81 128 131 39 16 186 84 35 46 195 174 114 144 103 
Pivot is 99
,Partition is at index 6
A=46 35 81 84 16 39 131 186 128 142 170 195 174 114 144 103

        可以看出划分是成功的:前6个数字都比枢纽99小;后8个数字则都大于枢纽。

        注意划分的过程不一定要像这个例子一样把数组划分成大小相同的两半;这取决于枢纽及数据关键字的值。有可能一组中数据项个数多于另一组的数据项个数。

    划分算法

        划分算法由两个指针开始工作,两个指针分别指向数组的两头。(这里使用“指针”这个词是指示数组数据项的,而不是C++中所说的指针。)在左边的指针,leftPtr,向右移动,而在右边的指针,rightPtr,向左移动。

        实际上,leftPtr初始化是时在第一个数据项的左边一位,rightPtr是在最后一个数据项的右边一位,这是因为在它们工作之前,它们都要分别的加一和减一。

        停止和交换

        当leftPtr遇到比枢纽小的数据项时,它继续右移,因为这个数据项的位置已经处在数组的正确一边了。但是,当遇到比枢纽大的数据项时,它就停下来,类似的,当rightPrt遇到大于枢纽的数据项时,它继续左移但是当发现比枢纽小的数据项时,它也停下来。当两个内层的while循环,第一个应用leftPtr,第二个应用于rightPrt,控制这个扫描过程。因为指针退出了while循环,所以它停止移动。下面是一段扫描不在适当位置上的数据项的简化代码:

while(theArray[++leftPtr] < pivot) //find bigger item
    ;    //(nop)
while(theArray[--right]>pivot)   //find smaller item
    ;    //(nop)
swap(lefgPtr,rightPtr);            //swap elements

            第一个while循环在发现比枢纽大的数据项时退出;第二个循环在发现小的数据项时退出。当这两个循环都退出之后,leftPtr和rightPrt都指着在数组的错误一方位置上的数据项,所以交换着两个数据项。






























256

© 著作权归作者所有

小风89
粉丝 20
博文 97
码字总数 98307
作品 0
杭州
高级程序员
私信 提问
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
2018/07/25
0
0
2020年,除了《深入理解java虚拟机》,还有哪些java书籍值得一看?

  2020年伊始,很多新粉丝立下了几大目标,其中热门目标之一就是,一年看十本技术书籍,问我有什么推荐,那我就姑且推荐一番,看看除了周志明的《深入理解java虚拟机》之外,还有哪些书籍值...

java进阶架构师
01/01
0
0
Java进阶之路——从初级程序员到架构师,从小工到专家

前言:此文章之前大号发过 后被恶意举报封号然此文章被发到博客 在此不计较那些人品有问题之人 再发一遍 怎样学习才能从一名Java初级程序员成长为一名合格的架构师,或者说一名合格的架构师应...

慕安
2017/06/28
677
4
Java程序员必读书单,家族又添新成员

点击关注异步图书,置顶公众号 每天与你分享IT好书 技术干货 职场知识 参与文末话题讨论,每日赠送异步图书。 ——异步小编 有些革命出其不意地吸引了全世界的眼球。Twitter、Linux操作系统和...

异步社区
2018/05/09
0
0
最全BAT算法面试100题:阿里、百度、腾讯、京东、美团、今日头条

第一:复杂度估算和排序算法(上) 1) 时间复杂度和空间复杂度 2)认识对数器 3)冒泡排序 4)选择排序 5)插入排序 6)如何分析递归过程的时间复杂度 7)归并排序 8)小和问题 第二:复杂度...

编程SHA
2019/04/25
162
0

没有更多内容

加载失败,请刷新页面

加载更多

工作自由--2020年开篇,开启一个项目:工作自由 worksolo.cn

新年伊始,我突发奇想,也是很多人敢想而不敢做的事情,下面我以一个多年软件开发从业者的角度去思考,去设计这个项目,当然希望看到这篇文章的你可以给我更多思路: 项目名称:工作自由 域名...

_aron_
21分钟前
14
0
王道 第一章 计算机系统概述

这门课学的是逻辑实现,不是具体的机型 主要内容: 基本部件的结构和组织方式 基本运算的操作原理 基本部件和单元的设计思想 处理器+内存=计算机 存储器 存储器(高速缓存、主存储器、虚拟存...

heronos
今天
81
0
SpringBoot+Mybatis+Thymeleaf-Build Blog site_1

1、快速构建Springboot项目 (1)、 Spring Boot 项目目录结构介绍 (2)、 Spring Boot 项目启动的几种方式 2、 (1)、hello blog (2)、 DispatchServlet 配置 (3)、 静态 web 资源如何...

杨木发
今天
128
0
关于docker0: iptables: No chain/target/match by that name的问题解决

由于Docker 0默认网桥的iptables策略冲突问题,将导致一些web server启动时出现如下错误: docker: Error response from daemon: driver failed programming external connectivity on endpo......

王焱君
今天
103
0
js 下载 canvas 兼容移动端

很蛋疼的问题PC上好好的, 移动端下载不了 , 貌似前端 js 生成的时 base64 格式的 图片数据,移动端无法直接下载, 但是chrome 移动端和pc端都没问题, 国产的几个浏览器全部挂了 之前的下载方式...

阿豪boy
昨天
96
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部