ITPub博客

首页 > 应用开发 > Java > Java排序算法速度比较(转载)

Java排序算法速度比较(转载)

原创 Java 作者:polalisi 时间:2007-09-11 14:16:18 0 删除 编辑


public class Sort {

public void swap(int a[], int i, int j) {
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}

public int partition(int a[], int low, int high) {
int pivot, p_pos, i;
p_pos = low;
pivot = a[p_pos];
for (i = low + 1; i <= high; i++) {
if (a[i] > pivot) {
p_pos++;
swap(a, p_pos, i);
}
}
swap(a, low, p_pos);
return p_pos;
}

public void quicksort(int a[], int low, int high) {
int pivot;
if (low < high) {
pivot = partition(a, low, high);
quicksort(a, low, pivot - 1);
quicksort(a, pivot + 1, high);
}

}

public static void main(String args[]) {
int vec[] = new int[] { 37, 47, 23, -5, 19, 56 };
int temp;
//
选择排序法(Selection Sort)
long begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length; j++) {
if (vec[j] > vec[i]) {
temp = vec[i];
vec[i] = vec[j];
vec[j] = temp;
}
}

}
}
long end = System.currentTimeMillis();
System.out.println("
选择法用时为:" + (end - begin));
//
打印排序好的结果

for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
//
冒泡排序法(Bubble Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 0; i < vec.length; i++) {
for (int j = i; j < vec.length - 1; j++) {
if (vec[j + 1] > vec[j]) {
temp = vec[j + 1];
vec[j + 1] = vec[j];
vec[j] = temp;
}
}

}
}
end = System.currentTimeMillis();
System.out.println("
冒泡法用时为:" + (end - begin));
//
打印排序好的结果

for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}

//插入排序法(Insertion Sort)
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
for (int i = 1; i < vec.length; i++) {
int j = i;
while (vec[j - 1] < vec[i]) {
vec[j] = vec[j - 1];
j--;
if (j <= 0) {
break;
}
}
vec[j] = vec[i];
}
}
end = System.currentTimeMillis();
System.out.println("
插入法用时为:
" + (end - begin));
//
打印排序好的结果

for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}

//快速排序法(Quick Sort)

Sort s = new Sort();
begin = System.currentTimeMillis();
for (int k = 0; k < 1000000; k++) {
s.quicksort(vec, 0, 5);
}
end = System.currentTimeMillis();
System.out.println("
快速法用时为:" + (end - begin));
//
打印排序好的结果

for (int i = 0; i < vec.length; i++) {
System.out.println(vec[i]);
}
}

}以下是运行结果:选择法用时为:23456
47
37
23
19
-5
冒泡法用时为:17256
47
37
23
19
-5
插入法用时为:7856
47
37
23
19
-5
快速法用时为:29756
47
37
23
19
-5

[@more@]

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10455649/viewspace-968941/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论
  • 博文量
    59
  • 访问量
    56096