俩 j 语言 加分号是比较好的写法
golang编码规范
scala编码规范
python Utils.py1
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
57class Utils(object):
def __init__(self, arr):
self.arr = arr
self.arr_len = len(self.arr)
def bubbleSort(self):
for i in range(0, self.arr_len, 1):
for j in range(0, self.arr_len - 1 - i, 1):
if self.arr[j] > self.arr[j+1]:
self.swap(self.arr, j, j+1)
def swap(self, arr, i, j):
arr[i], arr[j] = arr[j], arr[i]
def selectSort(self):
for i in range(0, self.arr_len, 1):
for j in range(i+1, self.arr_len, 1):
if self.arr[i] > self.arr[j]:
self.swap(self.arr, i, j)
def insertSort(self):
for i in range(0, self.arr_len, 1):
for j in range(i, 0, -1):
if self.arr[j] < self.arr[j-1]:
self.swap(self.arr, j-1, j)
def partition(self,low, high):
pivot = arr[low]
while(low < high):
while(low < high and self.arr[high] > pivot):
high -= 1
self.arr[low] = self.arr[high]
while(low < high and self.arr[low] < pivot):
low += 1
self.arr[high] = self.arr[low]
self.arr[low] = pivot
return low
def quickSort(self, low, high):
# low = 0 if not low else low
# high = self.arr_len if not high else high
if(low < high):
pivot = self.partition(low, high)
self.quickSort(low, pivot - 1)
self.quickSort(pivot + 1, high)
if __name__ == '__main__':
arr = [10,9,8,7,6,5,4,3,2,1]
print(arr)
# Utils(arr).bubbleSort()
# Utils(arr).selectSort()
# Utils(arr).insertSort()
Utils(arr).quickSort(0, len(arr) - 1)
print(arr)`
javascript Utils.js1
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// 亦或 交换数组的值
function swap(arr, i, j){
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
// 冒泡排序
function bubbleSort(arr){
for(let i=0; i<arr.length; i++){
for(let j=0; j<arr.length - i -1; j++){
if(arr[j] > arr[j+1]){
swap(arr, j, j+1);
}
}
}
//return arr;
}
// 选择排序
function selectSort(arr){
for(i=0; i<arr.length; i++){
for(j=i+1;j<arr.length;j++){
if(arr[i] > arr[j]){
swap(arr, i, j);
}
}
}
}
// 插入排序
function insertSort(arr){
for(i=0; i<arr.length; i++){
for(j=i; j>0; j--){
if(arr[j] < arr[j-1]){
swap(arr, j, j-1);
}
}
}
}
// 快速排序
function partition(arr, low , high){
let pivot = arr[low];
while(low < high){
while(low < high && arr[high] > pivot){
--high;
}
arr[low] = arr[high];
while(low<high && arr[low] < pivot){
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
function quickSort(arr, low, high){
if(low === undefined && high === undefined){
low = 0;
high = arr.length-1;
}
if(low < high){
let pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
return arr;
}
var arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
console.log(arr);
//bubbleSort(arr)
//selectSort(arr)
//insertSort(arr);
quickSort(arr);
console.log(arr);
java Utils.java 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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
class SortUtils{
private static <T extends Comparable<? super T>> int partition(T[] arr, int low, int high){
// 找到基准值
T pivot = arr[low]; // 把 low 这个坑挖出来了
// low, high 两根 "指针"
while(low < high){
// 从右边开始向左查找是否有比基准值小的值
while(low < high && arr[high].compareTo(pivot) == 1){
--high;
}
// 跳出上面的循环，意味着从右->左, 找到找到了比基准值小的值
arr[low] = arr[high];
// 然后从左往右找是否有比基准值大的值
while(low < high && arr[low].compareTo(pivot) == -1 ){
++low;
}
// 跳出上面的循环，意味着从左->右， 找到了比基准值大的值, 填坑
arr[high] = arr[low];
}
// 最后把 pivot 基准值回填到 low 里
arr[low] = pivot;
// 将此刻基准值的下标 返出去，用于下次快排分区的左右 index +- 1 临界下标
return low;
}
public static <T extends Comparable<? super T>> void quickSort(T[] arr){
quickSort(arr, 0, arr.length-1);
}
private static <T extends Comparable<? super T>> void quickSort(T[] arr, int low, int high){
if(low < high){
// 分区
int pivot = partition(arr, low, high);
// 对分区分别递归快排
// 左分区排序
quickSort(arr, low, pivot-1);
// 右分区排序
quickSort(arr, pivot+1, high);
}
return;
}
public static <T extends Number & Comparable<T>> T[] bubbleSort(T[] arr){
for(int i=0;i<arr.length;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j].compareTo(arr[j+1]) == 1){
T temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}
}
package com.patterns.strategy3;
import java.util.Arrays;
public class Utils {
public static void main(String [] args){
Long [] arrL = {10L,9L, 8L,7L, 6L, 5L, 4L,3L};
System.out.println(Arrays.toString(arrL));
// bubbleSort(arrL);
// selectSort(arrL);
// insertSort((arrL));
shellSort(arrL);
// quickSort(arrL);
System.out.println(Arrays.toString(arrL));
}
public static <T extends Number & Comparable> void swap(T[] arr, int i, int j){
T temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
public static <T extends Number & Comparable<? super T>> T[] bubbleSort(T[] arr){
for(int i=0; i<arr.length; i++){
for(int j=0; j<arr.length -i -1; j++){
if(arr[j].compareTo(arr[j+1]) == 1){
swap(arr, j, j+1);
}
}
}
return arr;
}
public static <T extends Number & Comparable<? super T>> T[] selectSort(T[] arr){
for(int i=0; i<arr.length; i++){
for(int j=i+1; j<arr.length; j++){
if(arr[i].compareTo(arr[j]) == 1){
swap(arr, i, j);
}
}
}
return arr;
}
public static <T extends Number & Comparable<? super T>> T[] insertSort(T[] arr){
for(int i=0; i<arr.length; i++){
for(int j=i; j>0; j--){
if(arr[j].compareTo(arr[j-1]) == -1){
swap(arr, j, j-1);
}
}
}
return arr;
}
// 改进版的 插入排序
public static <T extends Number & Comparable<? super T>> T[] shellSort(T[] arr){
int h = 1;
while(h < arr.length){
h = 3*h + 1;
}
for(int gap=h;gap>0;gap=(gap-1)/3){ // 从 h 开始缩小间隔=》 gap: 1
for(int i=gap; i<arr.length; i++){ // gap , gap+1, gap+2...
for(int j=i; j-gap>=0; j-=gap){
if(arr[j].compareTo(arr[j-gap]) == -1){
swap(arr, j , j-gap);
}
}
}
}
return arr;
}
public static <T extends Number & Comparable<? super T>> int partition(T[] arr, int low, int high){
T pivot = arr[low];
while(low<high){
while(low<high && arr[high].compareTo(pivot) == 1){
--high;
}
arr[low] = arr[high];
while(low < high && arr[low].compareTo(pivot) == -1){
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
// 快速排序
public static <T extends Number & Comparable<? super T>> T[] quickSort(T[] arr){
return quickSort(arr, 0, arr.length - 1);
}
public static <T extends Number & Comparable<? super T>> T[] quickSort(T [] arr, int low, int high){
if(low < high){
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot -1 );
quickSort(arr, pivot + 1, high);
}
return arr;
}
}
*golang Utils.go**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
83package main
import "fmt"
type Utils struct{}
func main(){
var arr = []int{10,9,8,7,6,5,4,3,2,1}
fmt.Printf("arr before sort: %v\n", arr)
var u = Utils{}
//u.BubbleSort(arr)
//u.SelectSort(arr)
//u.InsertSort(arr)
u.QuickSort(arr, 0, len(arr) -1)
fmt.Printf("arr after sort: %v\n", arr)
}
// 冒泡排序
func(u *Utils) BubbleSort(arr []int) []int{
arrLen := len(arr)
for i:=0; i<arrLen;i++{
for j:=0; j<arrLen-i-1; j++{
if arr[j] > arr[j+1]{
swap(arr, j, j+1)
}
}
}
return arr
}
// 选择排序
func(u *Utils)SelectSort(arr []int) []int{
arrLen := len(arr)
for i:=0; i<arrLen; i++{
for j:=i+1; j<arrLen; j++{
if arr[i] > arr[j]{
swap(arr, i, j)
}
}
}
return arr
}
// 插入排序
func(u *Utils)InsertSort(arr []int){
var arrLen = len(arr)
for i:=0; i<arrLen; i++{
for j:=i; j>0; j--{
if arr[j] < arr[j-1]{
swap(arr, j, j-1)
}
}
}
}
//快排 分区 挖坑填坑大法
func partition(arr[] int, low, high int) int{
// 以最左边为基准值
pivot := arr[low]
for ;low<high;{
for low < high && arr[high] > pivot{
high--
}
arr[low] = arr[high]
for low < high && arr[low] < pivot{
low++
}
arr[high] = arr[low]
}
arr[low] = pivot
return low
}
func(u *Utils)QuickSort(arr[] int, low, high int){
if(low < high){
pivot := partition(arr, low, high)
var u = Utils{}
u.QuickSort(arr, low, pivot -1)
u.QuickSort(arr, pivot + 1, high)
}
}
func swap(arr [] int, i, j int){
arr[i], arr[j] = arr[j], arr[i]
}
scala1
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466import Array.range
object Utils{
def main(arg:Array[String]):Unit={
var arr = Array(10,9,8,7,6,5,4,3,2,1)
show(arr)
//selectSort(arr)
//bubbleSort(arr)
//insertSort(arr)
quickSort(arr, 0, arr.length -1)
println()
show(arr)
}
def swap(arr : Array[Int], i:Int, j:Int):Unit={
arr(i) = arr(i) ^ arr(j)
arr(j) = arr(i) ^ arr(j)
arr(i) = arr(i) ^ arr(j)
}
def bubbleSort(arr:Array[Int]){
for(i <- 0 to arr.length-1; j <- 0 until arr.length - i -1){
if(arr(j) > arr(j+1)){
swap(arr, j, j+1)
}
}
}
def selectSort(arr:Array[Int]):Unit={
var arrLen = arr.length
for(i <- range(0, arrLen, 1)){
for(j <- range(i+1, arrLen, 1)){
if(arr(i) > arr(j)){
swap(arr, i, j)
}
}
}
}
def insertSort(arr:Array[Int]){
for(i <- 0 to (arr.length -1); j <- range(i, 0, -1)){
if(arr(j) < arr(j-1)){
swap(arr, j, j-1)
}
}
}
// 快速排序
def partition(arr: Array[Int], low:Int, high:Int):Int={
var pivot = arr(low)
var left = low
var right = high
while(left < right){
while(left < right && arr(right) > pivot){
right=right-1
}
arr(left) = arr(right)
while(left < right && arr(left) < pivot){
left=left+1
}
arr(right) = arr(left)
}
arr(left) = pivot
return left
}
def quickSort(arr:Array[Int], low:Int, high:Int){
if(low < high){
var pivot = partition(arr, low, high)
quickSort(arr, low, pivot - 1)
quickSort(arr, pivot+1, high)
}
}
def show(arr : Array[Int]){
for(x <- arr){
print(x+",")
}
}
}
package com.ghc.algorithm
object Sorter extends App {
implicit val prefix = "排序算法："
val arr:Array[Int] = (10 to 1 by -1).toArray
def bubbleSort(arr:Array[Int], name:String="冒泡排序"): Unit ={
println(s"$prefix $name 开始了...")
for(i <- 0 until arr.length; j<-0 until arr.length-i-1){
if(arr(j) > arr(j+1)){
swap(arr, j, j+1)
}
}
println(s"$prefix $name 结束了...")
}
def selectSort(arr:Array[Int], name:String="选择排序"): Unit ={
println(s"$prefix $name 开始了...")
for(i <- 0 to arr.length -2; j<- i+1 to arr.length-1){
if(arr(i) > arr(j)) swap(arr, i, j)
}
println(s"$prefix $name 结束了...")
}
/**
* 堆排序, 构建大顶堆，然后交换首尾下标 对应的值
* @param arr
* @param name
*/
def heapSort(arr:Array[Int], name:String="改进版选择排序 => 堆排序"):Unit={
println(s"$prefix $name 开始了...")
for(dynamicMaxLength<-arr.length to 2 by -1){
heapify(arr, dynamicMaxLength)
swap(arr, 0, dynamicMaxLength-1)
}
println(s"$prefix $name 结束了...")
}
/**
* 功能单一，仅为构建大顶堆
* @param arr
* @param dynamicMaxLength
*/
def heapify(arr:Array[Int], dynamicMaxLength:Int): Unit ={
// 从最后 最右 一个非叶子节点 开始构建大顶堆或者小顶堆
for(p <- (dynamicMaxLength/2 - 1) to 0 by -1){
// 如果 p 存在右子节点
if((2 * p + 2) < dynamicMaxLength){
if(arr(2*p+1) < arr(2*p+2)) swap(arr, 2*p+1, 2*p+2)
}
if(arr(2*p+1) > arr(p)) swap(arr, p, 2*p+1)
}
}
def insertSort(arr:Array[Int], name:String="插入排序"):Unit ={
println(s"$prefix $name 开始了...")
for(i<- 0 to arr.length-1;j<-i to 1 by -1){
if(arr(j) < arr(j-1)) swap(arr, j, j-1)
}
println(s"$prefix $name 结束了...")
}
/**
* 改进版的插入排序， gap 由大到小, 3*h+1 的公式
* @param arr
* @param name
*/
def shellSort(arr:Array[Int], name:String="改进版插入排序 => 希尔排序"):Unit={
println(s"$prefix $name 开始了...")
var h = 1
while(h<=arr.length/3){
h = h*3 + 1
}
var gap = h
while(gap >= 1){
for(i <- gap to arr.length-1; j<- i to gap by -gap){
if(arr(j) < arr(j-gap))
swap(arr, j, j-gap)
}
gap = (gap-1)/3
}
println(s"$prefix $name 结束了...")
}
def quickSort(arr:Array[Int], name:String="快速排序"): Unit ={
println(s"$prefix $name 开始了...")
quickSort(arr, 0, arr.length-1)
println(s"$prefix $name 结束了...")
}
def quickSort(arr:Array[Int], left:Int, right:Int): Unit ={
if(left < right) {
val pivot = partition(arr, left, right)
quickSort(arr, left, pivot-1)
quickSort(arr, pivot+1, right)
}
}
def partition(arr:Array[Int], low:Int, high:Int): Int ={
val pivot = arr(low)
var left = low
var right = high
while(left < right){
while(left < right && arr(right) > pivot){
right -= 1
}
arr(left) = arr(right)
while(left < right && arr(left) < pivot){
left += 1
}
arr(right) = arr(left)
}
arr(left) = pivot
left
}
def mergeSort(arr:Array[Int], name:String="归并排序"): Unit ={
println(s"$prefix $name 开始了...")
mergeSort(arr, 0, arr.length-1)
println(s"$prefix $name 结束了...")
}
/**
* 原理是 左右两边先有序，然后合并， 快排则是 找中分轴然后分治
* @param arr
* @param left
* @param right
*/
def mergeSort(arr:Array[Int], left:Int, right:Int): Unit ={
if(left < right){
val mid = left + ((right - left) /2)
mergeSort(arr, left, mid)
mergeSort(arr, mid+1, right)
merge(arr, left, mid+1, right)
}
}
def merge(arr:Array[Int], left:Int, right:Int, rightBounds:Int): Unit ={
var i = left
var j = right
val mid = right-1
var k = 0
// println(s"$left |$mid| $rightBounds")
var count = (rightBounds - left +1)
// print(s"count: $count")
val temp:Array[Int] = new Array[Int](count)
while (i <= mid && j <= rightBounds) {
// println(s"${arr(i)} <= ${arr(j)} : ${arr(i) <= arr(j)}")
arr(i) <= arr(j) match {
case true => {
temp(k) = arr(i)
k += 1
i += 1
}
case false => {
temp(k) = arr(j)
k += 1
j += 1
}
}
}
while (i <= mid) {
temp(k) = arr(i)
k += 1
i += 1
}
while (j <= rightBounds) {
temp(k) = arr(j)
k += 1
j += 1
}
for (m <- 0 to temp.length - 1) {
arr(left + m) = temp(m)
}
}
def countSort(arr:Array[Int], name:String="计数排序 --》 感觉好傻的亚子"): Unit ={
println(s"$prefix $name 开始了...")
val count = new Array[Int](arr.max+1)
val result = new Array[Int](arr.length)
for(i <- 0 to arr.length-1){
count(arr(i))+=1
}
var m = 0
for(j <- 0 to count.length-1){
if(count(j) > 0){
for(k <- count(j) until 0 by -1){
result(m) = j
m+=1
}
}
}
for(i <- 0 to arr.length-1){
arr(i) = result(i)
}
println(s"$prefix $name 结束了...")
}
def swap(arr:Array[Int], i:Int, j:Int): Unit ={
arr(i) = arr(i) ^ arr(j)
arr(j) = arr(i) ^ arr(j)
arr(i) = arr(i) ^ arr(j)
}
def showArr(arr:Array[Int]):Unit={
println(arr.mkString("<",",",">"))
}
showArr(arr)
bubbleSort(arr)
selectSort(arr)
insertSort(arr)
shellSort(arr)
quickSort(arr)
heapSort(arr)
mergeSort(arr)
countSort(arr)
showArr(arr)
}
import Array.range
object Demo{
def main(args:Array[String]):Unit={
for(i <- range(1,10,1)){
println(i+"! = "+factorial2(n=i))
}
printLangs("golang", "java", "python", "scala")
val result = apply(layout, 10)
println(result)
println(inc(7)-1)
println("1+3 = "+add(1)(3))
}
// 可变参数
def printLangs(langs:String*):Unit={
for(lang <- langs){
println(lang);
}
}
// 函数递归
def factorial(n:BigInt, prod:BigInt=1):BigInt={
if(n<1){
return prod
}
return factorial(n-1, n*prod)
}
// 函数嵌套 阶乘
def factorial2(n:BigInt):BigInt = {
def fact(n:BigInt, accumulator:BigInt):BigInt={
if(n<=1) return accumulator
return fact(n-1, n*accumulator)
}
return fact(n, 1)
}
// 高阶函数
def apply(f: Int => String, v:Int) = f(v)
def layout(n:Int):String = {
return "["+n+"]"
}
// 匿名函数
var inc = (x:Int) => x+1
// 柯里化
def add(x:Int) = (y:Int) => x+y
}
import scala.util.control.Breaks
object Test {
def main(args: Array[String]):Unit={
var arr = Array(10,9,7,5,4,3,2,1)
show(arr)
println()
// bubbleSort(arr)
// selectSort(arr)
// insertSort(arr)
// quickSort(arr)
shellSort(arr)
show(arr)
}
def show:Array[Int] => Unit = (arr) =>{
for(e <- arr){
print(e+",")
}
}
val swap:(Array[Int], Int, Int) => Unit = (arr, i, j) =>{
arr(i) = arr(i) ^ arr(j)
arr(j) = arr(i) ^ arr(j)
arr(i) = arr(i) ^ arr(j)
}
def bubbleSort(ints: Array[Int]):Unit={
var arrLen = ints.length;
for(i <- 0 until arrLen; j <- 0 until (arrLen -i -1)){
if(ints(j) > ints(j+1)){
swap(ints, j, j+1)
}
}
}
def selectSort(arr:Array[Int]):Unit={
for(i <- 0 to arr.length-1; j <- i to arr.length-1){
if(arr(i) > arr(j)){
swap(arr, i, j)
}
}
}
def insertSort(arr:Array[Int]):Unit={
for(i <- 0 until arr.length; j<- Range(i, 0, -1)){
if(arr(j-1) > arr(j)){
swap(arr, j, j-1)
}
}
}
def shellSort(arr:Array[Int]):Unit={
var h = 1
while(h < arr.length/3){
h = h*3 + 1
}
var gap = h
var loop = new Breaks
while(gap > 0){
// loop.breakable(
// if(gap == 0) {
// gap = 1
for(i <- Range(gap, arr.length, 1); j<- Range(i, gap-1, -gap)){
if(arr(j) < arr(j-gap)){
swap(arr, j, j-gap)
}
}
// loop.break()
// }
// )
// show(arr)
// println("gap: "+gap)
gap = (gap -1)/3
}
}
def partition(arr:Array[Int], low:Int, high:Int):Int ={
var left = low
var right = high
var pivot = arr(left)
while(left < right){
while(left < high && arr(right) > pivot){
right -= 1
}
arr(left) = arr(right)
while(left<high && arr(left) < pivot){
left += 1
}
arr(right) = arr(left)
}
arr(left) = pivot
left
}
def quickSort(ints: Array[Int]): Unit ={
quickSort(ints, 0, ints.length -1)
}
def quickSort(arr:Array[Int], low:Int, high:Int): Unit ={
if(low < high){
val pivot = partition(arr, low, high)
quickSort(arr, low, pivot -1)
quickSort(arr, pivot +1, high)
}
}
}
无力吐槽的 shell 正常人谁这么干呐
1 | #!/bin/sh |
1 | # 结尾， python 最好不写分号 |
提升 shell 颜值
1 | #!/bin/bash |
java 改进版本
1 | package com.ghc.utils; |