数据结构-排序

概述

image

排序的定义:

将一组杂乱无章的数据按一定规律顺次排列起来。

排序的目的:

便于查找!

内部排序和外部排序

  • 若待排序记录都在内存中,称为内部排序;
  • 若待排序记录一部分在内存,一部分在外存,则称为外部排序。

  • [ ] 注意:外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要复杂得多。

衡量标准

  • 时间效率——排序速度(比较次数与移动次数)
  • 空间效率——占内存辅助空间的大小
  • 稳定性——A和B的关键字相等,排序后A、B的先后次序保持不变,则称这种排序算法是稳定的。

分类

插入排序

直接插入排序

算法描述

 一般的排序过程:整个排序过程为n-1趟插入,即先将序列中第1个记录看成是一个有序子序列,然后从第2个记录开始,逐个进行插入,直至整个序列有序。

下文实现一个和一般的不同的算法

算法实现

为了便于理解,把比较的过程也打印了出来

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
 /*
插入排序:
此实现的算法与上文中所说有差异,是修改版的
不需要和前面的进行交换

思路:
1 从 数组中的第二个元素开始
2 和第一个元素进行比较 如果满足排序条件sortBy:(T,T) -> Bool)
3 则把第一个元素向后移一位 然后把第二个元素放在第一个位置上
4 如果是第三次插入则要和前面的两个进行比较 是否需要移动
5 依此类推
总结:此算法整个过程就是找一个合适的位置进行插入

*/

/// 插入排序
///
/// - Parameters:
/// - contents: 要排序的内容
/// - sortBy: 排序的条件
/// - Returns: <#return value description#>
func insertSort<T>(_ contents: [T], sortBy:(T,T) -> Bool) ->[T] {

guard contents.count > 1 else {
return contents
}

var cntnts = contents

for i in 1..<cntnts.count { //从第二个元素开始 因为第一个元素是有序的
print("--------第\(i)趟--------")
var j = i
let temp = cntnts[j]//保存当前的值
print("第\(i - j)次 是否需要移动 ?")
while j > 0 && sortBy(temp,cntnts[j-1]) {//当前的值与其前一个值做比较
print("+++第\(i - j)次 需要移动+++")
print("+++第\(i - j)次 \(cntnts[j-1])向后移动到\(cntnts[j])的位置+++")
cntnts[j] = cntnts[j-1] // 向后移动一位
j -= 1
}
print("**第\(i - j)次 不需要移动**")
print("+++\(temp)放到\(cntnts[j])的位置+++")
cntnts[j] = temp
print(cntnts)
}
return cntnts
}


使用:
var nums = [11,3,27,8,9]

nums = insertSort(nums, sortBy: { (n1, n2) -> Bool in
return n1 < n2
})

print(nums)

结果:

原始数组:
[11, 3, 27, 8, 9]
--------第1趟--------
第0次 是否需要移动 ?
+++第0次 需要移动+++
+++第0次 11向后移动到3的位置+++
**第1次 不需要移动**
+++3放到11的位置+++
[3, 11, 27, 8, 9]
--------第2趟--------
第0次 是否需要移动 ?
**第0次 不需要移动**
+++27放到27的位置+++
[3, 11, 27, 8, 9]
--------第3趟--------
第0次 是否需要移动 ?
+++第0次 需要移动+++
+++第0次 27向后移动到8的位置+++
+++第1次 需要移动+++
+++第1次 11向后移动到27的位置+++
**第2次 不需要移动**
+++8放到11的位置+++
[3, 8, 11, 27, 9]
--------第4趟--------
第0次 是否需要移动 ?
+++第0次 需要移动+++
+++第0次 27向后移动到9的位置+++
+++第1次 需要移动+++
+++第1次 11向后移动到27的位置+++
**第2次 不需要移动**
+++9放到11的位置+++
[3, 8, 9, 11, 27]
[3, 8, 9, 11, 27]

比较字符串也是可以的:

var strs = ["11","3","27","8","9"]

