2008-3-26 13:24
jiangjh62
排序算法(java)
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]);
}
}
}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5
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]);
}
}
}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5
2008-5-26 20:30
赵思敏
排序算法(java)
public class Sort {
public void swap(int a[], int i, int j) {
int tmp = a;
a = 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 > 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) {
temp = vec;
vec = 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);
}
// 冒泡排序法(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);
}
//插入排序法(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) {
vec[j] = vec[j - 1];
j--;
if (j <= 0) {
break;
}
}
vec[j] = vec;
}
}
end = System.currentTimeMillis();
System.out.println("插入法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec);
}
//快速排序法(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);
}
}
}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5
public class Sort {
public void swap(int a[], int i, int j) {
int tmp = a;
a = 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 > 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) {
temp = vec;
vec = 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);
}
// 冒泡排序法(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);
}
//插入排序法(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) {
vec[j] = vec[j - 1];
j--;
if (j <= 0) {
break;
}
}
vec[j] = vec;
}
}
end = System.currentTimeMillis();
System.out.println("插入法用时为：" + (end - begin));
//打印排序好的结果
for (int i = 0; i < vec.length; i++) {
System.out.println(vec);
}
//快速排序法(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);
}
}
}
以下是运行结果：
选择法用时为：234
56
47
37
23
19
-5
冒泡法用时为：172
56
47
37
23
19
-5
插入法用时为：78
56
47
37
23
19
-5
快速法用时为：297
56
47
37
23
19
-5
2008-5-26 20:30
赵思敏
(*^__^*) 嘻嘻……顶起来
2008-6-11 17:33
javalod
will you please list that in detail?
*** 作者被禁止或删除 内容自动屏蔽 ***
*** 作者被禁止或删除 内容自动屏蔽 ***
2008-7-29 10:54
hjessica
你这排序效率也太低了吧？
6个数排序要100ms左右？
选择排序在循环内部需要交换数据？？
冒泡排序对吗？？？
你这程序得到的结果正确，是亚微你在第一个排序的时候已经吧数据排好了。后面可定是正确的排序，你用随机生成数据看看，你的排序是不是正确？？、
6个数排序要100ms左右？
选择排序在循环内部需要交换数据？？
冒泡排序对吗？？？
你这程序得到的结果正确，是亚微你在第一个排序的时候已经吧数据排好了。后面可定是正确的排序，你用随机生成数据看看，你的排序是不是正确？？、
2008-7-30 10:41
zhangzongjun
good~
up~
up~
2008-8-5 11:20
laiwq
楼主打个包方便些
页: [1]
查看完整版本: 排序算法(java)
Powered by ITPUB论坛