目录
排序方法包排序工具包时间记录包测试包
主要是利用oop的思想来书写排序代码，本篇博客中，包括了：冒泡排序、选择排序、插入排序、希尔排序、快速排序、分桶排序，这6种排序算法。同时，还利用时间记录包来计算上述6种排序算法在同等任务量下，完成任务所需要的时间，从而得出哪种方法比较好用一些。
下方的代码可以直接复制到开发软件中进行测试。
排序方法包
public class Sort {
private void swap(int[] arr
, int begin
, int end
) {
int t
= arr
[begin
];
arr
[begin
] = arr
[end
];
arr
[end
] = t
;
}
public void bubble(int[] arr
) {
int t
;
for (int i
= 0; i
< arr
.length
- 1; i
++) {
for (int j
= 0; j
< arr
.length
- 1 - i
; j
++) {
if (arr
[j
] > arr
[j
+ 1]) {
swap(arr
,j
,j
+1);
}
}
}
}
public void select(int[] arr
) {
for (int i
= 0; i
< arr
.length
; i
++) {
int maxIx
= arr
.length
- 1-i
, maxValIx
= 0, t
;
for (int j
= 1; j
<= arr
.length
-1-i
; j
++) {
if (arr
[j
] > arr
[maxValIx
]) {
maxValIx
=j
;
}
if (maxIx
!= maxValIx
) {
swap(arr
,maxIx
,maxValIx
);
}
}
}
}
public void insert(int[] arr
) {
int t
, j
;
for (int i
= 1; i
< arr
.length
; i
++) {
t
= arr
[i
];
for (j
= i
- 1; j
>= 0 && arr
[j
] > t
; j
--) {
arr
[j
+ 1] = arr
[j
];
}
arr
[j
+ 1] = t
;
}
}
public void hill(int[] arr
) {
int step
= arr
.length
, t
;
while ((step
= step
/ 2) > 2) {
for (int i
= 0; i
+ step
< arr
.length
; i
++) {
if (arr
[i
] > arr
[i
+ step
]) {
swap(arr
,i
,i
+step
);
}
}
}
insert(arr
);
}
private int midNum(int[] arr
, int begin
, int end
) {
int _begin
= begin
, t
;
while (begin
< end
) {
if (arr
[end
] >= arr
[_begin
]) end
--;
else {
if (arr
[begin
] <= arr
[_begin
]) {
begin
++;
} else {
swap(arr
,begin
,end
);
}
}
}
if (begin
!= _begin
) {
swap(arr
,_begin
,begin
);
}
return _begin
;
}
public void quick(int[] arr
, int begin
, int end
) {
if (begin
>= end
) return;
int mid
= midNum(arr
, begin
, end
);
quick(arr
, begin
, mid
- 1);
quick(arr
, mid
+ 1, end
);
}
public void print(int[] arr
) {
for (int i
: arr
) {
System
.out
.print(i
+ "\t");
}
}
public void bucket(int[] arr
) {
final int U
= 10;
int[][] bucket
= new int[U
][arr
.length
];
int[] ixs
= new int[U
];
int t
, count
;
for (int i
= 1; ; i
*= U
) {
count
= 0;
for (int j
= 0; j
< arr
.length
; j
++) {
count
= (t
= arr
[j
] / i
) >= 1 ? ++count
: count
;
bucket
[t
%= U
][ixs
[t
]++] = arr
[j
];
}
if (count
== 0) break;
for (int j
= 0, ix
= 0; j
< bucket
.length
; j
++) {
for (int k
= 0; k
< ixs
[j
]; k
++) {
arr
[ix
++] = bucket
[j
][k
];
}
}
for (int i1
= 0; i1
< ixs
.length
; i1
++) {
ixs
[i1
] = 0;
}
}
}
}
排序工具包
import java
.util
.Random
;
public class SortTool {
public static int[] mkArray(int size
){
Random rand
= new Random();
int[] arr
= new int[size
];
for (int i
= 0; i
<arr
.length
; i
++) {
arr
[i
]=rand
.nextInt(size
*13)+1;
}
return arr
;
}
public static void find(boolean begin
,int[] arr
){
if (arr
.length
>100){
if (begin
) Timer
.begin();
else Timer
.end();
return;
}
int count
=0;
for (int i
: arr
) {
System
.out
.print(i
+"\t");
if (++count
%20==0){
System
.out
.println();
}
}
System
.out
.println();
}
}
时间记录包
public class Timer {
private static long begin
;
public static void begin(){
begin
=System
.currentTimeMillis();
}
public static float end(){
float diff
= (System
.currentTimeMillis()-begin
)/1000.0f;
System
.out
.println("耗时"+diff
+"秒");
return diff
;
}
}
测试包
public class Test {
public static void main(String
[] args
) {
int[] arr
= SortTool
.mkArray(10);
Sort st
= new Sort();
SortTool
.find(true, arr
);
st
.bucket(arr
);
SortTool
.find(false, arr
);
}
}