strs = insertSort(strs, sortBy: { (s1, s2) -> Bool in
return s1.compare(s2) == .orderedAscending
})


print(strs)

结果:

["11", "27", "3", "8", "9"]
算法分析
  • 设对象个数为n,则执行n-1趟
  • 比较次数和移动次数与初始排列有关

    1. 最好情况下:
       每趟只需比较 1 次,不移动
       总比较次数为 n-1
  1. 最坏情况下:第 i 趟比较i次,移动i+1次

若出现各种可能排列的概率相同,则可取最好情况和最坏情况的平均情况
平均情况比较次数和移动次数为n^2/4

结果:

  • 时间复杂度为 o(n^2)
  • 空间复杂度为 o(1)
  • 是一种稳定的排序方法

折半插入排序

折半插入排序(Binary Insertion Sort)是一种插入排序算法,通过不断地将数据元素插入到合适的位置进行排序,在寻找插入点时采用了折半查找

算法实现

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

/*
折半(二分)插入排序:

直接插入排序相当于在已经排好序的数组部分逐个比较 找到合适的插入位置,在查找插入的位置时从第一个到最后一个,因为已经插入的内容是有序的,所有很多冗余的比较。即如果插入的比最后一个还大(还小),则仍然会从第一个比较到最后一个
折半插入排序是直接插入排序的优化版
优化:
由于直接插入排序是在查找插入位置的时候比较浪费时间,所以折半插入排序就优化查找。
由于在逐渐插入的时候已经插入部分是有序的,查找插入位置其实就是在已经排好序的数组中找到一个位置,这时二分查找算法正好适合。



*/


/// 寻找要插入的位置
///
/// - Parameters:
/// - contents: <#contents description#>
/// - value: <#value description#>
/// - low: <#low description#>
/// - high: <#high description#>
/// - Returns: <#return value description#>
func binarySearchLocation<T:Comparable>(_ contents: inout [T],_ value:T ,_ low:Int,_ high:Int) ->Int {
if high <= low {
return (value > contents[low]) ? (low + 1): low
}
print("开始查找")
let midIdx = low + (high - low ) / 2
print("----当前已排好序的数组内容部分的中间位置是:第\(midIdx)个")
if value == contents[midIdx] {
return midIdx + 1
}
if value > contents[midIdx]{//binarySearchLocation(&contents, value, midIdx+1, high)
print("-----从右边找")
return binarySearchLocation(&contents, value, midIdx+1, high)
}
if value < contents[midIdx]{//binarySearchLocation(&contents, value, low, midIdx - 1)
print("-----从左边找")
return binarySearchLocation(&contents, value, low, midIdx - 1)
}
return 0
}



func binaryInsertSort<T:Comparable>(_ contents:inout [T]) -> [T] {
var j = 0
for i in 1..<contents.count {
print("\n\n***********第\(i)次***********\n")
j = i - 1
let temp = contents[i] // 开始插入temp
print("要插入的是\(temp)")//binarySearchLocation(&contents, temp, 0, j)
let location = binarySearchLocation(&contents, temp, 0, j) //找到temp应该插入的位置
print("-----找到了:第\(location)个合适")
while j >= location {
print("--------第\(j)个向后移动到第\(j+1)个")
contents[j+1] = contents[j]
j -= 1
}
print("结果:\n+++++ 把\(temp)放到第\(j+1)个位置 +++++")
contents[j+1] = temp
print("当前的排序结果是: \(contents[0...i])")
}

return contents
}

var arr = [1,33,0,2,4,44,3]

arr = binaryInsertSort(&arr)
print("\n--------最终结果是---------\n\(arr)")


排序过程和结果:

***********第1次***********

要插入的是33
-----找到了:第1个合适
结果:
+++++ 把33放到第1个位置 +++++
当前的排序结果是: [1, 33]


***********第2次***********

要插入的是0
开始查找
----当前已排好序的数组内容部分的中间位置是:第0个
-----从左边找
-----找到了:第0个合适
--------第1个向后移动到第2个
--------第0个向后移动到第1个
结果:
+++++ 把0放到第0个位置 +++++
当前的排序结果是: [0, 1, 33]


