文档章节

常见算法的记录

文森特梵高
 文森特梵高
发布于 2015/08/20 09:06
字数 597
阅读 60
收藏 7

快速排序

时间复杂度 O(n*log2n)

总结起来,快排的核心算法只有两步:

1)sort排序函数中,调用分区函数partition,将大的数组分成两块,然后再分别调用sort函数,这是一个递归过程。

2)partition分区函数

public class QSort {

	public static void main(String[] args) {
		quicksort qs = new quicksort();
		int data[] = { 44, 22, 2, 32, 54, 22, 88, 77, 99, 11 };
		qs.data = data;
		qs.sort(0, qs.data.length - 1);
		qs.display();
	}

}

class quicksort {
	public int data[];

	private int partition(int sortArray[], int low, int hight) {
		int key = sortArray[low];

		while (low < hight) {
			while (low < hight && sortArray[hight] >= key)
				hight--;
			sortArray[low] = sortArray[hight];

			while (low < hight && sortArray[low] <= key)
				low++;
			sortArray[hight] = sortArray[low];
		}
		sortArray[low] = key;
		return low;
	}

	public void sort(int low, int hight) {
		if (low < hight) {
			int result = partition(data, low, hight);
			sort(low, result - 1);
			sort(result + 1, hight);
		}

	}

	public void display() {
		for (int i = 0; i < data.length; i++) {
			System.out.print(data[i]);
			System.out.print(" ");
		}
	}
}


二分查找算法

public class BinarySearch {
	private int rCount=0;
	private int lCount=0;
	
	/**
	 * 获取递归的次数
	 * @return
	 */
	public int getrCount() {
		return rCount;
	}

	/**
	 * 获取循环的次数
	 * @return
	 */
	public int getlCount() {
		return lCount;
	}

	/**
	 * 执行递归二分查找,返回第一次出现该值的位置
	 * @param sortedData	已排序的数组
	 * @param start			开始位置
	 * @param end			结束位置
	 * @param findValue		需要找的值
	 * @return				值在数组中的位置,从0开始。找不到返回-1
	 */
	public int searchRecursive(int[] sortedData,int start,int end,int findValue)
	{
		rCount++;
		if(start<=end)
		{
			//中间位置
			int middle=(start+end)>>1;	//相当于(start+end)/2
			//中值
			int middleValue=sortedData[middle];
			
			if(findValue==middleValue)
			{
				//等于中值直接返回
				return middle;
			}
			else if(findValue<middleValue)
			{
				//小于中值时在中值前面找
				return searchRecursive(sortedData,start,middle-1,findValue);
			}
			else
			{
				//大于中值在中值后面找
				return searchRecursive(sortedData,middle+1,end,findValue);
			}
		}
		else
		{
			//找不到
			return -1;
		}
	}
	
	/**
	 * 循环二分查找,返回第一次出现该值的位置
	 * @param sortedData	已排序的数组
	 * @param findValue		需要找的值
	 * @return				值在数组中的位置,从0开始。找不到返回-1
	 */
	public int searchLoop(int[] sortedData,int findValue)
	{
		int start=0;
		int end=sortedData.length-1;
		
		while(start<=end)
		{
			lCount++;
			//中间位置
			int middle=(start+end)>>1;	//相当于(start+end)/2
			//中值
			int middleValue=sortedData[middle];
			
			if(findValue==middleValue)
			{
				//等于中值直接返回
				return middle;
			}
			else if(findValue<middleValue)
			{
				//小于中值时在中值前面找
				end=middle-1;
			}
			else
			{
				//大于中值在中值后面找
				start=middle+1;
			}
		}
		//找不到
		return -1;
	}
}

public class BinarySearchTest {  
	public static void main(String[] args) {
		BinarySearch bs=new BinarySearch();  
        
        int[] sortedData={1,2,3,4,5,6,6,7,8,8,9,10};  
        int findValue=9;  
        int length=sortedData.length;  
          
        int pos=bs.searchRecursive(sortedData, 0, length-1, findValue);  
        System.out.println("Recursice:"+findValue+" found in pos "+pos+";count:"+bs.getrCount());  
        int pos2=bs.searchLoop(sortedData, findValue);  
          
        System.out.println("Loop:"+findValue+" found in pos "+pos+";count:"+bs.getlCount());  
	}
}


© 著作权归作者所有

文森特梵高
粉丝 2
博文 28
码字总数 15386
作品 0
广州
程序员
私信 提问
八大排序算法-概要

常见的算法大概有8种,是我们需要掌握的。这些排序又可以分为排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,...

驛路梨花醉美
2016/06/20
14
0
常见排序算法小结

http://blog.csdn.net/whuslei/article/details/6442755 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特...

毛朱
2015/09/11
53
0
PHPer面试指南-算法篇

本书的 GitHub 地址:https://github.com/todayqq/PHPerInterviewGuide 算法可以说是大厂的必考题,对于算法,一定要理解其中的精髓、原理。 冒泡排序 冒泡排序的原理:一组数据,比较相邻数...

angkee
2018/01/24
0
0
常见排序算法及实现

一、冒泡排序 冒泡排序(Bubble Sort)是先从数组第一个元素开始,依次比较相邻两个数,若前者比后者 大,就将两者交换位置,然后处理下一对,依此类推,不断扫描数组,直到完成排序。 这个算...

thanatos_y
2016/07/30
47
0
聊聊分布式ID生成方法

目标: (1)全局唯一 (2)趋势有序 如何高效生成趋势有序的全局唯一ID呢? 一、需求缘起 几乎所有的业务系统,都有生成一个记录标识的需求,例如: (1)消息标识:message-id (2)订单标...

page_zxy
2016/12/27
71
0

没有更多内容

加载失败,请刷新页面

加载更多

计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
今天
5
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
今天
7
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
今天
6
0
【技术分享】TestFlight测试的流程文档

上架基本需求资料 1、苹果开发者账号(如还没账号先申请-苹果开发者账号申请教程) 2、开发好的APP 通过本篇教程,可以学习到ios证书申请和打包ipa上传到appstoreconnect.apple.com进行TestF...

qtb999
今天
10
0
再见 Spring Boot 1.X,Spring Boot 2.X 走向舞台中心

2019年8月6日,Spring 官方在其博客宣布,Spring Boot 1.x 停止维护,Spring Boot 1.x 生命周期正式结束。 其实早在2018年7月30号,Spring 官方就已经在博客进行过预告,Spring Boot 1.X 将维...

Java技术剑
今天
18
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部