Ytl's Java Blog

厚积而薄发---每一天都是一个全新的开始
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Bubble Sort

Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort is stable and adaptive.

Algorithm

  1. Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
  2. If at least one swap has been done, repeat step 1.

You can imagine that on every step big bubbles float to the surface and stay there. At the step, when no bubble moves, sorting stops. Let us see an example of sorting an array to make the idea of bubble sort clearer.

Example. Sort {5, 1, 12, -5, 16} using bubble sort.

Bubble sort example

Complexity analysis

Average and worst case complexity of bubble sort is O(n2). Also, it makes O(n2) swaps in the worst case. Bubble sort is adaptive. It means that for almost sorted array it gives O(n) estimation. Avoid implementations, which don't check if the array is already sorted on every step (any swaps made). This check is necessary, in order to preserve adaptive property.

Turtles and rabbits

One more problem of bubble sort is that its running time badly depends on the initial order of the elements. Big elements (rabbits) go up fast, while small ones (turtles) go down very slow. This problem is solved in the Cocktail sort.

Turtle example. Thought, array {2, 3, 4, 5, 1} is almost sorted, it takes O(n2) iterations to sort an array. Element {1} is a turtle.

Turtle example

Rabbit example. Array {6, 1, 2, 3, 4, 5} is almost sorted too, but it takes O(n) iterations to sort it. Element {6} is a rabbit. This example demonstrates adaptive property of the bubble sort.

Rabbit example

Code snippets

There are several ways to implement the bubble sort. Notice, that "swaps" check is absolutely necessary, in order to preserve adaptive property.

Java

public void bubbleSort(int[] arr) {

      boolean swapped = true;

      int j = 0;

      int tmp;

      while (swapped) {

            swapped = false;

            j++;

           for (int i = 0; i < arr.length - j; i++) {                               

                  if (arr[i] > arr[i + 1]) {                          

                        tmp = arr[i];

                        arr[i] = arr[i + 1];

                        arr[i + 1] = tmp;

                        swapped = true;

                  }

            }                

      }

}

Python

def bubbleSort(L) :

    swapped = True;

    while swapped:

        swapped = False

        for i in range(len(L)-1):

            if L[i]>L[i+1]:

                temp = L[i]

                L[i] = L[i+1]

                L[i+1] = temp

                swapped = True

posted @ 2011-05-06 16:03 ytl| 编辑 收藏

     摘要: 关于二分查找的原理互联网上相关的文章很多,我就不重复了,但网络的文章大部分讲述的二分查找都是其中的核心部分,是不完备的和效率其实还可以提高,如取中间索引使用开始索引加上末尾索引的和除以2,这种做法在数字的长度超过整型的范围的时候就会抛出异常,下面是我的代码,其中可能有些地方没考虑到或有什么不足  阅读全文

posted @ 2011-03-15 12:12 ytl 阅读(2118) | 评论 (5)编辑 收藏

     摘要:   阅读全文

posted @ 2009-11-15 00:18 ytl 阅读(994) | 评论 (0)编辑 收藏

Java处理Excel数据有很多方式,如Apache的POI或JXL等.

我首先给出一个Excele数据的读入的方式(使用的是jxl.jar包)

package com.ccniit.readexcel;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import jxl.Sheet;
import jxl.Workbook;
import jxl.read.biff.BiffException;

