FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/code/lc912.java at master · mJackie/leetcode · GitHub
mJackie
/
leetcode
Public
Notifications
You must be signed in to change notification settings
Fork
135
Star
405
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
code
/
lc912.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
120 lines (116 loc) · 3.42 KB
Breadcrumbs
leetcode
/
code
/
lc912.java
Copy path
File metadata and controls
120 lines (116 loc) · 3.42 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package
code
;
/*
* 912. Sort an Array
* 题意：数组排序
* 难度：Medium
* 分类：
* 思路：
* Tips：注意和lc215区别
* lc215
*/
public
class
lc912
{
public
static
void
main
(
String
[]
args
) {
int
[]
arr
=
sortArray3
(
new
int
[]{
5
,
2
,
3
,
1
});
for
(
int
i
:
arr
){
System
.
out
.
println
(
i
);
}
}
// 快排
public
int
[]
sortArray
(
int
[]
nums
) {
quickSort
(
nums
,
0
,
nums
.
length
-
1
);
return
nums
;
}
public
void
quickSort
(
int
[]
nums
,
int
left
,
int
right
){
if
(
left
>=
right
)
return
;
//注意返回
int
l
=
left
;
int
r
=
right
;
int
pivot
=
nums
[
left
];
while
(
left
<
right
){
while
(
left
<
right
&&
nums
[
right
]>=
pivot
)
right
--;
int
temp
=
nums
[
right
];
nums
[
right
] =
nums
[
left
];
nums
[
left
]=
temp
;
//交换
while
(
left
<
right
&&
nums
[
left
]<
pivot
)
left
++;
temp
=
nums
[
right
];
nums
[
right
] =
nums
[
left
];
nums
[
left
]=
temp
;
}
nums
[
left
] =
pivot
;
quickSort
(
nums
,
left
+
1
,
r
);
quickSort
(
nums
,
l
,
right
-
1
);
}
// 归并
public
static
int
[]
sortArray2
(
int
[]
nums
) {
mergeSort
(
nums
,
0
,
nums
.
length
-
1
);
return
nums
;
}
public
static
void
mergeSort
(
int
[]
nums
,
int
left
,
int
right
){
if
(
left
<
right
) {
int
mid
= (
left
+
right
)/
2
;
mergeSort
(
nums
,
left
,
mid
);
mergeSort
(
nums
,
mid
+
1
,
right
);
merge
(
nums
,
left
,
mid
,
right
);
}
}
public
static
void
merge
(
int
[]
nums
,
int
left
,
int
mid
,
int
right
){
int
[]
temp
=
nums
.
clone
();
//记住这个方法
int
cur
=
left
;
int
pos1
=
left
;
int
pos2
=
mid
+
1
;
while
(
pos1
<=
mid
&&
pos2
<=
right
){
if
(
temp
[
pos1
]<
temp
[
pos2
]) {
//注意是temp 复制后的
nums
[
cur
] =
temp
[
pos1
];
pos1
++;
cur
++;
}
else
{
nums
[
cur
] =
temp
[
pos2
];
pos2
++;
cur
++;
}
}
while
(
pos1
<=
mid
){
nums
[
cur
] =
temp
[
pos1
];
pos1
++;
cur
++;
}
while
(
pos2
<=
right
){
nums
[
cur
] =
temp
[
pos2
];
pos2
++;
cur
++;
}
}
//堆排
public
static
int
[]
sortArray3
(
int
[]
nums
) {
//建堆
int
pos
=
nums
.
length
/
2
;
while
(
pos
>=
0
){
AdjustTree
(
nums
,
nums
.
length
-
1
,
pos
);
pos
--;
}
//排序，每次找出最大的，从堆中去掉，调整堆
int
cur
=
nums
.
length
-
1
;
while
(
cur
>=
0
){
//交换位置
int
temp
=
nums
[
0
];
nums
[
0
] =
nums
[
cur
];
nums
[
cur
] =
temp
;
cur
--;
AdjustTree
(
nums
,
cur
,
0
);
}
return
nums
;
}
public
static
void
AdjustTree
(
int
[]
nums
,
int
len
,
int
pos
){
//调整堆
int
pos_exchange
=
pos
*
2
+
1
;
while
(
pos_exchange
<=
len
){
//left
if
(
pos_exchange
+
1
<=
len
&&
nums
[
pos_exchange
+
1
]>
nums
[
pos_exchange
]){
//比较左右节点，挑出来大的
pos_exchange
+=
1
;
}
if
(
nums
[
pos_exchange
]>
nums
[
pos
]){
//和父节点比较
int
temp
=
nums
[
pos
];
nums
[
pos
] =
nums
[
pos_exchange
];
nums
[
pos_exchange
] =
temp
;
pos
=
pos_exchange
;
pos_exchange
=
pos
*
2
+
1
;
}
else
{
break
;
}
}
}
}
Back
|
FazBrowse Home
|
New Git URL