- it
- 冒泡，选择，希尔，快速排序算法比较
package com
.kkgs
.sort
;
import java
.util
.Arrays
;
public class SortDemo {
public static void bubbleSort(int[] arr
) {
for (int i
= 1; i
< arr
.length
; i
++) {
for (int j
= 0; j
< arr
.length
- i
; j
++) {
if (arr
[j
] > arr
[j
+ 1]) {
int temp
= arr
[j
];
arr
[j
] = arr
[j
+ 1];
arr
[j
+ 1] = temp
;
}
}
}
}
public static void optimizateBubbleSort(int[] arr
) {
boolean flag
= true;
int last_change
= 0;
int border_change
= arr
.length
- 1;
for (int i
= 1; i
< arr
.length
; i
++) {
for (int j
= 0; j
< border_change
; j
++) {
if (arr
[j
] > arr
[j
+ 1]) {
int temp
= arr
[j
];
arr
[j
] = arr
[j
+ 1];
arr
[j
+ 1] = temp
;
flag
= false;
last_change
= j
;
}
}
border_change
= last_change
;
if (flag
) {
break;
}
}
}
public static void selectSort(int[] arr
) {
for (int i
= 0; i
< arr
.length
- 1; i
++) {
int temp
= arr
[i
+ 1];
int index
= i
;
while (index
>= 0 && arr
[index
] > temp
) {
arr
[index
+ 1] = arr
[index
];
index
--;
}
arr
[index
+ 1] = temp
;
}
}
public static void shellSort(int[] arr
, int[] increments
) {
for (int index
= 0; index
< increments
.length
; index
++) {
int incrementCount
= increments
[index
];
for (int increment
= 0; increment
< incrementCount
; increment
++) {
for (int i
= increment
; i
< arr
.length
- incrementCount
; i
+= incrementCount
) {
int temp
= arr
[i
+ incrementCount
];
int j
= i
;
while (j
>= 0 && arr
[j
] > temp
) {
arr
[j
+ incrementCount
] = arr
[j
];
j
-= incrementCount
;
}
arr
[j
+ incrementCount
] = temp
;
}
}
}
}
public static void quickSort(int[] arr
, int low
, int high
) {
int begin
= low
;
int end
= high
;
int temp
= arr
[low
];
while (begin
< end
) {
while (begin
< end
&& arr
[end
] > temp
) {
end
--;
}
if (begin
< end
) {
arr
[begin
] = arr
[end
];
begin
++;
}
while (begin
< end
&& arr
[begin
] < temp
) {
begin
++;
}
if (begin
< end
) {
arr
[end
] = arr
[begin
];
end
--;
}
}
arr
[begin
] = temp
;
if (begin
> 0) {
quickSort(arr
, 0, begin
- 1);
}
if (begin
< high
) {
quickSort(arr
, begin
+ 1, high
);
}
}
public static void main(String
[] args
) {
int[] arr
= { 9999, 123, 45, 12, 4643, 12, 32, 55, 56 };
long startTime
= System
.currentTimeMillis();
bubbleSort(arr
);
long endTime
= System
.currentTimeMillis();
System
.out
.println("冒泡时间差："+(endTime
-startTime
));
long startTime2
= System
.currentTimeMillis();
optimizateBubbleSort(arr
);
long endTime2
= System
.currentTimeMillis();
System
.out
.println("优化后的冒泡排序时间差："+(endTime2
-startTime2
));
long startTime1
= System
.currentTimeMillis();
selectSort(arr
);
long endTime1
= System
.currentTimeMillis();
System
.out
.println("选择排序时间差："+(endTime1
-startTime1
));
long startTime3
= System
.currentTimeMillis();
quickSort(arr
, 0, arr
.length
-1);
int[] increments
= { 4, 1 };
long endTime3
= System
.currentTimeMillis();
System
.out
.println("快速时间差："+(endTime3
-startTime3
));
long startTime4
= System
.currentTimeMillis();
shellSort(arr
, increments
);
long endTime4
= System
.currentTimeMillis();
System
.out
.println("希尔时间差："+(endTime4
-startTime4
));
}
}