***********第3次***********

要插入的是2
开始查找
----当前已排好序的数组内容部分的中间位置是:第1个
-----从右边找
-----找到了:第2个合适
--------第2个向后移动到第3个
结果:
+++++ 把2放到第2个位置 +++++
当前的排序结果是: [0, 1, 2, 33]


***********第4次***********

要插入的是4
开始查找
----当前已排好序的数组内容部分的中间位置是:第1个
-----从右边找
开始查找
----当前已排好序的数组内容部分的中间位置是:第2个
-----从右边找
-----找到了:第3个合适
--------第3个向后移动到第4个
结果:
+++++ 把4放到第3个位置 +++++
当前的排序结果是: [0, 1, 2, 4, 33]


***********第5次***********

要插入的是44
开始查找
----当前已排好序的数组内容部分的中间位置是:第2个
-----从右边找
开始查找
----当前已排好序的数组内容部分的中间位置是:第3个
-----从右边找
-----找到了:第5个合适
结果:
+++++ 把44放到第5个位置 +++++
当前的排序结果是: [0, 1, 2, 4, 33, 44]


***********第6次***********

要插入的是3
开始查找
----当前已排好序的数组内容部分的中间位置是:第2个
-----从右边找
开始查找
----当前已排好序的数组内容部分的中间位置是:第4个
-----从左边找
-----找到了:第3个合适
--------第5个向后移动到第6个
--------第4个向后移动到第5个
--------第3个向后移动到第4个
结果:
+++++ 把3放到第3个位置 +++++
当前的排序结果是: [0, 1, 2, 3, 4, 33, 44]

--------最终结果是---------
[0, 1, 2, 3, 4, 33, 44]

算法分析

  • 折半查找比顺序查找快,所以折半插入排序就平均性能来说比直接插入排序要快
  • 它所需要的关键码比较次数与待排序对象序列的初始排列无关,仅依赖于对象个数。在插入第 i 个对象时,需要经过 log2i +1 次关键码比较,才能确定它应插入的位置

  • 当 n 较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差

  • 在对象的初始排列已经按关键码排好序或接近有序时,直接插入排序比折半插入排序执行的关键码比较次数要少
  • 折半插入排序的对象移动次数与直接插入排序相同,依赖于对象的初始排列

总结:

相比较直接插入排序而言

  1. 减少了比较次数,但没有减少移动次数
  2. 平均性能优于直接插入排序
  • 时间复杂度为 o(n2)
  • 空间复杂度为 o(1)
  • 是一种稳定的排序方法

希尔排序

希尔排序的出发点是:
  • 直接插入排序在基本有序时,效率较高
  • 在待排序的记录个数较少时,效率较高
基本思想

 先将整个待排记录序列分割成若干子序列,分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

分段方法

 子序列的构成不是简单地“逐段分割”
将相隔某个增量dk的记录组成一个子序列
让增量dk逐趟缩短(例如依次取5,3,1)
直到dk=1为止。

优点

 小元素跳跃式前移
最后一趟增量为1时,序列已基本有序
平均性能优于直接插入排序

排序过程

例:关键字序列 T=(49,38,65,97, 76, 13, 27, 49*,55, 04)

  • dk 值较大,子序列中对象较少,速度较快;
  • dk 值逐渐变小,子序列中对象变多,但大多数对象已基本有序,所以排序速度仍然很快。
算法实现
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
func insertionSort<T:Comparable>(_ list: inout [T],sortBy:(T,T) -> Bool, start: Int, dk: Int) {
for i in stride(from: (start + dk), to: list.count, by: dk) {
let currentValue = list[i]
var loc = i
while loc >= dk && sortBy(list[loc - dk] ,currentValue){
print("\(list[loc - dk]) 向后移动\(dk)位")
list[loc] = list[loc - dk]
loc -= dk
print("list: \(list)")
}
list[loc] = currentValue
}
}


