# 1、快排&冒泡排&选择排&擂台
# AcWing 785. 快速排序
package javatest;
import java.util.Scanner;
public class ACWing {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int len = sc.nextInt();
int[] shuzu = new int[len];
for (int i = 0; i < len; i++) {
shuzu[i] = sc.nextInt();
}
// quickSort(shuzu, len, 0, len - 1);
// maopaoSort(shuzu, len);
// selectSort(shuzu, len);
leitaiSort(shuzu, len);
for (int i = 0; i < shuzu.length; i++) {
System.out.print(shuzu[i] + " ");
}
}
//快速排序
static int[] quickSort(int[] s, int len, int l, int r) {
if (l >= r)
return s;
int flag = s[l];
int p_i = l, p_j = r;
while (p_i < p_j) {
while (p_i < p_j && s[p_j] >= flag) p_j--;
while (p_i < p_j && s[p_i] <= flag) p_i++;
int temp = s[p_i];
s[p_i] = s[p_j];
s[p_j] = temp;
if (p_i >= p_j) {
int temp0 = s[l];
s[l] = s[p_i];
s[p_i] = temp0;
}
}
quickSort(s, len, l, p_i - 1);
quickSort(s, len, p_i + 1, r);
return s;
}
//冒泡排序
static int[] maopaoSort(int[] s, int len) {
for (int i = 0; i < len - 1; i++)
for (int j = 0; j < len - i - 1; j++)
if (s[j] > s[j + 1]) {
int temp = s[j];
s[j] = s[j + 1];
s[j + 1] = temp;
}
return s;
}
//选择排序
static int[] selectSort(int[] s, int len) {
for (int i = 0; i < len - 1; i++)
for (int j = i + 1; j < len; j++)
if (s[j] < s[i]) {
int temp = s[j];
s[j] = s[i];
s[i] = temp;
}
return s;
}
//选择-擂台排序
static int[] leitaiSort(int[] s, int len) {
for (int i = 0; i < len - 1; i++) {
int k = i;
for (int j = i + 1; j < len; j++) if (s[j] < s[k]) k = j;
int temp = s[k];
s[k] = s[i];
s[i] = temp;
}
return s;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82