public class ExcelHander {

    
public static String[] getColName(String desc) {
        InputStream is 
= null;
        String[] colNames 
= null;
        
try {
            is 
= new FileInputStream(new File(desc));
            Workbook wb 
= Workbook.getWorkbook(is);
            Sheet sheet 
= wb.getSheet(0);
            
int cols = sheet.getColumns();
            colNames 
= new String[cols];
            
for (int i = 0; i < cols; i++{
                colNames[i] 
= sheet.getCell(i, 0).getContents();
                
// System.out.println("列名: " + colNames[i]);
            }

            is.close();
        }
 catch (FileNotFoundException e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        }
 catch (BiffException e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        }
 catch (IOException e) {
            
// TODO Auto-generated catch block
            e.printStackTrace();
        }

        
return colNames;

    }


    
public List<Map<String, Object>> readExcel(String desc) {
        List
<Map<String, Object>> datas = null;
        
try {
            InputStream is 
= new FileInputStream(new File(desc));
            Workbook wb 
= Workbook.getWorkbook(is);
            
if(wb == null){
                
return null;
            }

            Sheet sheet 
= wb.getSheet(0);
            
int cols = sheet.getColumns();
            
int rows = sheet.getRows();
            datas 
= new ArrayList<Map<String, Object>>();
            
for (int i = 1; i < rows; i++{
                Map
<String, Object> data = new HashMap<String, Object>();
                
for (int j = 0; j < cols; j++{
                    String key 
= sheet.getCell(j, 0).getContents();
                    
// System.out.println("key:" + key);
                    Object value = (Object) sheet.getCell(j, i).getContents();
                    
// System.out.println("value:" + value.toString());
                    data.put(key, value);
                }

                datas.add(data);
            }

            is.close();
            wb.close();
        }
 catch (FileNotFoundException e) {
            e.printStackTrace();
        }
 catch (BiffException e) {
            e.printStackTrace();
        }
 catch (IOException e) {
            e.printStackTrace();
        }

        
return datas;
    }


}



posted @ 2009-04-12 13:57 ytl 阅读(321) | 评论 (0)编辑 收藏

再见了我的 2008

谨以此文献给我们的2008年--

但愿你的点点滴滴永存于我们心间....

再见我的2008--杨天宁 

还有一点点的时间
让我们用来回忆
还有一点点的时间
可以用来哭泣
可以不管得到还是失去
轻轻合上眼睛
紧紧抱着它啊
时间这样飞逝
我们就这样长大
我们哭着笑着唱着
在勇敢地成长
想想身边每个朋友
你们是否不再孤单害怕
听时间开始倒记
这样随音乐大声唱起
再见我的2008年
好怀念你在我的身边
当昨天它一点点走远
我知道我们不能回到从前
再见我的2008年
我记得你的每一个瞬间
无论明天悲喜或是改变
只希望我们都能快乐一点
钟声它已走远...

2008,这一年发生了太多太多的事,或许有些事你已经淡忘,但也有些事会长存于你的心间,难以磨灭.

在2008年即将离我们而去之际,让我们回首一下自己这一年所经历过的点点滴滴.在这一年里,我们哭过,笑过,痛苦过,挣扎过,努力过,认真过,也跌到过,爬起过,遗憾过...无论你在这一年里是达到了自己的目标,实现了梦想,还是犯下了不可弥补的错误,让自己身边的人受到伤害,这一切都将过去,因为 2008年在你生命中只有一次而已,而它正逐渐离我们而去...

年初的南方大雪灾(家人因为地滑,摔伤)
手足口病肆虐
藏独事件
网络开始流行全民"中国心"头像
全球华人开展爱国行动 坚决反对西藏独立
奥运火炬传递活动遭藏独份子阻碍
512汶川大地震 无数人在此灾难中痛失亲人朋友(学校损失被迫异地复课)
08年8月8日20点 北京奥运会开幕
刘翔因腿伤退出比赛 成为全民讨论热点
毒奶粉事件 使中国奶制品业受重创
起于美国的金融风暴 席卷全球

2008,是属于中国人的奥运年.从4年前得知我们要举办奥运的那一刻起,到后来奥运圣火辗转传递,然后到奥运会顺利开幕,选手们展开精彩角逐,最后到奥运圆满闭幕,这些都在我们心中留下一个个永生难忘的精彩瞬间 那一个个运动健儿挥洒汗水,顽强拼搏的身影也铭刻于我们心底...

2008,也是中国多灾多难的一年.一个突如其来的大地震,让无数的人痛失自己挚爱的亲人,朋友,也失去了自己心爱的家园...跌倒了,不要紧,最后我们还是爬起来了.当得知这一噩耗时,我们全国同胞都纷纷伸出自己的援助之手,捐资捐物,帮灾民重建家园.这也让我们看到了中华的希望,我们传统的互助精神并没有被遗忘.一个灾难的磨练,令世人更加清楚地认识到了这个民族的力量所在.

......

对于我而言,2008也是具有里程碑式意义的一年.因为这一年我告别了自己的大学生涯,开始人生新旅程.不晓得我这个句号划得完不完美,但是我自己无悔就够了,毕竟我努力过了,就让所大学以前的记忆,所有记忆都停在这一年吧,也停留在我的内心深处...

时间推着我们向前 我们是无法停留在原地的 只有把昨天的记忆埋于心底作养料 用现有的来播种 然后期待明天能开出绚烂的花朵...

再见了,2008;再见了,我的大学生活,虽说是再见却永远不会再见,但愿我在往后十年里能有所成就,也希望09年以后,世界能继续朝着繁荣安定的方向迈进,能顺利找到工作.....

posted @ 2008-12-25 20:09 ytl 阅读(4646) | 评论 (7)编辑 收藏

个人在项目开发中总结的。供大家参考

1.页面显示中文时出现的乱码,通常使用

1 <%@ page contentType="text/html;charset=gb2312"%>

 

可以达到处理乱码的效果

2.从请求中获得数据是出现的中文乱码处理方法有
(1) get请求有两种处理方法
方法1:
在tomcat的配置文件(conf)中的server.xml的

1  <Connector port="8080" protocol="HTTP/1.1" 
2                connectionTimeout="20000" 
3                redirectPort="8443" 
4                URIEncoding="gb2312"/>


加入上面第4行代码即可。
方法2:也就是通常说的再编码的说法,

1<%
2   String name=request.getParameter("name");
3   byte []b = name.getBytes("GB2312");
4   name=new String(b);
5%>
6也可简化为:
7<%=new String(request.getParameter().getBytes("GB2312"))
8%>


(2)post请求
在jsp页面中加入也下代码

1<%request.setCharacterEncoding("gb2312");%>

需要注意的是这部分代码要放写在获得请求内容以前。

3.以上就是JSP页面中出现乱码的方法,最后我想说的就是如何确定发送的
  请求是GET 还是POST。
(1)一般表单(Form)提交中有method方法确定。
(2)通过URL链接传递为GET方法提交
(3)通过地址重写的为GET方法提交

谢谢阅读

posted @ 2008-05-08 16:54 ytl 阅读(1079) | 评论 (3)编辑 收藏

            我是软件专业现在是大二的学生,我们已经学了1年的Java 知识,现在还没有开Java Web  我想多

提前和多学点知识,可我有点迷惑。开始应该还先学JSP方面的知识,学JSP 必须要学习HTML方面的知道,

如涉及到CSS,JS.如果想把网站设计更美观的还需要学习PS。当一切都好的时候,可能考虑学习框架,可现

在Java框架特多,我应该怎么选择,那些好啊。最后学习J2EE方面东西。我在互联网上看到,有点人说学习

J2EE可无EJB,这是真的吗??还有最后问题学了这样一切,现在流行AJAX。又要学习这个知识。我想了我

应该从哪里开始啊。如果都学一个人精力不能有那么多啊,可要是不学那开发做出来东西在外观或其他方面

没有别人好吧。希望那些高手们,帮我出个主意。。谢谢啦。。。

posted @ 2008-01-14 19:45 ytl 阅读(1795) | 评论 (12)编辑 收藏

仅列出标题
共2页: 上一页 1 2