目录
一、冒泡排序二、选择排序三、插入排序四、希尔排序五、桶排序
一、冒泡排序
相邻位置比较
public class Sort {
public static void main(String
[] args
){
Random rand
= new Random();
int[] arr
= new int[10];
for (int i
=0; i
< arr
.length
; i
++) {
arr
[i
] = rand
.nextInt(100)+1;
System
.out
.print(arr
[i
]+"\t");
}
System
.out
.println();
for (int i
= 0,t
; i
< arr
.length
-1; i
++) {
for (int j
= i
+1; j
< arr
.length
; j
++) {
if (arr
[i
] > arr
[j
]){
t
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = t
;
}
}
}
for (int c
: arr
) {
System
.out
.print(c
+"\t");
}
}
}
二、选择排序
一轮比较只换一次位置
public class Sort {
public static void main(String
[] args
){
Random rand
= new Random();
int[] arr
= new int[10];
for (int i
=0; i
< arr
.length
; i
++) {
arr
[i
] = rand
.nextInt(100)+1;
System
.out
.print(arr
[i
]+"\t");
}
System
.out
.println();
for (int maxIx
= arr
.length
-1,maxValIx
,t
; maxIx
>= 0; maxIx
--) {
maxValIx
= 0;
for (int j
= 1; j
<= maxIx
; j
++) {
if (arr
[maxValIx
] < arr
[j
]){
maxValIx
= j
;
}
}
if (maxValIx
!=maxIx
){
t
= arr
[maxIx
];
arr
[maxIx
] = arr
[maxValIx
];
arr
[maxValIx
] = t
;
}
}
for (int i
= 0,minIx
,minValIx
,t
; i
< arr
.length
-1; i
++) {
minIx
= i
;
minValIx
= i
;
for (int j
= i
+1; j
< arr
.length
; j
++) {
if (arr
[minValIx
] > arr
[j
]){
minValIx
= j
;
}
}
if (minIx
!= minValIx
){
t
= arr
[minIx
];
arr
[minIx
] = arr
[minValIx
];
arr
[minValIx
] = t
;
}
}
for (int c
: arr
) {
System
.out
.print(c
+"\t");
}
}
}
三、插入排序
先存值，比较后再插入
相对有序程度较高时更有效
public class Sort {
public static void main(String
[] args
){
Random rand
= new Random();
int[] arr
= new int[10];
for (int i
=0; i
< arr
.length
; i
++) {
arr
[i
] = rand
.nextInt(100)+1;
System
.out
.print(arr
[i
]+"\t");
}
System
.out
.println();
for (int i
= 1,j
,t
; 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
;
}
for (int c
: arr
) {
System
.out
.print(c
+"\t");
}
}
}
四、希尔排序
使相对有序程度更高
public class Sort {
public static void main(String
[] args
){
Random rand
= new Random();
int[] arr
= new int[10];
for (int i
=0; i
< arr
.length
; i
++) {
arr
[i
] = rand
.nextInt(100)+1;
System
.out
.print(arr
[i
]+"\t");
}
System
.out
.println();
for (int step
= arr
.length
/2; step
>= 2 ; step
/= 2) {
for (int i
= 0,t
; step
+i
< arr
.length
&& arr
[i
]>arr
[i
+step
]; i
++) {
t
= arr
[i
];
arr
[i
] = arr
[i
+step
];
arr
[i
+step
] = t
;
}
}
for (int i
= 1,j
,t
; 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
;
}
for (int c
: arr
) {
System
.out
.print(c
+"\t");
}
}
}
五、桶排序
二维数组
public class Sort {
public static void main(String
[] args
){
Random rand
= new Random();
int[] arr
= new int[10];
for (int i
=0; i
< arr
.length
; i
++) {
arr
[i
] = rand
.nextInt(100)+1;
System
.out
.print(arr
[i
]+"\t");
}
System
.out
.println();
final int U
= 10;
int[][] bucket
= new int[U
][arr
.length
];
int[] ixs
= new int[U
];
for (int i
= 1,count
,t
;; i
*=10) {
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
];
}
}
Arrays
.fill(ixs
,0);
}
for (int c
: arr
) {
System
.out
.print(c
+"\t");
}
}
}
