-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBubbleSort.kt
More file actions
75 lines (67 loc) · 1.85 KB
/
BubbleSort.kt
File metadata and controls
75 lines (67 loc) · 1.85 KB
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
package sort
/*
冒泡排序
比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
*/
/*
分类:内部比较排序
数据结构:数组
最差时间复杂度:O(n^2)
最优时间复杂度:O(n)
平均时间复杂度:O(n^2)
所需辅助空间:O(1)
稳定性:稳定
*/
fun bubbleSort(a: IntArray,n: Int){
for(i in 0 until n-1){
for (j in 0 until n-1-i){
if (a[j]>a[j+1]){ //如果条件改成a[j] >= a[j+1]，则变为不稳定算法
swap(a,j,j+1)
}
}
}
}
/*
冒泡改进-鸡尾酒排序
分类:内部比较排序
数据结构:数组
最差时间复杂度:O(n^2)
最优时间复杂度:O(n)
平均时间复杂度:O(n^2)
所需辅助空间:O(1)
稳定性:稳定
*/
fun cocktailSort(a: IntArray,n: Int){
//初始化边界
var left: Int = 0
var right: Int = n - 1
while (left < right){
//前半轮，将最大元素放到后面
for (i in left until right){
if (a[i] > a[i+1]){
swap(a,i,i+1)
}
}
right--
//后半轮，将最小元素放到前面
for (i in right downTo left+1 ){
if (a[i-1] > a[i]){
swap(a,i-1,i)
}
}
left++
}
}
fun main(args: Array<String>) {
val array: IntArray = intArrayOf(5,7,3,9,3,2,0,1,6)
val n: Int = array.size
bubbleSort(array,n)
// cocktailSort(array,n)
println("冒泡排序结果:")
for (i in 0 until n){
print(array[i].toString() + ",")
}
}