比较排序之快速排序(实例代码)

2016-02-15 01:27:40 365体育投注网址

快速排序(简称快排)因为其效率较高(平均O(nlogn))经常在笔试题中对其考查。对于快排的第一步是选取一个“基数”,将会用这个“基数”与其它数进行比较交换。而这个“基数”的选择将影响到快排的效率如何,但如果为了选择基数而选择基数则会本末倒置。例如为了找到最佳基数,则需要在整个待排序列中找到中位数,但查找中位数实际上代价又会很高。基数的选择通常来说就是待排序序列中的第一个对象或者中间的一个对象或者最后一个对象。本文以选取第一个元素为例对快排做一个简要分析实现。以待排序列{6, 5, 3, 1, 7, 2, 4}为例,选取第一个元素6为基数。选择了基数过后则需要进行和数组元素进行比较交换,如何进行比较和谁进行比较?快排第二步在数组的第一个元素和最后元素各设置一个“哨兵”。选好基数,设置好哨兵过后,接下来则是开始比较,将基数先与最后一个哨兵j进行比较,如果大于哨兵j则与其进行交换同时哨兵i+1。此时基数不再与哨兵j进行比较,而是与哨兵i进行比较,如果基数大于哨兵i,则哨兵一直向后移,直到大于基数为止交换同时哨兵j-1。重复上面的步骤,基数再与哨兵j比较。最终结果可见哨兵i的位置=哨兵j的位置,此时将基数赋值给这个位置。这样就达到了基数6左边的数字均小于它,右边的数字均大于它,再利用递归对其左右数组进行同样的步骤选取基数,设置哨兵,最后即可完成排序。javapackage com.algorithm.sort.quick;import java.util.Arrays;/** * 快速排序 * Created by yulinfeng on 2017/6/26. */public class Quick { public static void main(String[] args) { int[] nums = {6, 5, 3, 1, 7, 2, 4}; nums = quickSort(nums, 0, nums.length - 1); System.out.println(Arrays.toString(nums)); } /** * 快速排序 * @param nums 待排序数组序列 * @param left 数组第一个元素索引 * @param right 数组最后一个元素索引 * @return 排好序的数组序列 */ private static int[] quickSort(int[] nums, int left, int right) { if (left < right) { int temp = nums[left]; //基数 int i = left; //哨兵i int j = right; //哨兵j while (i < j) { while (i < j && nums[j] >= temp) { j--; } if (i < j) { nums[i] = nums[j]; i++; } while (i < j && nums[i] < temp) { i++; } while (i < j) { nums[j] = nums[i]; j--; } } nums[i] = temp; quickSort(nums, left, i - 1); quickSort(nums, i + 1, right); } return nums; }}Python3#快速排序def quick_sort(nums, left, right): if left < right: temp = nums[left] #基数 i = left #哨兵i j = right #哨兵j while i < j: while i < j and nums[j] >= temp: j -= 1 if i < j: nums[i] = nums[j] i += 1 while i < j and nums[i] < temp: i += 1 if i < j: nums[j] = nums[i] j -= 1 nums[i] = temp quick_sort(nums, left, i - 1) quick_sort(nums, i + 1, right) return numsnums = [6, 5, 3, 1, 7, 2, 4]nums = quick_sort(nums, 0, len(nums) - 1)print(nums)以上这篇比较排序之快速排序(实例代码)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持脚本之家。

在前两篇文章中, 我们实现了同步/异步发送短信以及限制发送短信频率.这一篇, 我们介绍一下限制每日向同一个用户(根据手机号和ip判断)发送短信的次数1、数据表结构由于需要记录整天的发送记录, 因此这里我们将数据保存到数据库中. 数据表结构如下:type为验证码的类型, 比如注册, 重置密码等.sendTime的默认值为当前时间.2、限制日发送次数我们这里需要用到上一篇中提到的接口和实体类.DailyCountFilter.javapublic class DailyCountFilter implements SmsFilter { private int ipDailyMaxSendCount; private int mobileDailyMaxSendCount; private SmsDao smsDao; // 省略了部分无用代码 @Override public boolean filter(SmsEntity smsEntity) { if (smsDao.getMobileCount(smsEntity.getMobile()) >= mobileDailyMaxSendCount) { return false; } if (smsDao.getIPCount(smsEntity.getIp()) >= ipDailyMaxSendCount) { return false; } smsDao.saveEntity(smsEntity); return true; }}主要代码很简单, 首先判断向指定的手机号发送的次数是否达到了日最大发送次数, 之后再判断指定的ip请求发送的次数是否达到了最大次数. 如果都没有, 则将本次发送的手机号, ip等信息保存到数据库中.当然, 这个类存在一定的问题: 在判断是否超过最大次数到保存实体数据之间可能已经有其他线程保存了新的数据. 造成上面的两个判断并不是绝对的准确.我们可以使用序列化等级的事务保证不会发生错误, 但是代价太高. 因此我们这里不做处理. 因为我们前面已经实现了限制发送频率. 如果先使用FrequencyFilter过滤一次, 限制发送频率, 那么基本上不可能出现前面说的问题.还有一个问题: 随着时间的推移, 这个表会越来越大, 造成查询的性能相当的差. 我们可以向上一篇中那样, 每隔一段时间就删除无用的数据; 也可以动态的创建表, 然后向新表中插入数据.3、使用动态表这里我们采用第二种方案: 数据表的名字为"sms_四位年_两位月", 比如"sms_2016_02". 插入数据时根据现在的时间获得表名, 然后再插入. 另外使用Quartz在每月的20号2点生成下个月以及下下个月的数据表:我们首先修改DailyCountFilter类, 在这个类中添加任务计划, 定时生成数据表:DailyCountFilter.java// 在上面代码的基础上, 再添加如下代码public class DailyCountFilter implements SmsFilter { private Scheduler sched; @Override public void init() throws SchedulerException { smsDao.createTable(0); // 创建这个月的数据表 smsDao.createTable(1); // 创建下个月的数据表 SchedulerFactory sf = new StdSchedulerFactory(); sched = sf.getScheduler(); // 创建Quartz容器 JobDataMap jobDataMap = new JobDataMap(); jobDataMap.put("smsDao", smsDao); // 创建运行任务时需要使用的数据map // 创建job对象, 该对象执行实际的任务 JobDetail job = JobBuilder.newJob(CreateSmsTableJob.class) .usingJobData(jobDataMap) .withIdentity("create sms table job").build(); // 创建trigger对象, 该对象用来描述触发执行job的时间规则 // 比如这里的每月20号2点 CronTrigger trigger = TriggerBuilder.newTrigger() .withIdentity("create sms table trigger") .withSchedule(CronScheduleBuilder.cronSchedule("0 0 2 20 * ?"))// 每月的20号2点 .build(); sched.scheduleJob(job, trigger); // 注册任务和触发规则 sched.start(); // 启动调度 } @Override public void destroy() { try { sched.shutdown(); } catch (SchedulerException e) {} } public static class CreateSmsTableJob implements Job { @Override public void execute(JobExecutionContext context) throws JobExecutionException { JobDataMap dataMap = context.getJobDetail().getJobDataMap(); SmsDao smsDao = (SmsDao) dataMap.get("smsDao"); // 获得传过来的smsDao对象 smsDao.createTable(1); // 创建下个月的数据表 smsDao.createTable(2); // 创建下下个月的数据表 } }}接下来, 我们看看SmsDao的部分代码:SmsDao.javapublic class SmsDao { /** * 创建新的日志表 * * @param monthExcursion 偏移的月数 */ public void createTable(int monthExcursion){ String sql = "CREATE TABLE IF NOT EXISTS " + getTableName(monthExcursion) + " LIKE sms"; // 执行sql语句 } /** * 保存SmsEntity实体对象 */ public void saveEntity(SmsEntity smsEntity){ String sql = "INSERT INTO " + getNowTableName() + " (mobile, ip, type) VALUES(?, ?, ?)"; // 执行sql语句 } /** * 获得指定手机号今天请求发送短信的次数 * * @param mobile 用户手机号 * @return 今天请求发送短信的次数 */ public long getMobileCount(String mobile){ String sql = "SELECT count(id) FROM " + getNowTableName() + " WHERE mobile=? AND time >= CURDATE()"; // 执行sql语句, 返回查询结果 } // 省略了getIPCount方法 /** * 获得现在使用的表的名字 */ private String getNowTableName() { return getTableName(0); } private DateFormat dateFormat = new SimpleDateFormat("yyyy_MM"); /** * 获得相对现在偏移monthExcursion月的表名 * * @param monthExcursion 偏移的月数 * @return 对应月的表名 */ private String getTableName(int monthExcursion) { Calendar calendar = Calendar.getInstance(); calendar.add(Calendar.MONTH, monthExcursion); Date date = calendar.getTime(); return "sms_" + dateFormat.format(date); }}SmsDao中的createTable方法成功运行有个前提, 就是存在sms数据表. createTable方法会复制sms表的结构创建新的数据表.我们保留发送短信的数据(手机号, ip, 时间等), 而不是直接删除, 是因为以后可能需要分析这些数据, 获取我们想要的信息, 比如判断服务商短信的到达率、是否有人恶意发送短信等. 甚至可能获得意外的"惊喜".以上就是本文的全部内容,希望大家可以继续关注。

详解XML,Object,Json转换与Xstream的使用1.Xstream的特点:这里直接引用Xstream官方的叙述: 灵活易用:在更高的层次上提供了简单、灵活、易用的统一接口,用户无需了解项目的底层细节 无需映射:大多数对象都可以在无需映射的情况下进行序列化与反序列化的操作 高速稳定:设计时力求达到的最重要的指标是解析速度快、占用内存少,以使之能够适用于大的对象处理或是对信息吞吐量要求高的系统 清晰易懂:项目采用reflection机制得到无冗余信息的XML文件。所生成 的XML文件较本地Java序列化产物更简洁,格式更清晰,更便于用户阅读 无需修改:完全序列化包括private和final类型在内的全部内部字段。支 持非公有类和内部类,类可以没有缺省的构造函数 易于集成:通过实现特定的接口,XStream可以直接与其它任何树型结构进行序列化与反序 列化操作(而不仅仅是XML格式) 灵活转换:转换策略是可以定制的,允许用户自定义特殊类型的对象如何以XML格式存储。 错误处理:由于XML资料不合法而造成异常时,会提供详细地诊断信息帮助处理问题。 2.初始化XStream类说Xstream简单是因为它提供统一入口,主要类XStream用作所有项目的入口点。它将重要组件集成在一起,提供更简单易用的API操作。我们可以使用以下的语句进行初始化操作:XStreamxstream = new XStream();默认情况下,XStream会 采用Xpp3库,XPP3是一种运行效率非常高的XML全解析实现。如果你不想依靠Xpp3库的话,也可以使用一个标准的JAXP DOM解析器,可以采用以下语句进行初始化://不使用XPP3库XStreamxstream = new XStream(new DomDriver());此xstream实例,为线程安全的,可以供多个线程进行调用,共享使用。参考 com.thoughtworks.xstream.io.xml包,会发现系统提供了多种标识解析器供我们选择,包括,DomDriver、 JDomDriver、StaxDriver等等。前面提到了Xstream提供了对Json的支持,是因为Xstream内置了两个Driver:1.JsonHierarchicalStreamDriver:不依赖其他类库,只实现 obj->JSON2.JettisonMappedXmlDriver:依赖jettison类库,实现 JSON->obj or obj->JSON 两种Driver在处理相同设置的Object时会得到不同的JSON串,JsonHierarchicalStreamDriver得到的串更简洁,确如官网所说。JsonHierarchicalStreamDriver有个小问题——默认输出带格式的JSON串,结构中带空格、换行,并且没有提供修饰方式。3.常用方法:xStream.toXML(object):将对象转换成XML、Json。xStream.toXML(obj, outputStream):将对象转换XML、Json并封装成输出流。xStream.toXML(object, writer): 将对象转换XML、Json并封成写入流。xStream.fromXML():将XML、Json转换成对象,此方法接受File、InputStream、Reader、String、URL类型的参数。xStream.alias("news", News.class):为指定类名创建别名。xStream.useAttributeFor(News.class, "id"):将id设为 News的元素的属性。xStream.aliasField("other", BookShelf.class,"remark"):修改节点名称,将BookShelf类中的remark节点名修改为other。xStream.addImplicitCollection(BookShelf.class, "books"):去掉集体节点的父节点。xStream.aliasAttribute("姓名", "name"):修改属性的name,为姓名。4.实例1:将对象转换成XML   /** * 将对象转换成Xml格式的字符串 * @param object 要转换成Xml的对象 * @return String:Xml格式的字符串 */ public static String convertObject2Xml(Object object) { xStream=new XStream(); xStream.alias("news", News.class);//修改元素名称 xStream.useAttributeFor(News.class, "id");//将id设为News的元素的属性 return xStream.toXML(object); } 5.实例2:将XML象转换成对象/** * 将成Xml格式的字符串转换成Java对象 * @param inputStream 要转换成Java对象的inputStream * @return String:Xml格式的字符串 */ public static Object convertXml2Object(InputStream inputStream) { xStream=new XStream(); xStream.alias("news", News.class);//修改元素名称 xStream.useAttributeFor(News.class, "id");//将id设为News的元素的属性 return xStream.fromXML(inputStream);//此方法也可将xml转换成map } 6.实例3:将对象转换成Json/** * 将对象转换成Json格式的字符串 * @param object 要转换成Json的对象 * @return String:Json格式的字符串 */ public static String convertObject2Json(Object object) { xStream = new XStream(newJsonHierarchicalStreamDriver() { publicHierarchicalStreamWriter createWriter(Writer out) { //删除根节点 return new JsonWriter(out, JsonWriter.DROP_ROOT_MODE); } }); return xStream.toXML(object); } 感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

Java是垃圾回收语言的一种,其优点是开发者无需特意管理内存分配,降低了应用由于局部故障(segmentation fault)导致崩溃,同时防止未释放的内存把堆栈(heap)挤爆的可能,所以写出来的代码更为安全。不幸的是,在Java中仍存在很多容易导致内存泄漏的逻辑可能(logical leak)。如果不小心,你的Android应用很容易浪费掉未释放的内存,最终导致内存用光的错误抛出(out-of-memory,OOM)。1.一般内存泄漏(traditional memory leak)的原因是:当该对象的所有引用都已经释放了,对象仍未被释放。(译者注:Cursor忘记关闭等)2.逻辑内存泄漏(logical memory leak)的原因是:当应用不再需要这个对象,当仍未释放该对象的所有引用。如果持有对象的强引用,垃圾回收器是无法在内存中回收这个对象。在Android开发中,最容易引发的内存泄漏问题的是Context。比如Activity的Context,就包含大量的内存引用,例如View Hierarchies和其他资源。一旦泄漏了Context,也意味泄漏它指向的所有对象。Android机器内存有限,太多的内存泄漏容易导致OOM。检测逻辑内存泄漏需要主观判断,特别是对象的生命周期并不清晰。幸运的是,Activity有着明确的生命周期,很容易发现泄漏的原因。Activity.onDestroy()被视为Activity生命的结束,程序上来看,它应该被销毁了,或者Android系统需要回收这些内存(译者注:当内存不够时,Android会回收看不见的Activity)。如果这个方法执行完,在堆栈中仍存在持有该Activity的强引用,垃圾回收器就无法把它标记成已回收的内存,而我们本来目的就是要回收它!结果就是Activity存活在它的生命周期之外。Activity是重量级对象,应该让Android系统来处理它。然而,逻辑内存泄漏总是在不经意间发生。(译者注:曾经试过一个Activity导致20M内存泄漏)。在Android中,导致潜在内存泄漏的陷阱不外乎两种:全局进程(process-global)的static变量。这个无视应用的状态,持有Activity的强引用的怪物。活在Activity生命周期之外的线程。没有清空对Activity的强引用。检查一下你有没有遇到下列的情况。1.Static Activities在类中定义了静态Activity变量,把当前运行的Activity实例赋值于这个静态变量。如果这个静态变量在Activity生命周期结束后没有清空,就导致内存泄漏。因为static变量是贯穿这个应用的生命周期的,所以被泄漏的Activity就会一直存在于应用的进程中,不会被垃圾回收器回收。static Activity activity; void setStaticActivity() { activity = this;}View saButton = findViewById(R.id.sa_button);saButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { setStaticActivity(); nextActivity(); }});2.Static Views类似的情况会发生在单例模式中,如果Activity经常被用到,那么在内存中保存一个实例是很实用的。正如之前所述,强制延长Activity的生命周期是相当危险而且不必要的,无论如何都不能这样做。特殊情况:如果一个View初始化耗费大量资源,而且在一个Activity生命周期内保持不变,那可以把它变成static,加载到视图树上(View Hierachy),像这样,当Activity被销毁时,应当释放资源。(译者注:示例代码中并没有释放内存,把这个static view置null即可,但是还是不建议用这个static view的方法)static view; void setStaticView() { view = findViewById(R.id.sv_button);}View svButton = findViewById(R.id.sv_button);svButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { setStaticView(); nextActivity(); }});3.Inner Classes继续,假设Activity中有个内部类,这样做可以提高可读性和封装性。将如我们创建一个内部类,而且持有一个静态变量的引用,恭喜,内存泄漏就离你不远了(译者注:销毁的时候置空,嗯)。private static Object inner; void createInnerClass() { class InnerClass { } inner = new InnerClass();}View icButton = findViewById(R.id.ic_button);icButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { createInnerClass(); nextActivity(); }});内部类的优势之一就是可以访问外部类,不幸的是,导致内存泄漏的原因,就是内部类持有外部类实例的强引用。4.Anonymous Classes相似地,匿名类也维护了外部类的引用。所以内存泄漏很容易发生,当你在Activity中定义了匿名的AsyncTsk。当异步任务在后台执行耗时任务期间,Activity不幸被销毁了(译者注:用户退出,系统回收),这个被AsyncTask持有的Activity实例就不会被垃圾回收器回收,直到异步任务结束。void startAsyncTask() { new AsyncTask<Void, Void, Void>() { @Override protected Void doInBackground(Void... params) { while(true); } }.execute();} super.onCreate(savedInstanceState);setContentView(R.layout.activity_main);View aicButton = findViewById(R.id.at_button);aicButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { startAsyncTask(); nextActivity(); }});5.Handler同样道理,定义匿名的Runnable,用匿名类Handler执行。Runnable内部类会持有外部类的隐式引用,被传递到Handler的消息队列MessageQueue中,在Message消息没有被处理之前,Activity实例不会被销毁了,于是导致内存泄漏。void createHandler() { new Handler() { @Override public void handleMessage(Message message) { super.handleMessage(message); } }.postDelayed(new Runnable() { @Override public void run() { while(true); } }, Long.MAX_VALUE >> 1);}View hButton = findViewById(R.id.h_button);hButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { createHandler(); nextActivity(); }});6.Threads我们再次通过Thread和TimerTask来展现内存泄漏。void spawnThread() { new Thread() { @Override public void run() { while(true); } }.start();}View tButton = findViewById(R.id.t_button);tButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { spawnThread(); nextActivity(); }});7.TimerTask只要是匿名类的实例,不管是不是在工作线程,都会持有Activity的引用,导致内存泄漏。void scheduleTimer() { new Timer().schedule(new TimerTask() { @Override public void run() { while(true); } }, Long.MAX_VALUE >> 1);}View ttButton = findViewById(R.id.tt_button);ttButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { scheduleTimer(); nextActivity(); }});8.Sensor Manager最后,通过Context.getSystemService(int name)可以获取系统服务。这些服务工作在各自的进程中,帮助应用处理后台任务,处理硬件交互。如果需要使用这些服务,可以注册监听器,这会导致服务持有了Context的引用,如果在Activity销毁的时候没有注销这些监听器,会导致内存泄漏。void registerListener() { SensorManager sensorManager = (SensorManager) getSystemService(SENSOR_SERVICE); Sensor sensor = sensorManager.getDefaultSensor(Sensor.TYPE_ALL); sensorManager.registerListener(this, sensor, SensorManager.SENSOR_DELAY_FASTEST);}View smButton = findViewById(R.id.sm_button);smButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { registerListener(); nextActivity(); }});总结看过那么多会导致内存泄漏的例子,容易导致吃光手机的内存使垃圾回收处理更为频发,甚至最坏的情况会导致OOM。垃圾回收的操作是很昂贵的开销,会导致肉眼可见的卡顿。所以,实例化的时候注意持有的引用链,并经常进行内存泄漏检查。

eclipse 系统内部自带了浏览器,打开步骤如下:(1)点击工具栏Window 菜单并选择 Show View;(2)选择 show view > other;(3)在弹出来的对话框的搜索栏中输入 "browser";(4)在树形菜单中选择 "Internal Web Browser" 并点击 OK。(5)在内置浏览器中我们在地址栏中输入网址,如:http://www.jb51.net/,即可打开网页。总结以上就是打开eclipse内置浏览器的步骤,希望对大家有所帮助。更多有关eclipse的内容可以浏览:Eclipse 4.3.2 SR2 官方中文最新版32位、eclipse使用教程(图文)、eclipse常用设置图解等。