二分查找,和快排。过几天比较下快排和插入排序,两个的效率。
package algorithms;
/**
* 快排,递归二分查找
* @author henry
* @date 2010-06-04 1:04:10
*/
public class RbSearch {
public static int[] a = { 11, 22, 44, 5, 0, 3, 9, 10, 45 };
/**
* 二分查找
*
* @param left
* @param middle
* @param right
* @param searchkey
* @return
*/
public static boolean binarySearch(int left, int right, int searchkey, int[] arr) {
if(left > right) {//如果左指针大于右指针位置
return false;//返回false
}
int middle = (left + right) / 2;//取数组分割点下标
if(searchkey > arr[middle]) {
return binarySearch(middle + 1, right, searchkey, arr);
}
if(searchkey < arr[middle]) {
return binarySearch(left, middle - 1, searchkey, arr);
}
if(searchkey == arr[middle]) {
System.out.println("找到了!arr[" + middle + "]=" + searchkey);
return true;
}
return false;
}
/**
* 快排2
* 这种方式是用数组的第一位数,作为数组分割点,然后分割排序
*
* @param arr
* @param left
* @param right
*/
public static void quickSort2(int[] arr, int left, int right) {
int povit,tmp;
int i = left;
int j = right;
povit = arr[left];
do {
while(arr[i] < povit && i < right) {//找出比povit大的数
i++;
}
while(arr[j] > povit && j > left) {//找出比povit小的数
j--;
}
if(i < j) {//如果找出数值的位置下标符合条件,则两数组调换
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
} while(i < j);
if(i > j) {//如果左指针大于右指针,把分割数跟下标为j的调换数值
tmp = arr[left];
arr[left] = arr[j];
arr[j] = tmp;
}
if(left < j)
quickSort2(arr, left, j - 1);
if(j < right)
quickSort2(arr, j + 1, right);
}
/**
* 快速排序1
* 这种方式是第一步就取出给定数组的分割点进行排序
*
* @param arr
*/
public static void quickSort(int[] arr, int left, int right) {
int middle, tmp;
int i = left;
int j = right;
middle = arr[(left + right)/2];
do {
while(arr[i] < middle && i < right) {//找出比middle大的数
i++;
}
while(arr[j] > middle && j > left) {//找出比middle小的数
j--;
}
if(i <= j) {//如果找出数值的位置下标符合条件,则两数组调换
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;//i下标右移
j--;//j下标左移
}
} while (i < j);
if(left < j) {
quickSort(arr, left, j);
}
if(right > i) {
quickSort(arr, i, right);
}
}
public static void main(String[] args) {
System.out.println("原序数组:");
for (int k : a) {
System.out.print(k + " ");
}
System.out.println();
quickSort2(a, 0, a.length-1);
System.out.println("排序后:");
for (int k : a) {
System.out.print(k + " ");
}
System.out.println();
int searchKey = 45;//要查询的数字
if(!binarySearch(0, a.length - 1, searchKey, a)) {
System.out.println("查找不到对应数据:" + searchKey);
}
}
}
分享到:
相关推荐
教材和相关的阅读材料中对读者写者问题算法均有描述,但这个算法在不断地有读者流的情况下,写者会被阻塞。编写一个写者优先解决读者写者问题的程序,其中读者和写者均是多个进程,用信号量作为同步互斥机制。
一个理发店,由一间等候室W和一间工作室B组成,理发店环境和运作示意图如下图所示。顾客可以从外面大街上进入W,等候理发。两个房间的入口是并排的且共享一扇日本式可...2)请用P、V操作写出这些进程的同步控制算法。
教材和相关的阅读材料中对读者写者问题算法均有描述,但这个算法在不断地有读者流的情况下,写者会被阻塞。编写一个写者优先解决读者写者问题的程序,其中读者和写者均是多个进程,用信号量作为同步互斥机制。
三、 专业面试对自己简历上不要为了蒙骗面试官,写的项目自己捡不熟悉,对简历上的东西一问三不知,语言表达不清楚,说不半天不能告诉面试官你做的工作内容和意义,这个很不好。 群面 一般10-14个人,看当天应聘的...
参考教材中的生产者消费者算法,创建5个进程,其中两个进程为生产者进程,3个进程为消费者进程。一个生产者进程试图不断地在一个缓冲中写入大写字母,另一个生产者进程试图不断地在缓冲中写入小写字母。3个消费者...
以前写的,用来延时关机。 费功夫的不是写代码而是画图标。
休息的时候无意间看到群里有人发出了华为的校招题,一开始看题目的时候觉得很简单,于是晚上就试着写了一下,结果写的过程中打脸,不断的整理逻辑不断的重写,但我的性格又是不做出来晚上睡不好的那种,于是在做...
根据我20年的读书经验,图书分类上最大的缺陷之一就是没有首先把书分为两类:可以睡前躺在床上看的书和不能躺在床上看的书——因为很多书太重。绝大多数计算机类书籍属于后者,这本书则属于前一类,传递着一种简单、...
参考教材中的生产者消费者算法,创建5个进程,其中两个进程为生产者进程,3个进程为消费者进程。一个生产者进程试图不断地在一个缓冲中写入大写字母,另一个生产者进程试图不断地在缓冲中写入小写字母。3个消费者...
使用系统调用pipe()建立一条管道,两个子进程分别向管道写一句话: Child process1 is sending a message! Child process2 is sending a message! 父进程从管道读出来自两个子进程的信息,显示在屏幕上。 ...
2、采用写者优先重写P94的读者- 写者问题,并通过一个读写序列,将算法与读者优先算法进行比较。 3、P98的53题的上机作业。 【实验原理】 回答以下问题: 1. 简述调用fork创建新进程的过程 Unix系统中,fork属于...
不不不,应该是结婚后,睡在别人的床上,你甘心吗?你的心不会痛吗?所以必须学Linux。 不仅如此,如果你会Linux就能提前在服务器环境进行测试,从而避免很多Bug的产生。如果你会Linux就能搞一些个人常用的服务,为...
能自己编写内核程序并不意味着可以读懂内核,虽然反过来是一定成立的。读懂别人编写的没有代码的程序,比自己编写更困难一些,但的确是值得的。 第8章 进入Windows内核 96 8.1 开始Windows内核编程 97 8.1.1 ...
调整了程序中关卡对于胜利和失败的算法 几个植物和僵尸做了调整 修改了几个BUG 2010.12.27 对初始界面稍作修改 2010.12.9 添加了“靠天吃饭”小游戏 给领带僵尸添加两种形象 修正辣椒爆炸图片的问题 ...
下班后,在家玩魔兽冰峰王座,过全关一个种族(打了3天),开始写InfoBase的MainMenu (主菜单我一直都没有整理功能,呵呵),Access数据库在删除数据后并不会减少文件尺寸,所以加了几个数据库的维护功能。...
CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法,讲CRC算法的文章很多,之所以还要写这篇,是想换一个方法介绍CRC算法,希望能让大家更容易理解CRC算法。 先说说什么是数据校验。数据在传输过程...
能自己编写内核程序并不意味着可以读懂内核,虽然反过来是一定成立的。读懂别人编写的没有代码的程序,比自己编写更困难一些,但的确是值得的。 第8章 进入Windows内核 96 8.1 开始Windows内核编程 97 8.1.1 ...
您不会让我写O(2 n )算法,但是在浪费的CPU周期上我不会失去睡眠 直接支持MySQL BIGINT UNSIGNED类型。 PostgreSQL和SQLite不支持BIGINT UNSIGNED 。 试图为它提供鞋拔的支持已被证明太复杂了。
能自己编写内核程序并不意味着可以读懂内核,虽然反过来是一定成立的。读懂别人编写的没有代码的程序,比自己编写更困难一些,但的确是值得的。 第8章 进入Windows内核 第9章 用C++编写的内核程序 第10章 继续探索...