一、 划分算法描述
1. 划分就是将数据项分成两组,一组大于某个特定的数据项,而另一组小于某个特定的数据项。在划分算法中,这个特定的数据项叫做枢纽。
2. 如下图所示:划分算法的思想是:中间的横线代表枢纽;数据项的左端和右端分别有两个指针(leftPtr和rightPtr);leftPtr从左向右遍历元素,rightPtr从右向左遍历元素,当leftPtr遇到比枢纽元素大的元素时停止,当rightPtr遇到比枢纽元素小的元素时停止,然后将这两个元素交换位置;接下来,leftPtr继续向右遍历,rightPtr继续向左遍历,重复上面的操作;当两个指针相遇时遍历结束。
二、 Java语言描述划分算法
package com.solid.sort;
public class Partition {
//定义数组
private int[] arr;
private static int nElems;
/**
* 构造方法
* @param maxSize
*/
public Partition(int maxSize) {
arr = new int[maxSize];
nElems = 0;
}
/**
* 数组中插入元素
* @param key
*/
public void insert(int key) {
arr[nElems++] = key;
}
/**
* 遍历数组中的所有元素
*/
public void display() {
for(int i=0; i<nElems; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
/**
* 划分算法
* @param left
* @param right
* @param pivot
* @return
*/
public int partitionIt(int left, int right, int pivot) {
int leftPtr = left - 1;
int rightPtr = right + 1;
while(true) {
while(leftPtr < right && arr[++leftPtr] < pivot)
;
while(rightPtr > left && arr[--rightPtr] > pivot)
;
if(leftPtr >= rightPtr) {
break;
} else {
int temp = arr[leftPtr];
arr[leftPtr] = arr[rightPtr];
arr[rightPtr] = temp;
}
}
return leftPtr;
}
/**
* 测试main方法
* @param args
*/
public static void main(String[] args) {
Partition partition = new Partition(100);
partition.insert(15);
partition.insert(30);
partition.insert(65);
partition.insert(70);
partition.insert(18);
partition.insert(75);
partition.insert(55);
partition.insert(40);
partition.display();
System.out.println("pivot at index:" + partition.partitionIt(0, nElems-1, 50));
partition.display();
}
}
分享到:
相关推荐
第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和...
第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值和最小值 删除节点 ...
高级算法点此进入:(下方link因为部署需要无法直接查看)图论/离散基础算法分析设计该部份比较简单,因此不做详细介绍,仅提供一个目录和部份知识点。复杂度分析分治贪心动规划分问题回溯局搜图灵机与P/NP/NPCP/NP/...
第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值...
第7章 高级排序 希尔排序 划分 快速排序 基数排序 小结 问题 实验 编程作业 第8章 二叉树 为什么使用二叉树? 树的术语 一个类比 二叉搜索树如何工作 查找节点 插入一个节点 遍历树 查找最大值...
4.问:一个算法应该具有哪五个重要的特征? 答:①有穷性:算法的有穷性是指算法必须能在执行有限个步骤之后终止; ②确切性:算法的每一步骤必须有确切的定义; ③输入项:一个算法有0个或多个输入,以刻画运算...
6.5.3 实例分析3——网格重新划分算法MAPS 附录6.1 数学背景 附录6.2 演示 第三部分 动画制作 第7章 角色动画 7.1 简介 7.2 顶点动画与合成 7.3 骨架动画 7.4 低层次动画管理 7.4.1 行进的路径规划 7.4.2 骨架动画...
6.5.5 基于排序的一个简单的连接算法 6.5.6 简单排序连接的分析 6.5.7 一种更有效的基于排序的连接 6.5.8 基于排序的算法小结 习题 6.6 基于散列的两趟算法 6.6.1 通过散列划分关系 6.6.2 基于散列的...
6.5.3 实例分析3——网格重新划分算法MAPS 附录6.1 数学背景 附录6.2 演示 第三部分 动画制作 第7章 角色动画 7.1 简介 7.2 顶点动画与合成 7.3 骨架动画 7.4 低层次动画管理 7.4.1 行进的路径规划 7.4.2 骨架动画...
主题细目话题采集数据结构LinkedList,堆,数组,ArrayList,HashMap,树,图,堆栈,队列,双端队列演算法排序,搜索,BFS,Dijkstra,动态编程,NQueens Android开发天气报告,GithubProfile应用程序,
数据结构与算法:最常见的各种排序,最好能手写 .. Java 高级:JVM 内存结构、垃圾回收器、回收算法、GC、并发编程相关(多 线程、线程池等)、NIO/BIO、各种集合类的比较优劣势(底层数据结构也要 掌握,特别是扩容等)...
2. Jvm堆内存的划分结构和优化 3 2.1. 原理 6 2.1.1. 年轻代 6 2.1.2. 年老代 6 2.1.3. 持久代 7 2.2. 参数说明 8 2.3. 疑问解答 9 2.4. 垃圾回收器选择 10 2.4.1. 串行收集器 10 2.4.2. 并行收集器(吞吐量优先) ...
128 5.1.2 规则的排序方案 129 5.1.3 如何建立基于规则的分类器 130 5.1.4 规则提取的直接方法 130 5.1.5 规则提取的间接方法 135 5.1.6 基于规则的分类器的特征 136 5.2 最近邻分类器 137 5.2.1 算法 138 5.2.2 ...
13.1.4 三/五法则 447 13.1.5 使用=default 449 13.1.6 阻止拷贝 449 13.2 拷贝控制和资源管理 452 13.2.1 行为像值的类 453 13.2.2 定义行为像指针的类 455 13.3 交换操作 457 13.4 拷贝控制示例 ...
被毁坏的玉米地 ACM程序设计培训教程 经典数据结构与算法……………………………………………………………1 1.1 线性表………………………………………………………………………………1 1.1.1 线性表的顺序存储...
13.1.4 三/五法则 447 13.1.5 使用=default 449 13.1.6 阻止拷贝 449 13.2 拷贝控制和资源管理 452 13.2.1 行为像值的类 453 13.2.2 定义行为像指针的类 455 13.3 交换操作 457 13.4 拷贝控制示例 ...
//next是指针变量,指向构造体变量 【算法思想】 利用一维构造体存放所有学生的信息,输入后,在输出时要对学生按学号的上下排序 ,然后可以执行按学号查询学生信息,输入学号,删除学生信息,输入学号可以找出该 ...