func shellSort<T:Comparable>(_ contents: inout [T], sortBy:(T,T) -> Bool) {
var sublistCount = contents.count / 2

while sublistCount > 0 {
print("---- dk= \(sublistCount) -----")
for loc in 0..<sublistCount {
print(" loc = \(loc)")
insertionSort(&contents, sortBy: sortBy, start: loc, dk: sublistCount)
}
print("移动结果:\(contents)")
sublistCount = sublistCount / 2
}

}


var arr = [33,2,12,34,21]

print("原始数组是:\n\(arr)\n")
shellSort(&arr) { (v1, v2) -> Bool in
return v1 > v2
}

print("最终结果:\n\(arr)\n")




结果:


原始数组是:
[33, 2, 12, 34, 21]

---- dk= 2 -----
loc = 0
33 向后移动2位
list: [33, 2, 33, 34, 21]
33 向后移动2位
list: [12, 2, 33, 34, 33]
loc = 1
移动结果:[12, 2, 21, 34, 33]
---- dk= 1 -----
loc = 0
12 向后移动1位
list: [12, 12, 21, 34, 33]
34 向后移动1位
list: [2, 12, 21, 34, 34]
移动结果:[2, 12, 21, 33, 34]
最终结果:
[2, 12, 21, 33, 34]
算法分析
  • 时间复杂度是n和d的函数:

    O(n^1.25)~ O(1.6n^1.25)—经验公式

  • 空间复杂度为 o(1)

  • 是一种不稳定的排序方法

交换排序

冒泡排序

基本思想

每趟不断将记录两两比较,并按“前小后大” 规则交换

1
2
3
4
5
6
21,25,49, 25*,16,  08
21,25,25*,16, 08 , 49
21,25, 16, 08 ,25*,49
21,16, 08 ,25, 25*,49
16,08 ,21, 25, 25*,49
08,16, 21, 25, 25*,49
优点

每趟结束时,不仅能挤出一个最大值到最后面位置,还能同时部分理顺其他元素;
一旦下趟没有交换,还可提前结束排序

实现
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

/*
使用泛型 需要外界传入是升序还是降序也就是 比较的规则 这样写的好处是
这个排序方法任何容器中装的任何类型都可以使用 比如 Int ,String ,甚至是你自定义的 model 根据你model任意一个字段 作比较都是可以的

*/

/// 冒泡排序
///
/// - Parameters:
/// - contents: 要比较的内容
/// - sortBy: 排序规则
/// - Returns: 返回排好序的内容
func bubbleSort<T>(_ contents: inout [T],_ sortBy:(T,T)->Bool)->[T] {
guard contents.count > 1 else {
return contents
}
let n = contents.count
for i in 0..<n {
for j in 0..<(n - 1 - i) {
if sortBy(contents[j],contents[j+1]){
contents.swapAt(j, j + 1)
}
}
}
return contents
}

使用:

var nums = [11,3,27,8,9]
nums = bubbleSort(&nums, { (n1, n2) -> Bool in
return n1 > n2
})

print(nums)
结果:
[3, 8, 9, 11, 27]

var strs = ["11","3","27","8","9"]
strs = bubbleSort(&strs, { (n1, n2) -> Bool in
return n1.compare(n2) == .orderedAscending
})

print(strs)
结果:

["9", "8", "3", "27", "11"]
算法分析
  • 时间复杂度为 o(n^2)
  • 空间复杂度为 o(1)
  • 是一种稳定的排序方法

快速排序

图片来源于网络

基本思想:
  • 任取一个元素 (如第一个) 为中心
  • 所有比它小的元素一律前放,比它大的元素一律后放,形成左右两个子表;
  • 对各子表重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个

①每一趟的子表的形成是采用从两头向中间交替式逼近法;

②由于每趟中对各子表的操作都相似,可采用递归算法。

