# 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.

## 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.

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.

## 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 阅读(2619) | 评论 (5)编辑 收藏

摘要:   阅读全文

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

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

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;

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);
}

}

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 阅读(408) | 评论 (0)编辑 收藏

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

512汶川大地震 无数人在此灾难中痛失亲人朋友(学校损失被迫异地复课)
08年8月8日20点 北京奥运会开幕

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

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

......

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

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

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

2.从请求中获得数据是出现的中文乱码处理方法有
(1) get请求有两种处理方法

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

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请求

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

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

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

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

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

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