实现
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
 /*
快速排序
*/
func quicklySort<T: Comparable>(_ contents:inout [T], low: Int, high: Int) {
var i = low
var j = high
guard low < high,low >= 0,high < contents.count else {
return
}
let piv = (low + (high - low) / 2)//标志位
let lowValue = contents[piv] //

/*
一个循环的流程


从高位(右边)开始:
1 循环判断 当前高位的值是否大于标志位值 如果大于 则再向前一位比较 一直找到小于标志位的index
2 高位找到比标志位的值小的index 之后 停止开始从低位(左边)开始

低位开始 :

1 循环判断 当前低位的值是否小于标志位 如果小于标志位则index + 1 进行下一位比较,直到找到比标志位大的值
2 低位找到比标志位大的值之后停止

交换:

从低位和高位找到了 比标志位大的值和比标志位小的值 然后这两个值交换

当i >= j 即低位的index >= 高位的index时 停止这一轮的循环

*/

print("\n标志位")
print(lowValue)

while i < j {
while contents[j] > lowValue {
j -= 1//高位的 index - 1
}
while contents[i] < lowValue {
i += 1
}
if i <= j {
contents.swapAt(i, j)
print("contenti-->\(contents[i])" + "和" + " contentj-->\(contents[j])" + "交换")
/*
交换完成后 i 向下一步
j 向前一步
*/
i += 1
j -= 1
}
}
print("本轮排序结果:\n\(contents)")
print("\n----------下一轮分割线--------------")
print("low = \(low),high = \(high), i = \(i),j = \(j)")
if low < j {
print("\n----------左边--------------")
quicklySort(&contents, low: low, high: j)
}
if i < high {
print("\n----------右边--------------")
quicklySort(&contents, low: i, high: high)
}
}


var arr2 = [7,32,2,1,5]
print("初始化数组")
print(arr2)
quicklySort(&arr2, low: 0, high: arr2.count - 1)


结果:


初始化数组
[7, 32, 2, 1, 5]

标志位
2
contenti-->1和 contentj-->7交换
contenti-->2和 contentj-->32交换
本轮排序结果:
[1, 2, 32, 7, 5]

----------下一轮分割线--------------
low = 0,high = 4, i = 2,j = 1

----------左边--------------

标志位
1
contenti-->1和 contentj-->1交换
本轮排序结果:
[1, 2, 32, 7, 5]

----------下一轮分割线--------------
low = 0,high = 1, i = 1,j = -1

----------右边--------------

标志位
7
contenti-->5和 contentj-->32交换
本轮排序结果:
[1, 2, 5, 7, 32]

----------下一轮分割线--------------
low = 2,high = 4, i = 3,j = 3

----------左边--------------

标志位
5
contenti-->5和 contentj-->5交换
本轮排序结果:
[1, 2, 5, 7, 32]

----------下一轮分割线--------------
low = 2,high = 3, i = 3,j = 1

----------右边--------------

标志位
7
contenti-->7和 contentj-->7交换
本轮排序结果:
[1, 2, 5, 7, 32]

----------下一轮分割线--------------
low = 3,high = 4, i = 4,j = 2
算法分析
  • 时间效率:O(nlog2n) —每趟确定的元素呈指数增加
  • 空间效率:O(log2n)—递归要用到栈空间
  • 稳 定 性: 不稳定 —可选任一元素为支点。

选择排序

简单选择排序

基本思想

 每一趟在后面 n-i +1个中选出关键码最小的对象, 作为有序序列的第 i 个记录

实现
算法分析
  • 时间复杂度:O(n²)
  • 空间复杂度:O(1)
  • 不稳定

堆排序

基本思想
  • (1)将序列r[1..n] 建初堆,交换r[1]和r[n],则r[n]为关键字最大的记录。
  • (2)将r[1..n-1]重新调整为堆,交换r[1]和r[n-1] ,则r[n-1]为关键字次大的记录。
  • (3)循环n-1次,直到交换了r[1]和r[2]为止,得到了一个非递减的有序序列r[1..n]。
算法分析
  • 时间效率:O(nlog2n)
  • 空间效率:O(1)
  • 稳 定 性:不稳定

==适用于n 较大的情况==

坚持原创,您的支持将鼓励我继续创作!